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

Математика. Натуральные числа: Алгоритм Евклида // Центр онлайн-обучения «Фоксфорд»

Функция от x и y, обозначающая цветом, следуя по спектру, число итераций по алгоритму Евклида. Наиболее явный синий луч — золотая пропорция

Алгоритм Евклида — издревле известный алгоритм, находящий наибольший общий делитель двух натуральных чисел, через повтор операции деления с остатком. Носит имя древнегреческого математика Евклида.

На языке Scheme:

(define (E m n)
 (cond ((= n 0) m) (else (E n (modulo m n)))))

Словами: при вводе $m,n:m>n$, если n ноль, ответ m,
иначе рекурсия со вводом (n и (остаток от деления m на n)).

Выглядит в развернутом виде так:
$m=na_{0}+b_{0}$, $0<b_{0}<n$
$n=b_{0}a_{1}+b_{1}$, $0<b_{1}<b_{0}$
$b_{0}=b_{1}a_{2}+b_{2}$, $0<b_{2}<b_{1}$
…
$b_{k-3}=b_{k-2}a_{k-1}+b_{k-1}$, $0<b_{k-1}<b_{k-2}$
$b_{k-2}=b_{k-1}a_{k}$ (деление нацело).

Если вводится числитель и знаменатель рационального числа́, то разложение по алгоритму Евклида выдаёт чи́сла, образующие его цепную дробь:
${\frac {m}{n}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}$

Если обозначить наибольший общий делитель чисел a и b как НОД(a, b), то увидим, что в процессе алгоритма Евклида вычисляется наибольший общий делитель заданных m и n:
НОД(m, n) = НОД(n, b₀) = НОД(b₀, b₁) = … = НОД (b_k-2,b_k-1) = b_k-1.

Также по индукции доказывается, что на каждом шаге r выполнено b_r = mx_r + ny_r для некоторых целых x_r и y_r.

В частности, существует представление НОД(m, n) = mx + ny для некоторых целых x и y.

Отсюда выводится, что если натуральное число a не делится на простое число p, то существуют такие целые x и y, что ax + py = 1. Из этого следует, что если произведение двух натуральных чисел ab делится на простое число p, то хотя бы одно из них делится на p. Этот факт является ключевым при доказательстве основной теоремы арифметики о единственности разложения натуральных чисел на простые множители, которая опирается на то, что для натуральных чисел существует алгоритм Евклида. Алгебраическим языком это выражается так: в кольце целых чисел все идеалы главные, а значит оно факториальное (с единственным разложением на простые).