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

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

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

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

В стандартной форме алгоритм применяют к положительным целым числам $a$ и $b$, где $a\ge b$. Он возвращает НОД этой пары. Если числа имеют разные знаки, перед вычислением используют их абсолютные значения.

Основная идея состоит в том, что НОД не изменяется, если большее число заменить остатком от деления на меньшее. Поэтому вместо исходных чисел постепенно рассматривают всё меньшие пары.

Формула Евклида

Деление с остатком записывают так:

где:

• $a$ — делимое;
• $b$ — делитель;
• $q$ — неполное частное;
• $r$ — остаток;
• $0\le r<b$.

Из этой записи следует переход:

Иными словами, пару $(a,b)$ заменяют парой $(b,r)$. Затем делят $b$ на $r$, получают новый остаток и повторяют процедуру:

Процесс заканчивается, когда очередной остаток становится равен нулю. Последний ненулевой остаток и есть НОД исходных чисел.

Например, если на последнем шаге получается

то

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

Для нахождения НОД двух чисел используют такую последовательность:

1. Взять абсолютные значения чисел и расположить их по убыванию.
2. Разделить большее число на меньшее с остатком.
3. Заменить пару чисел парой «бывший делитель и остаток».
4. Повторять деление до тех пор, пока остаток не станет равен нулю.
5. Взять последний ненулевой остаток.

Рассмотрим числа $252$ и $105$.

Сначала делим $252$ на $105$:

Теперь делим $105$ на полученный остаток $42$:

Следующий шаг:

Последний ненулевой остаток равен $21$, поэтому

Ответ можно представить в виде цепочки:

Важно не принимать за ответ первый полученный остаток. В данном примере остаток $42$ ещё не является НОД: после следующего деления появляется меньший ненулевой остаток $21$.

Почему алгоритм Евклида работает

Пусть

Любой общий делитель чисел $a$ и $b$ делит их линейную комбинацию:

Значит, если некоторое число делит и $a$, и $b$, то оно делит и $r$. Следовательно, общий делитель пары $(a,b)$ является общим делителем пары $(b,r)$.

Верно и обратное рассуждение. Если число делит $b$ и $r$, то из равенства

оно делит и $a$. Поэтому пары $(a,b)$ и $(b,r)$ имеют один и тот же набор общих делителей, а значит, и один и тот же НОД:

Последовательность вычислений обязательно завершается. После каждого деления остаток меньше предыдущего делителя и неотрицателен:

Получается последовательность неотрицательных целых чисел, которая строго убывает, пока остатки не достигнут нуля. Бесконечно уменьшаться среди таких чисел она не может.

Псевдокод алгоритма

Алгоритм можно записать в виде псевдокода:

НОД(a, b):
      a := |a|
      b := |b|

      пока b ≠ 0:
          r := a mod b
          a := b
          b := r

      вернуть a

Здесь a mod b обозначает остаток от деления $a$ на $b$. После каждой итерации значение $b$ становится меньше, поэтому цикл завершается.

Например, реализация на Python выглядит так:

def gcd(a, b):
      a = abs(a)
      b = abs(b)

      while b != 0:
          a, b = b, a % b

      return a

Проверка:

print(gcd(252, 105))  # 21

Время работы алгоритма зависит от количества выполненных делений. Для двух чисел алгоритм Евклида работает за $O(\log min(|a|,|b|))$ шагов, поэтому обычно значительно быстрее полного перебора делителей или разложения чисел на простые множители.

Примеры применения алгоритма

Нахождение НОД за несколько делений

Найдём НОД чисел $544$ и $119$:

Последний ненулевой остаток равен $17$. Следовательно,

Пример с точным делением

Найдём НОД чисел $126$ и $84$:

На втором шаге деление выполняется без остатка. Поэтому последний ненулевой остаток равен $42$:

Точное деление не означает, что ответом является частное $2$. Ответом служит делитель, на который число разделилось без остатка, то есть $42$.

Проверка результата

Результат можно проверить делением исходных чисел на найденный НОД. Для пары $544$ и $119$ был получен НОД $17$:

Оба частных являются целыми, поэтому $17$ действительно является общим делителем. Чтобы убедиться, что он наибольший, достаточно опираться на выполненные шаги алгоритма: последний ненулевой остаток по свойству алгоритма Евклида и есть НОД.

Для пары $126$ и $84$ проверка выглядит так:

Оба исходных числа делятся на $42$ без остатка.

Алгоритм Евклида для нескольких чисел

НОД нескольких чисел находят последовательно. Сначала вычисляют НОД первых двух чисел, затем находят НОД полученного результата и третьего числа. Для четырёх и более чисел действуют аналогично.

Для трёх чисел $a$, $b$ и $c$ схема имеет вид:

Рассмотрим числа $84$, $126$ и $210$.

Сначала найдём НОД первой пары:

Значит,

Теперь найдём НОД числа $42$ и третьего числа $210$:

Следовательно,

Порядок последовательного объединения не меняет результата, но на практике удобно каждый раз заменять уже обработанную группу её НОД:

НОД и наименьшее общее кратное

С помощью алгоритма Евклида можно находить не только НОД, но и наименьшее общее кратное — НОК. Для ненулевых целых чисел выполняется формула:

Например, для чисел $12$ и $18$:

поэтому

Формулу обычно применяют после вычисления НОД. В программной реализации сначала находят НОД, а затем выполняют деление, чтобы не увеличивать промежуточное произведение без необходимости:

def lcm(a, b):
      if a == 0 or b == 0:
          return 0
      return abs(a // gcd(a, b) * b)

Особые случаи

Одно из чисел равно нулю

Для целого числа $a$, не равного нулю, выполняется:

Действительно, общие делители чисел $a$ и $0$ совпадают с делителями числа $|a|$, а наибольший положительный из них равен $|a|$. Например:

При практическом выполнении алгоритма удобно сначала заменить числа их абсолютными значениями. Если второе число равно нулю, вычисление прекращают: модуль первого числа является ответом.

Отрицательные числа

Знак числа не влияет на его общие делители. Поэтому перед применением алгоритма отрицательные числа заменяют абсолютными значениями:

Далее выполняют обычные шаги:

Отсюда

Обычно НОД выбирают неотрицательным. Если хотя бы одно из чисел ненулевое, его значение положительно.

Два нулевых числа

Случай

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

Итак, алгоритм Евклида применим к двум целым числам, не равным нулю одновременно. Для отрицательных значений используют модули, а при наличии одного нуля НОД равен модулю второго числа.