Алгоритм Евклида. Нахождение наибольшего общего делителя

Евклид - древнегреческий математик.

Работал в Александрии в 3 в. до н. э.

Главный труд ""Начала"" (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов, оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.

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

(нахождение наибольшего общего делителя)

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

Описание алгоритма нахождения НОД делением

1. Большее число делим на меньшее.

2. Если делится без остатка, то меньшее число и есть НОД.

3. Если есть остаток, то меньшее число делим на первый остаток .

4. Первый остаток на второй и т. д. пока деление не закончится без остатка.

Пример:

Найти НОД для 30 и 18.

30/18 = 1 (остаток 12)

18/12 = 1 (остаток 6)

12/6 = 2 (остаток 0). Конец: НОД – это делитель.

НОД (30, 18) = 6

Описание алгоритма нахождения НОД вычитанием

1. Из большего числа вычитаем меньшее.

2. Если получается 0, то значит, что числа равны друг другу и являются НОД.

3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

Пример:

Найти НОД для 30 и 18.

30 - 18 = 12

18 - 12 = 6

12 - 6 = 6

6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6