Существуют разные способы поиска НОД. Одним из наиболее эффективных из них является алгоритм Евклида для вычисления наибольшего общего делителя. Рассмотрим его подробнее.
Алгоритм Евклида для нахождения НОД — это последовательное деление с остатком.
На каждом этапе нахождения НОД с помощью алгоритма Евклида производится деление большего из пары двух чисел на меньшее, а остаток записывается и используется при дальнейших вычислениях в качестве нового делителя для предыдущего.
Вычисление остатка производят до тех пор, пока он не будет равен нулю, тогда последний использованный делитель и будет являться наибольшим общим делителем, полученным через алгоритм Евклида.
Пусть даны два числа a= и , причём и оба этих числа не равны нулю. Тогда если предположить, что равно нулю, то НОД этих двух чисел будет равен . Рассмотрим теперь случай, когда не равно нулю. В этом случае остаток от деления на пусть будет , тогда справедливо равенство:
Пусть будет частным от деления на , тогда при любом целом , числа и имеют те же общие делители, что и числа и .
То есть применение алгоритма Евклида для нахождения наибольшего общего делителя есть не что иное, как последовательная цепочка вычислений остатков и частных от деления.
Цепочку вычисления НОД с помощью алгоритма Евклида можно записать так:
;
;
.
Вычисления продолжаются до тех пор пока остаток не станет равным нулю, тогда за НОД принимается .
Каждое последовательное вычисление нового остатка называется итерацией.
Рисунок 1. Алгоритм Евклида: блок-схема. Автор24 — интернет-биржа студенческих работ
Рассмотрим пример на получение НОД через алгоритм Евклида.
Осуществите вычисление НОД с помощью алгоритма Евклида для пары
При вычислении НОД получаем последовательно пары чисел:
;
;
;
;
— последняя пара является конечной, так как остаток равен нулю. Значит, наибольшим общим делителем для чисел и является число .
Алгоритм Евклида: доказательство
Докажем корректность алгоритма Евклида с помощью двух этапов.
Сначала рассмотрим последний остаток , не равный нулю.
Этот остаток является делителем обоих чисел и . Так как этот остаток является общим делителем, то он должен быть меньше или равен некоторому .
Для того чтобы показать, что является делителем и , запишем предыдущий остаток через :
;
Так как последний остаток , то также должен быть делителем :
, так как он является делителем обоих слагаемых в правой части равенства.
Проведя последующие итерации, получается, что является делителем всех предыдущих остатков, включая и .
При этом ни один из предыдущих остатков не является делителем и , так как деление на них происходит с остатком.
Поэтому является общим делителем и , при этом меньшим, либо равным .
На втором этапе показываем, что любой общий делитель и , в том числе и , должен делиться на .
Возьмём любое число , являющееся делителем и , также оно должно быть делителем любого получающегося остатка .
Соответственно, числа и можно представить как и , причём — натуральные числа.
Получается, что является делителем , так как .
Используя аналогичные рассуждения, можно доказать, что является делителем всех остатков.
Таким образом, получается, что должен быть делителем , что значит, что .
Также должен быть меньше или равен . Это и предыдущее заключение что противоречат друг другу во всех случаях, кроме , следовательно, .
То есть является НОД, полученным через алгоритм Евклида.
НОД: расширенный алгоритм Евклида
Расширенный алгоритм Евклида рассматривает НОД через линейную комбинацию этих чисел с некоторыми целыми коэффициентами.
Здесь остатки вычисляются по следующим формулам:
;
.
.