Алгоритм Евклида для нахождения НОД
В статье наибольший общий делитель (НОД), определение, примеры, свойства НОД мы сформулировали и доказали алгоритм Евклида. Алгоритм Евклида является универсальным способом, позволяющим вычислять наибольший общий делитель двух положительных целых чисел.
Напомним суть алгоритма Евклида. Для нахождения наибольшего общего делителя двух чисел aи b (a и b – целые положительные числа, причем a больше или равно b) последовательно выполняется деление с остатком, которое дает ряд равенств вида
Деление заканчивается, когда rk+1=0, при этом rk=НОД(a, b).
Рассмотрим примеры нахождения НОД по алгоритму Евклида.
Пример.
Найдите наибольший общий делитель чисел 64 и 48.
Решение.
Воспользуемся алгоритмом Евклида. В этом примере a=64, b=48.
Делим 64 на 48, получаем 64:48=1 (ост. 16) (при необходимости смотрите правила и примеры деления с остатком), что можно записать в виде равенства 64=48·1+16, то есть,q1=1, r1=16.
Теперь делим b на r1, то есть, 48 делим на 16, получаем 48:16=3, откуда имеем48=16·3. Здесь q2=3, а r2=0, так как 48 делится на 16 без остатка. Мы получили r2=0, поэтому это был последний шаг алгоритма Евклида, и r1=16 является искомым наибольшим общим делителем чисел 64 и 48.
Ответ:
НОД(64, 48)=16.
Покажем решение еще одного примера, но теперь обойдемся без подробных пояснений шагов алгоритма Евклида.
Пример.
Чему равен НОД чисел 111 и 432?
Решение.
Из свойств наибольшего общего делителя мы знаем, что НОД(111, 432)=НОД(432, 111). Воспользуемся алгоритмом Евклида для нахождения НОД(432, 111).
Разделив 432 на 111, получаем равенство 432=111·3+99.
На следующем шаге делим 111 на 99, имеем 111=99·1+12.
Деление 99 на 12 дает равенство 99=12·8+3.
А 12 на 3 делится без остатка и 12=3·4. Поэтому это последний шаг алгоритма Евклида, и НОД(432, 111)=3, следовательно, и искомый наибольший общий делитель чисел 111 и432 равен 3.
Ответ:
НОД(111, 432)=3.
Для закрепления материала найдем с помощью алгоритма Евклида наибольший общий делитель чисел 661 и 113.
Пример.
Найдите НОД(661, 113) по алгоритму Евклида.
Решение.
Выполняем деление: 661=113·5+96; 113=96·1+17; 96=17·5+11; 17=11·1+6; 11=6·1+5;6=5·1+1, наконец, 5=1·5. Таким образом, НОД(661, 113)=1, то есть, 661 и 113 –взаимно простые числа.
Заметим, что если бы мы с самого начала обратились к таблице простых чисел, то выяснили бы, что числа 661 и 113 – простые, откуда можно было бы сразу сказать, что их наибольший общий делитель равен 1.
Ответ:
НОД(661, 113)=1.
К началу страницы