Убедимся, что любой общий делитель всякой пары натуральных чисел является также и общим делителем пары : если уменьшаемое делится на число , то оно имеет вид , если вычитаемое делится на число , то оно имеет вид , тогда

то есть их разность также делится на число .

Аналогично доказывается, что любой общий делитель пары является общим делителем пары , следовательно,

Пусть . Можно свести НОД к наибольшему общему делителю другой пары чисел, в которой наибольшее из чисел окажется меньше, чем , а именно: НОД НОД.

Таким образом, можно получить последовательность равенств вида НОД или вида НОД, но НОД НОД.

Такую последовательность действительно можно получить, так как при получается, что и , то есть в равенстве НОД НОД максимум из чисел под знаком НОД в правой части с каждым таким шагом уменьшается по крайней мере на 1, но числа и – конечны, следовательно, через конечное число преобразований можно получить цепочку равенств вида НОД.

 

Назовём выражение вида , где линейной комбинацией над чисел и . Ясно, что сумма линейных комбинаций над чисел и снова линейная комбинация над чисел и , разность линейных комбинаций над чисел и снова линейная комбинация над чисел и .

 

Последнее полученное равенство можно продолжить:

При этом число получалось последовательным вычитанием из линейной комбинации над чисел и линейных комбинаций над чисел и , то есть есть линейная комбинация над чисел и , следовательно, существуют целые числа и , такие что .