section_heading: Dokaz
paragraph_text: Dokaz ćemo da <math> d \mid a, d \mid b, </math> ali i da je <math> d = M(a, b). </math> Pretpostavimo bez smanjenja općenitosti (BSO) da <math> d \nmid a. </math> Prema teoremu o dijeljenju s ostatkom možemo pisati <math> a = dq + r,\ q \in \mathbb{Z},\ r = \{1, 2, ..., d - 1\}. </math> Dobivamo <math> r = a - dq. </math> Koristeći (1) dobivamo <math> r = a(1 - kq) + b(-ql), </math> što znači <math> r \in S </math>. No, <math> 0 < r < d, </math> što je kontradikcija jer je <math> d = \min S. </math> Dakle, <math> d \mid a </math> i analogno <math> d \mid b. </math>