Презентация на тему Алгоритм Евклида

наибольшего общего делителя (НОД) двух натуральных чисел.
Вспомним математику. Наибольший

общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:
НОД(12,18) = 6.
Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М,N).

Но зато достаточно давно, задолго до появления ЭВМ, был

известен алгоритмический способ решения этой задачи.
Называется он алгоритмом Евклида.

что если M>N, то
НОД(М,N) = НОД(М - N,N).
Иначе говоря,

НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа.

(M>N). Это значит, что М = тК, N =

пК, где т, п — натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К — делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их раз­ности M-N, в том числе и наибольший общий делитель. Отсюда:
НОД(М,N) = НОД(М - N,N).
Второе очевидное свойство:
НОД(М,М) = М.

них в качестве ответа, в противном случае продолжить выполнение

алгоритма;
заменить большее число разностью большего и меньшего из чисел;
вернуться к выполнению п. 1.

нахождения наибольшего общего делителя для двух натуральных чисел