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

Существуют разные способы поиска НОД. Одним из наиболее эффективных из них является алгоритм Евклида для вычисления наибольшего общего делителя. Рассмотрим его подробнее.

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

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

Пусть даны два числа a=$f_0$ и $b=f_1$, причём $f_0≥f_1$ и оба этих числа не равны нулю. Тогда если предположить, что $f_1$ равно нулю, то НОД этих двух чисел будет равен $f_0$. Рассмотрим теперь случай, когда $f_1$ не равно нулю. В этом случае остаток от деления $f_0$ на $f_1$ пусть будет $f_2$, тогда справедливо равенство:

$НОД(f_0, f_1)= НОД(f_1, f_2)$

Пусть $a$ будет частным от деления $f$ на $g$, тогда при любом целом $a$, числа $f_0$ и $f_1$ имеют те же общие делители, что и числа $f_1$ и $f_2=(f_0-a\cdot f_1)$.

Цепочку вычисления НОД с помощью алгоритма Евклида можно записать так:

$f_0=a_1 \cdot f_1 + f_2$;

$f_1=a_2 \cdot f_2 + f_3$;

$...$

$f_n=a_n \cdot f_{n+1} + f_{n+2}$.

Вычисления продолжаются до тех пор пока остаток $f_{n+2}$ не станет равным нулю, тогда за НОД принимается $f_{n+1}$.

Рисунок 1. Алгоритм Евклида: блок-схема. Автор24 — интернет-биржа студенческих работ

Рассмотрим пример на получение НОД через алгоритм Евклида.

Алгоритм Евклида: доказательство

Докажем корректность алгоритма Евклида с помощью двух этапов.

Сначала рассмотрим последний остаток $f_{n-1}$, не равный нулю.

Этот остаток является делителем обоих чисел $a$ и $b$. Так как этот остаток является общим делителем, то он должен быть меньше или равен некоторому $НОД=g$.

Для того чтобы показать, что $f_{n-1}$ является делителем $a$ и $b$, запишем предыдущий остаток через $f_{n-1}$:

$f_{n-2}=q_{n}f_{n-1}$;

Так как последний остаток $f_{n-1}=0$, то$ f_{n-1}$ также должен быть делителем $f_{n-3}$:

$f_{n-3}=q_{n-1}f_{n-2}+f_{n-1}$, так как он является делителем обоих слагаемых в правой части равенства.

Проведя последующие итерации, получается, что $f_{n-1}$ является делителем всех предыдущих остатков, включая $a$ и $b$.

При этом ни один из предыдущих остатков не является делителем $a$ и $b$, так как деление на них происходит с остатком.

Поэтому $f_{n-1}$ является общим делителем $a$ и $b$, при этом меньшим, либо равным $g$.

На втором этапе показываем, что любой общий делитель $a$ и $b$, в том числе и $g$, должен делиться на $f_{n-1}$.

Возьмём любое число $c$, являющееся делителем $a$ и $b$, также оно должно быть делителем любого получающегося остатка $f_k$.

Соответственно, числа $a$ и $b$ можно представить как $a=mc$ и $b=lc$, причём $l, m$ — натуральные числа.

Получается, что $c$ является делителем $f_1$, так как $f_1=a-q_0lc=(m-q_0l)c$.

Используя аналогичные рассуждения, можно доказать, что $c$ является делителем всех остатков.

Таким образом, получается, что $НОД=g$ должен быть делителем $f_{n-1}$, что значит, что $g≤f_{n-1}$.

Также $g$ должен быть меньше или равен $r_{n-1}$. Это и предыдущее заключение что $f_{n-1}≤g$ противоречат друг другу во всех случаях, кроме $f{n-1}=g$, следовательно, $g=f_{n-1}$.

То есть $f_{n-1}$ является НОД, полученным через алгоритм Евклида.

НОД: расширенный алгоритм Евклида

Расширенный алгоритм Евклида рассматривает НОД через линейную комбинацию этих чисел с некоторыми целыми коэффициентами.

Здесь остатки вычисляются по следующим формулам:

$r_1=a-bq_0$;

$r_2=b-r_1q_1=b-(a-bq_0)q_1=b(1+q_0q_1)-aq_1$.

$r_n=r_{n-2}-r_{n-1}q_{n-1}=...ax+by$.