Cho $d$ là ước số chung lớn nhất của $2$ số $a$ và $b$. Chứng minh rằng tồn tại các số nguyên $m$ và $n$ sao cho  $ am +bn =d$.

Gọi d’ > 0 là giá trị nhỏ nhất của số có dạng (am + bn),với m,n thuộc Z, và m, n độc lập với nhau: $ {\rm{d’ }} = {\rm{ am }} + {\rm{ bn’}} $
Giả sử  $ {\rm{am }} + {\rm{ bn}} \vdots {\rm{d’}} $  $ \begin{array}{l} \Leftrightarrow {\rm{am }} + {\rm{ bn  = d’q  +  r}}
{\rm{q}} \in {\rm{N,r}} \in {\rm{Z,r \end{array} $
Do đó : $ r = {\rm{am }} + {\rm{ bn – (am’ }} + {\rm{ bn’}})q \Leftrightarrow r = {\rm{a(m  –  m’}}q) + b(n – n’q) $
Điều này có nghĩa là tồn tại một số r > 0 có dạng (am + bn) và r Vậy :  $ {\rm{am }} + {\rm{ bn}} \vdots {\rm{d’}} $  $  \Leftrightarrow {\rm{d’}} | {{\rm{am }} + {\rm{ bn}}}  $
Ta chọn  $ {\rm{m }} = {\rm{ 1 }};{\rm{ n }} = {\rm{ }}0 $  $  \Rightarrow d\left| {a.1 + b.0 = a} \right. $
Ta lại chọn  $ {\rm{m }} = {\rm{ }}0,{\rm{ n }} = {\rm{ 1 }}: $  $  \Rightarrow d’\left| b \right. $
Do đó d’ là ước số chung của a và b $  \Leftrightarrow d’\left| {d = (a,b)} \right. $                                 (1)
Mặt khác $ \begin{array}{l}
d = (a,b) \Rightarrow d\left| {a \wedge d} \right|b \Rightarrow d\left| {am + bn} \right.\\
\forall m,n \in Z\\
 \Rightarrow d\left| {d’} \right. &  &  &  &  & (2)
\end{array} $                        
Từ (1), và (2)  $  \Rightarrow d = d’ $ (đpcm)