Как найти НОД двух чисел по алгоритму Евклида

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

Алгоритм Евклида — один из наиболее ранних численных алгоритмов в истории. Название было дано в честь греческого математика Евклида, который впервые дал ему описание в книгах «Начала». Изначально назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль. Сегодня чаще используется взятие остатка от деления вместо вычитания, но суть метода сохранилась.

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

Понятие НОД

Аббревиатура НОД расшифровывается как «наибольший общий делитель».

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

Основная суть алгоритма Евклида

Суть алгоритма заключается в построении ряда следующего вида (при условии, что a больше b):

a, b, x₁, x₂, x₃, … x_n.

В нем каждое последующее число — это остаток от деления двух предыдущих, ряд заканчивается, когда остаток от деления становится равным 0 — при условии использования деления.

В нем каждое последующее число является результатом вычитания двух предыдущих, ряд заканчивается, когда частное становится равным 0 — при условии использования вычитания.

Последовательность нахождения НОД при помощи деления:

1. Большее число делится на меньшее.
2. Если результат деления:

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

3. Переход к пункту 1.

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

1. Из большего числа вычитается меньшее.
2. Если результат вычитания:

• равен 0, то числа равны друг другу и являются НОД;
• не равен 0, в таком случае большее число заменяется на результат вычитания.

3. Переход к пункту 1.

Примеры решения задач с алгоритмом Евклида

Решение:

128 — 96 = 32

96 — 32 = 64

64 — 32 = 32

32 — 32 = 0

Или

128 / 96 = 1 (остаток 32)

96 / 32 = 3

Ответ: 32

Решение:

37 / 17 = 2 (остаток 3)

17 / 3 = 5 (остаток 2)

3 / 2 = 1 (остаток 1)

2 / 1 = 2 (остаток 0)

Или

37 — 17= 20

20 — 17 = 3

17 — 3 = 14

14 — 3 = 11

11 — 3 = 8

8 — 3 = 5

5 — 3 = 2

3 — 2 = 1

2 — 1 = 1

1 — 1 = 0

Числа 37 и 17 являются простыми, соответственно, их НОД — единица. Совет: перед вычислениями проверяйте таблицу простых чисел.

Ответ: 1