Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

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

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

Определение 1

Алгоритм Евклида для нахождения НОД — это последовательное деление с остатком.

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

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

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

НОД(f0,f1)=НОД(f1,f2)

Пусть a будет частным от деления f на g, тогда при любом целом a, числа f0 и f1 имеют те же общие делители, что и числа f1 и f2=(f0af1).

Замечание 1

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

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

f0=a1f1+f2;

f1=a2f2+f3;

...

fn=anfn+1+fn+2.

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

Определение 2

Каждое последовательное вычисление нового остатка называется итерацией.

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

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

«Алгоритм Евклида » 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Помощь с рефератом от нейросети
Написать ИИ

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

Пример 1

Осуществите вычисление НОД с помощью алгоритма Евклида для пары (39;15)

При вычислении НОД получаем последовательно пары чисел:

НОД(39;15);

НОД(15;9);

НОД(9;6);

НОД(6;3);

НОД(3;0) — последняя пара является конечной, так как остаток равен нулю. Значит, наибольшим общим делителем для чисел 39 и 15 является число 3.

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

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

Сначала рассмотрим последний остаток fn1, не равный нулю.

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

Для того чтобы показать, что fn1 является делителем a и b, запишем предыдущий остаток через fn1:

fn2=qnfn1;

Так как последний остаток fn1=0, тоfn1 также должен быть делителем fn3:

fn3=qn1fn2+fn1, так как он является делителем обоих слагаемых в правой части равенства.

Проведя последующие итерации, получается, что fn1 является делителем всех предыдущих остатков, включая a и b.

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

Поэтому fn1 является общим делителем a и b, при этом меньшим, либо равным g.

На втором этапе показываем, что любой общий делитель a и b, в том числе и g, должен делиться на fn1.

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

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

Получается, что c является делителем f1, так как f1=aq0lc=(mq0l)c.

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

Таким образом, получается, что НОД=g должен быть делителем fn1, что значит, что gfn1.

Также g должен быть меньше или равен rn1. Это и предыдущее заключение что fn1g противоречат друг другу во всех случаях, кроме fn1=g, следовательно, g=fn1.

То есть fn1 является НОД, полученным через алгоритм Евклида.

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

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

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

r1=abq0;

r2=br1q1=b(abq0)q1=b(1+q0q1)aq1.

rn=rn2rn1qn1=...ax+by.

Дата последнего обновления статьи: 29.03.2024
Получи помощь с рефератом от ИИ-шки
ИИ ответит за 2 минуты
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot

Изучаешь тему "Алгоритм Евклида "? Могу объяснить сложные моменты или помочь составить план для домашнего задания!

AI Assistant