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

Дано: числа $a = 1071$ и $b = 462$. Найти: их наибольший общий делитель, наименьшее общее кратное и коэффициенты Безу.

Рабочий метод - алгоритм Евклида: делим большее число на меньшее с остатком, затем прежний делитель на полученный остаток, и так до нулевого остатка. Последний ненулевой остаток и есть ответ: НОД(1071, 462) = 21, отсюда НОК(1071, 462) = 23 562, а расширенный алгоритм даёт соотношение $-3 \cdot 1071 + 7 \cdot 462 = 21$. Калькулятор сверху прогоняет ту же лестницу делений для любой пары чисел, ниже - решение по шагам.

Решение по шагам

Дано. $a = 1071$, $b = 462$.

Найти. $\gcd(1071, 462)$, $\operatorname{lcm}(1071, 462)$ и целые $x$, $y$ такие, что $1071x + 462y = \gcd(1071, 462)$.

Шаг 1. Делим большее число на меньшее с остатком.

$$1071 = 2 \cdot 462 + 147.$$

Остаток 147 не равен нулю, значит останавливаться рано. Новая пара для следующего шага - делитель и остаток текущего шага, то есть 462 и 147.

Шаг 2. Делим прежний делитель на прежний остаток.

$$462 = 3 \cdot 147 + 21.$$

Остаток 21 снова ненулевой, поэтому берём следующую пару: 147 и 21.

Шаг 3. Повторяем деление, пока остаток не обнулится.

$$147 = 7 \cdot 21 + 0.$$

Остаток стал нулевым, алгоритм закончил работу. Последний ненулевой остаток равен 21, и это ответ первой части задачи.

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

Шаг 4. Проверяем ответ. Оба исходных числа обязаны делиться на найденный НОД нацело, а получившиеся частные - быть взаимно простыми:

$$1071 : 21 = 51, \qquad 462 : 21 = 22.$$

Деление прошло без остатка, а числа 51 и 22 общих делителей, кроме единицы, не имеют, потому что $51 = 3 \cdot 17$, а $22 = 2 \cdot 11$. Значит 21 - именно наибольший общий делитель, а не какой-то промежуточный общий делитель вроде 3 или 7.

Шаг 5. Находим НОК через уже известный НОД. Наименьшее общее кратное не требует отдельного алгоритма: оно связано с НОД произведением самих чисел.

$$\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)} = \frac{1071 \cdot 462}{21} = \frac{494\,802}{21} = 23\,562.$$

Ответ. $\gcd(1071, 462) = 21$, $\operatorname{lcm}(1071, 462) = 23\,562$.

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

Весь метод держится на одном равенстве: если $a = qb + r$, то

$$\gcd(a, b) = \gcd(b, r).$$

Доказывается оно в две строки. Любой общий делитель $d$ чисел $a$ и $b$ делит и разность $r = a - qb$, то есть он общий делитель пары $(b, r)$. Обратно, любой общий делитель пары $(b, r)$ делит сумму $qb + r = a$, то есть он общий делитель пары $(a, b)$. Множества общих делителей у двух пар совпадают полностью, а раз совпадают множества, совпадают и их наибольшие элементы.

Дальше работает убывание. Остаток при делении всегда строго меньше делителя, поэтому последовательность $b > r_1 > r_2 > \dots \ge 0$ строго убывает и состоит из целых неотрицательных чисел. Бесконечно убывать такая последовательность не может, значит через конечное число шагов остаток обязательно станет нулём. В этот момент пара выглядит как $(\gcd, 0)$, а наибольший общий делитель числа и нуля равен самому числу - на нуль делится всё.

Скорость у метода отличная: число шагов растёт примерно как логарифм меньшего из чисел, худший случай дают соседние числа Фибоначчи. Для пары 1071 и 462 хватило трёх делений, для пары из десятизначных чисел понадобится порядка полусотни. Именно поэтому в вычислительной арифметике НОД ищут Евклидом, а не разложением на множители: разложить большое число на простые несопоставимо дороже, на этой разнице стоит вся асимметричная криптография.

Расширенный алгоритм Евклида и коэффициенты Безу

Соотношение Безу утверждает, что НОД любых двух целых чисел представим в виде $ax + by$ с целыми $x$ и $y$. Найти эти коэффициенты можно, раскрутив ту же лестницу в обратную сторону. Берём предпоследнюю строку таблицы и выражаем из неё остаток:

$$21 = 462 - 3 \cdot 147.$$

Теперь из первой строки выражаем 147 и подставляем вместо него:

$$147 = 1071 - 2 \cdot 462 \quad\Longrightarrow\quad 21 = 462 - 3 \cdot (1071 - 2 \cdot 462).$$

Раскрываем скобки и приводим подобные, аккуратно собирая коэффициенты при 1071 и при 462 по отдельности:

$$21 = -3 \cdot 1071 + 7 \cdot 462.$$

Проверка занимает одну строку: $-3 \cdot 1071 = -3213$, $7 \cdot 462 = 3234$, разность равна 21. Итак, $x = -3$, $y = 7$. Один из коэффициентов почти всегда отрицательный, и это нормально: положительными оба они бывают только в вырожденных случаях.

Коэффициенты Безу нужны не ради красоты. Если $\gcd(a, m) = 1$, то из равенства $ax + my = 1$ сразу следует $ax \equiv 1 \pmod m$, то есть $x$ - обратный элемент к $a$ по модулю $m$. Так находят обратные при расшифровке в схеме Эль-Гамаля и в других системах с открытым ключом, где рядом стоит быстрое возведение в степень по модулю. Тот же расширенный алгоритм решает линейные диофантовы уравнения $ax + by = c$: они разрешимы ровно тогда, когда $c$ делится на $\gcd(a, b)$.

Второй способ: сравнить разложения на простые множители

Школьный способ выглядит иначе: раскладываем оба числа на простые и берём общие множители в наименьших степенях. Здесь $1071 = 3^2 \cdot 7 \cdot 17$, $462 = 2 \cdot 3 \cdot 7 \cdot 11$, общими оказываются тройка и семёрка в первой степени, откуда $\gcd = 3 \cdot 7 = 21$ - тот же ответ. Если взять максимальные степени вместо минимальных, получится НОК: $2 \cdot 3^2 \cdot 7 \cdot 11 \cdot 17 = 23\,562$.

Отсюда же видно, почему верна формула связи. Для каждого простого $p$ показатели в разложениях складываются: $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$, а произведение по всем простым и даёт $\gcd \cdot \operatorname{lcm} = a \cdot b$. Переключатель графика в калькуляторе сверху показывает ровно эту картинку: столбики показателей для обоих чисел, для их НОД и для НОК. На контрольной способ хорош для двузначных и трёхзначных чисел, но уже для четырёхзначных разложение занимает больше времени, чем три деления Евклидом.

Частые ошибки

• Останавливаются на нулевом остатке и берут его за ответ. Ответ - последний ненулевой остаток. В нашем примере это 21, а не 0.
• Делят не то на то. На каждом шаге делимым становится прежний делитель, а делителем - прежний остаток. Если по инерции продолжить делить исходное число, лестница развалится.
• Путают неполное частное и остаток. В записи $1071 = 2 \cdot 462 + 147$ частное 2 в дальнейшем не участвует вовсе, работает только остаток 147. Частные понадобятся лишь в расширенном алгоритме.
• Считают НОК как произведение чисел. Произведение $1071 \cdot 462 = 494\,802$ кратно обоим числам, но наименьшим кратным не является: делить на НОД обязательно.
• Берут общие простые в наибольших степенях. Во втором способе НОД собирается из минимальных показателей, максимальные дают НОК. Перепутанные минимум и максимум меняют ответы местами.
• Теряют знак в соотношении Безу. При обратной подстановке скобка $-3 \cdot (1071 - 2 \cdot 462)$ даёт $+6 \cdot 462$, и это слагаемое нужно сложить с уже имеющимся $462$, получив 7, а не 6.

FAQ

Чему равен НОД, если одно из чисел делится на другое? Он равен меньшему числу. Например, $\gcd(462, 154) = 154$, потому что первое же деление даёт нулевой остаток, и последним ненулевым остатком оказывается сам делитель. Алгоритм при этом отработает за один шаг.

Что означает НОД, равный единице? Что числа взаимно просты: общих делителей, кроме единицы, у них нет. Дробь из таких чисел уже несократима, а по модулю одного из них второе обратимо, что и используют в криптографии.

Как искать НОД трёх и более чисел? Последовательно и попарно: $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$. Порядок роли не играет, а промежуточные результаты быстро уменьшаются, так что третий и четвёртый шаги обычно совсем короткие.

Изменится ли ответ, если сначала делить меньшее число на большее? Нет. При делении 462 на 1071 неполное частное равно нулю, а остаток - самому числу 462, поэтому первый шаг просто поменяет числа местами и алгоритм пойдёт как обычно. Одно лишнее деление - единственная плата за неверный порядок.

Коротко

1. Делим большее число на меньшее с остатком: $1071 = 2 \cdot 462 + 147$.
2. Повторяем деление для пары «прежний делитель, прежний остаток»: $462 = 3 \cdot 147 + 21$, затем $147 = 7 \cdot 21 + 0$.
3. Последний ненулевой остаток - ответ: $\gcd(1071, 462) = 21$. Проверка: $1071 : 21 = 51$ и $462 : 21 = 22$ взаимно просты.
4. НОК считаем через НОД: $\operatorname{lcm} = 1071 \cdot 462 / 21 = 23\,562$.
5. Коэффициенты Безу получаем обратной подстановкой: $-3 \cdot 1071 + 7 \cdot 462 = 21$.