Нахождение наибольшего общего делителя чисел с помощью алгоритма Евклида

1.

Нахождение
наибольшего общего делителя
чисел с помощью
алгоритма Евклида
Крючкова Светлана Николаевна
учитель математики МОУ «Майская гимназия
Белгородского района Белгородской области»

2.

Алгори́тм Евкли́да —
эффективный алгоритм для
нахождения наибольшего
общего делителя двух целых
чисел

3.

Алгоритм назван в честь греческого
математика Евклида
Первое описание алгоритма находится в
«Началах» Евклида (около 300 лет до н. э.),
что делает его одним из старейших
численных алгоритмов, используемых в
наше время

4.

Повторим теорию
Делителем натурального числа а
называется натуральное число, на которое а
делится без остатка
Пример
Делителями числа 12 будут числа 1; 2; 3; 4; 6 и 12
Делителями числа 18 будут числа 1; 2; 3; 6; 9 и 18

5.

Повторим теорию
Общим делителем нескольких чисел
называется такое число, которое является
делителем каждого из них
Пример
Делителями числа 12 будут числа 1; 2; 3; 4; 6 и 12
Делителями числа 18 будут числа 1; 2; 3; 6; 9 и 18
Числа 1; 2; 3; 6 - будут
общими делителями чисел 12 и 18

6.

Повторим теорию
Наибольшим общим делителем нескольких
чисел называется наибольшее число, на
которое данные числа делятся без остатка
Пример
Числа 1; 2; 3; 6 - общие делители чисел 12 и 18
6 наибольшее из этих числе, значит НОД (12;18)=6

7.

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

8.

Найдём
наибольший
общий
Пример
делитель чисел 64 и 48.
Для этого из большего числа вычтем
меньшее 64 – 48 = 16
Из полученных трех чисел выбираем два
меньших и повторяем вычитание
48 – 16 = 32 и т.д. 32 – 16 = 16 Как
только два числа стали равны, значит
полученное число и есть НОД искомых
чисел. В данном примере
НОД (64: 48) = 16

9.

Пример
Найдём наибольший общий
делитель чисел 115 и 46
Выполним вычисления по предложенному алгоритму
Ответ: НОД (115; 46) = 23