Изменения

Пусть <mathtex>a</mathtex> и <mathtex>b</mathtex> — целые числа, не равные одновременно нулю, и последовательность чисел: <mathtex> a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n</mathtex>определена тем, что каждое <mathtex>r_k</mathtex> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть: <mathtex>a = bq_0 + r_1</mathtex>: <mathtex>b = r_1q_1 + r_2</mathtex>: <mathtex>r_1 = r_2q_2 + r_3</mathtex>: <mathtex>\cdots</mathtex>: <mathtex>r_{k-2} = r_{k-1} q_{k-1} + r_k</mathtex>: <mathtex>\cdots</mathtex>: <mathtex>r_{n-1} = r_n q_n</mathtex>

Тогда НОД(''a'',''b''), наибольший общий делитель <mathtex>a</mathtex> и <mathtex>b</mathtex>, равен<mathtex>r_n</mathtex>, последнему ненулевому члену этой последовательности.

'''Существование''' таких <mathtex>r_1, r_2, ...</mathtex>, то есть возможность деления с остатком <mathtex>m</mathtex> на <mathtex>n</mathtex> для любого целого <mathtex>m</mathtex> и целого <mathtex>n\ne 0</mathtex>, доказывается индукцией по ''m''.

* Пусть <mathtex>a = bq + r</mathtex>, тогда <mathtex>\gcd (a,b) = \gcd (b,r).</mathtex>

# Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда <mathtex> a = t_1 * k </mathtex> ; <mathtex> b = t_2 * k; </mathtex> где <mathtex> t_1 </mathtex> и <mathtex> t_2 </mathtex> — целые числа из определения.# Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а <mathtex>r = a - bq = (t_1 - t_2*q)*k </mathtex> (выражение в скобках есть целое число, следовательно, k делит r без остатка)

* <mathtex>\gcd (0,r) = r</mathtex> для любого ненулевого <mathtex>r.</mathtex>

Проще сформулировать алгоритм Евклида так: если даны натуральные числа <mathtex>a</mathtex> и <mathtex>b</mathtex> и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.