$AlexLat$

Доказательство . Рассмотрим множество P = { au + bv ⎜ u,v ∈ Z }. Очевидно, что P ⊆ Z , а
знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , b , 0 ∈ P . 
Пусть x , y ∈ P и y ≠ 0 . Тогда остаток от деления x на y принадлежит P . Действительно:
x = yq + r , 0 ≤ r < y ,
r = x – yq = ( au ₁ + bv ₁ ) – ( au ₂ + bv ₂ ) q = a ( u ₁ – u ₂ q )+ b ( v 1 – v ₂ q ) ∈ P .
Пусть d ∈ P - наименьшее положительное число из P (призадумайтесь, почему такое
имеется!). Тогда а делится на d . В самом деле, a = dq + r ₁ , 0 ≤ r ₁ < d , a ∈ P , d ∈ P , значит r ₁
∈ P , следовательно r ₁ = 0. Аналогичными рассуждениями получается, что b делится на d ,
значит d - общий делитель a и b .
Далее, раз d ∈ P , то d = au 0 + bv 0 . Если теперь d ₁ - общий делитель 
a и b , то d ₁ | ( au 0 + b v 0 ), т.е. d ₁ | d . Значит d ≥ d ₁ и d - наибольший общий делитель.