|
|
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 < }}d'
\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 < d, mâu thuẫn với cách chọn d’
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)
|