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

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

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

Алгоритм Евклида — это алгоритм, основная функция которого заключается в поиске наибольшего общего делителя (НОД) для двух целых чисел.

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

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Понятие НОД

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

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

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

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

a, b, x1, x2, x3, … xn.

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

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

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

  1. Большее число делится на меньшее.
  2. Если результат деления:
  • без остатка, то меньшее число и есть НОД;
  • с остатком, тогда большее число заменяется на остаток.
  1. Переход к пункту 1.
Пример №1

60 / 36 = 1 (остаток 24)

36 / 24 = 1 (остаток 12)

24 / 12 = 2 (остаток 0)

НОД для 60 и 36 равен 12 (делитель).

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

  1. Из большего числа вычитается меньшее.
  2. Если результат вычитания:
  • равен 0, то числа равны друг другу и являются НОД;
  • не равен 0, в таком случае большее число заменяется на результат вычитания.
  1. Переход к пункту 1.
Пример №2

60 — 36 = 24

36 — 24 = 12

24 — 12 = 12

12 — 12 = 0

НОД для 60 и 36 равен 12 (уменьшаемое, вычитаемое)

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

Задача №1

Найти наибольший общий делитель для чисел 128 и 96.

Решение:

128 — 96 = 32

96 — 32 = 64

64 — 32 = 32

32 — 32 = 0

Или

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

96 / 32 = 3

Ответ: 32

Задача №2

Найти наибольший общий делитель для чисел 37 и 17.

Решение:

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

Насколько полезной была для вас статья?

Рейтинг: 4.44 (Голосов: 16)

Заметили ошибку?

Выделите текст и нажмите одновременно клавиши «Ctrl» и «Enter»