Алгоритм Евклида

Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое r_k — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq ₀ + r ₁

b = r ₁ q ₁ + r ₂

r ₁ = r ₂ q ₂ + r ₃

r_{k − 2} = r_{k − 1} q_{k − 1} + r_k

r_{n − 1} = r_nq_n

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

Существование таких r ₁, r ₂,..., то есть возможность деления с остатком m на n для любого целого m и целого , доказывается индукцией по m.

Корректность

этого алгоритма вытекает из следующих двух утверждений:

1. Пусть a = bq + r, тогда НОД (a,b) = НОД (b,r).

Доказательство.

Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда a = t₁ * k; b = t₂ * k; где t₁ и t₂ — целые числа из определения.

Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а r = a − bq = (t₁ − t₂ * q) * k (выражение в скобках есть целое число, следовательно, k делит r без остатка)

Обратное также верно и доказывается аналогично пункту 2 - любой делитель b и r так же является делителем a и b.

Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.

В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.

1. НОД (0, r) = r для любого ненулевого r.

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