This chapter hasn’t been translated into English yet, so here is the Russian original. Your browser can translate the page; the formulas and widgets work the same. Back to the English contents →

Решатель

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

Введите два числа или больше — решатель найдёт наибольший общий делитель и наименьшее общее кратное двумя способами и покажет, почему ответ верен.

Примеры: 84 и 126 НОК(12; 18; 30) 1071, 462 взаимно простые 35 и 64 Безу 240 и 46 84x + 126y = 42 6x + 9y = 7

Загружаем решатель…

Что можно ввести

Два числа или больше — через пробел, запятую или «и»: 84 и 126, 12, 18, 30. Решатель найдёт и НОД, и НОК; если нужно что-то одно, так и напишите: НОД(84; 126), НОК 12 18 30. Ещё он умеет проверять, взаимно ли просты числа (взаимно простые 35 и 64), находить коэффициенты Безу (Безу 240 и 46) и решать в целых числах уравнения вида 84x + 126y = 42.

Отрицательные числа можно: делители у $-12$ те же, что у $12$, поэтому решатель берёт модули. Ноль тоже можно: $\text{НОД}(0, 7) = 7$, ведь ноль делится на что угодно, а $\text{НОК}(0, 7) = 0$.

Алгоритм Евклида: как искать НОД

Наибольший общий делитель двух чисел — самое большое число, на которое делятся оба. Для маленьких чисел его видно сразу: $\text{НОД}(12, 18) = 6$. Для больших перебирать делители долго, а раскладывать числа на простые множители — ещё дольше. Алгоритм Евклида обходится без того и другого. Он описан в «Началах» Евклида (книга VII) больше двух тысяч лет назад, и компьютеры считают НОД именно так.

Делим большее число на меньшее с остатком: $a = b \cdot q + r$.
Если остаток равен нулю, ответ — меньшее число $b$.
Иначе заменяем пару $(a, b)$ на $(b, r)$ и повторяем.

Ответ — последний ненулевой остаток. Числа тают очень быстро: французский математик Габриель Ламе в 1844 году доказал, что делений понадобится не больше, чем пятикратное число цифр меньшего числа. Для двух двадцатизначных чисел это не больше сотни делений, а пробных делителей при разложении перебирать пришлось бы сотни миллионов.

Большее из двух чисел.

Меньшее — делитель.

Остаток, $0 \le r < b$. Он меньше $b$, поэтому пара чисел с каждым шагом уменьшается и когда-нибудь дойдёт до нуля.

Почему НОД не меняется: всё, что делит $a$ и $b$, делит и $r = a - bq$; и наоборот, всё, что делит $b$ и $r$, делит и $a = bq + r$. У пар $(a, b)$ и $(b, r)$ одни и те же общие делители, значит, и наибольший общий. Пример: $126 = 1 \cdot 84 + 42$, поэтому $\text{НОД}(126, 84) = \text{НОД}(84, 42)$, а $84 = 2 \cdot 42$ делится нацело — ответ $42$.

У алгоритма есть наглядная геометрия, её показывает картинка решателя. Возьмём прямоугольник $a \times b$ и будем отрезать от него самые большие квадраты. От $126 \times 84$ отрежется квадрат $84 \times 84$, останется полоска $84 \times 42$, и она точно покрывается двумя квадратами $42 \times 42$. Сторона последнего квадрата — НОД: такими квадратами можно замостить весь исходный прямоугольник без щелей, и никакими бо́льшими нельзя.

Как искать НОК

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

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

Пример: $\text{НОК}(84, 126) = \frac{84 \cdot 126}{42} = 2 \cdot 126 = 252$. Удобнее сначала разделить одно из чисел на НОД, а потом умножать: числа меньше. Заодно видно, что $\text{НОД} \cdot \text{НОК} = a \cdot b$ — хорошая проверка ответа.

Второй способ — через разложение на простые множители. Раскладываем оба числа: $84 = 2^2 \cdot 3 \cdot 7$, $126 = 2 \cdot 3^2 \cdot 7$. В НОД идут только общие простые множители, каждый в наименьшей из степеней: $2 \cdot 3 \cdot 7 = 42$. В НОК — все простые множители, каждый в наибольшей степени: $2^2 \cdot 3^2 \cdot 7 = 252$. Для небольших чисел это быстро и наглядно (в решателе — круги с общими множителями), для больших сначала придётся долго раскладывать.

Для трёх и более чисел считают по цепочке: $\text{НОД}(a, b, c) = \text{НОД}(\text{НОД}(a, b), c)$, и так же для НОК. А вот формула «произведение, делённое на НОД» для трёх чисел уже неверна: $\text{НОК}(2, 2, 2) = 2$, а не $8 : 2 = 4$.

Разобранные примеры

Пример 1. Сократить дробь $\frac{391}{527}$

Ни на $2$, ни на $3$, ни на $5$ эти числа не делятся, но алгоритм Евклида находит общий делитель за четыре деления:

$$527 = 1 \cdot 391 + 136,\quad 391 = 2 \cdot 136 + 119,\quad 136 = 1 \cdot 119 + 17,\quad 119 = 7 \cdot 17.$$

Последний ненулевой остаток — $17$. Значит, $391 = 17 \cdot 23$, $527 = 17 \cdot 31$ и $\frac{391}{527} = \frac{23}{31}$. Заодно $\text{НОК}(391, 527) = 23 \cdot 527 = 12\,121$.

Пример 2. Три числа: 12, 18 и 30

Разложения: $12 = 2^2 \cdot 3$, $18 = 2 \cdot 3^2$, $30 = 2 \cdot 3 \cdot 5$. Общие простые — $2$ и $3$, каждое в наименьшей степени: $\text{НОД} = 2 \cdot 3 = 6$. Все простые в наибольших степенях: $\text{НОК} = 2^2 \cdot 3^2 \cdot 5 = 180$.

По цепочке то же самое: $\text{НОД}(12, 18) = 6$, $\text{НОД}(6, 30) = 6$; $\text{НОК}(12, 18) = 36$, $\text{НОК}(36, 30) = 180$. Проверка: $180 = 12 \cdot 15 = 18 \cdot 10 = 30 \cdot 6$, а у множителей $15$, $10$, $6$ нет общего делителя, кроме $1$, — значит, меньшего общего кратного нет.

Пример 3. Соотношение Безу для 240 и 46

Алгоритм Евклида: $240 = 5 \cdot 46 + 10$, $46 = 4 \cdot 10 + 6$, $10 = 1 \cdot 6 + 4$, $6 = 1 \cdot 4 + 2$, $4 = 2 \cdot 2$. НОД равен $2$. Теперь идём назад и выражаем двойку через исходные числа, каждый раз подставляя остаток из предыдущей строки:

$$2 = 6 - 4 = 6 - (10 - 6) = 2 \cdot 6 - 10 = 2(46 - 4 \cdot 10) - 10 = 2 \cdot 46 - 9 \cdot 10 = 2 \cdot 46 - 9(240 - 5 \cdot 46) = 47 \cdot 46 - 9 \cdot 240.$$

Получилось $240 \cdot (-9) + 46 \cdot 47 = 2$. Проверка: $-2160 + 2162 = 2$.

Пример 4. Уравнение $84x + 126y = 42$ в целых числах

$\text{НОД}(84, 126) = 42$, и $42$ делится на $42$, поэтому решения есть. Одно видно сразу: $84 \cdot (-1) + 126 \cdot 1 = 42$. Все остальные получаются сдвигом: если к $x$ прибавить $126 : 42 = 3$, а из $y$ вычесть $84 : 42 = 2$, левая часть не изменится. Ответ: $x = -1 + 3k$, $y = 1 - 2k$, $k$ — любое целое. Решатель записывает то же самое, начиная с наименьшего неотрицательного $x$: $x = 2 + 3k$, $y = -1 - 2k$.

А у уравнения $6x + 9y = 7$ решений нет: левая часть при любых целых $x$ и $y$ делится на $\text{НОД}(6, 9) = 3$, а $7$ на $3$ не делится.

Соотношение Безу и уравнения в целых числах

Два целых числа, хотя бы одно из них не ноль.

Целые коэффициенты, их находит обратный ход алгоритма Евклида. Пара не единственная: вместе с $(x, y)$ подходит и $\left(x + \frac{b}{d}k,\ y - \frac{a}{d}k\right)$, где $d = \text{НОД}(a, b)$.

НОД — наименьшее натуральное число, которое можно получить в виде $ax + by$. Всё, что так получается, делится на НОД.

Пример: $1071 \cdot (-3) + 462 \cdot 7 = -3213 + 3234 = 21 = \text{НОД}(1071, 462)$.

Из соотношения Безу сразу следует правило для уравнения $ax + by = c$: оно разрешимо в целых числах ровно тогда, когда $c$ делится на $\text{НОД}(a, b)$. Отсюда и старая задача о кувшинах: кувшинами на $3$ и $5$ литров можно отмерить $4$ литра, потому что $\text{НОД}(3, 5) = 1$, а кувшинами на $4$ и $6$ литров нечётный объём не отмерить никак. Подробнее — в главе о делимости.

Типичные ошибки

Путают НОД и НОК. НОД не больше меньшего из чисел, НОК не меньше большего. Если «НОД» получился больше одного из чисел, что-то не так.
В алгоритме Евклида делят не на то. Следующий шаг — деление прежнего делителя на остаток, а не исходного числа на остаток.
В ответ пишут последнее частное или ноль. НОД — последний ненулевой остаток, то есть делитель в последней строке.
В НОД берут множители в наибольшей степени, в НОК — в наименьшей. Ровно наоборот: общий делитель не может содержать больше двоек, чем есть в каждом из чисел.
Считают НОК как произведение. $a \cdot b$ — общее кратное, но наименьшее только для взаимно простых чисел: $\text{НОК}(4, 6) = 12$, а не $24$.
Для трёх чисел делят произведение на НОД. Эта формула работает только для двух чисел; для трёх считают по цепочке.

Что ещё посмотреть

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