Калькулятор НОД и НОК

НОД и НОК онлайн с подробным решением

Наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) относятся к основам арифметики: их проходят в 6 классе вместе с дробями, а затем встречают в теории чисел вместе с алгоритмом Евклида и соотношением Безу. Калькулятор принимает от 2 до 20 целых чисел и показывает ход решения: последовательные деления, разложение на простые множители, коэффициенты Безу и несократимую дробь.

Умение быстро находить НОД и НОК нужно при сокращении дробей, приведении к общему знаменателю, в задачах «когда они снова встретятся?» и при разрезании прямоугольника на одинаковые квадраты. Школьники, родители, проверяющие домашнее задание, учителя, готовящие решения, и программисты, работающие с циклами, шестерёнками или ключами RSA, получают точный ответ и полное решение для тетради.

1. Введите числа

   В поле «Целые числа (от 2 до 20)» наберите от 2 до 20 чисел через запятую, пробел или точку с запятой либо нажмите на один из примеров.

2. Посмотрите НОД и НОК

   Две карточки обновляются прямо при вводе; кнопка «Копировать» копирует число без разделителей в буфер обмена.

3. Проверьте свойства

   Ниже указано, взаимно простые ли числа (для трёх и более чисел ещё и попарно), а для двух чисел приводятся проверка НОД × НОК = a × b, соотношение Безу и несократимая дробь a/b.

4. Раскройте пояснения

   Блок «Алгоритм Евклида по шагам» показывает каждое деление a = q × b + r, а в блоке «Разложение на простые множители» видны наименьшие и наибольшие показатели степеней.

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

Инструмент использует алгоритм Евклида: большее число делится с остатком на меньшее, a = q × b + r, затем то же повторяется для b и остатка r, поскольку НОД(a; b) = НОД(b; r). Последний ненулевой остаток и есть НОД. НОК находится без разложения: НОК(a; b) = a × b ÷ НОД(a; b).

Для трёх и более чисел вычисления идут по цепочке: НОД(a; b; c) = НОД(НОД(a; b); c), так же и для НОК. Блок разложения показывает второй школьный способ: если a = 2α × 3β × …, то НОД берёт каждый общий простой множитель с наименьшим показателем, а НОК берёт все простые множители с наибольшим показателем.

• a и b: делимое и делитель в каждой строке (сначала большее число).
• q: неполное частное; r: остаток, всегда от 0 до b − 1.
• НОД: наибольшее целое число, на которое делятся все числа; НОК: наименьшее натуральное число, делящееся на каждое из них.
• u и v: коэффициенты Безу, целые числа (возможно, отрицательные), для которых u × a + v × b = НОД(a; b); их даёт расширенный алгоритм Евклида.
• α, β…: показатели степеней в разложении, например 12 = 2² × 3¹.

Примеры нахождения НОД и НОК

Где применяются НОД и НОК

• Дроби: сократить 12/18 до 2/3, разделив на НОД 6, или сложить 5/12 + 7/18 с общим знаменателем 36 = НОК(12; 18): 15/36 + 14/36 = 29/36.
• Циклы и расписания: два автобуса отходят вместе в 8:00, один каждые 12 минут, другой каждые 18; снова вместе они отправятся в 8:36, через НОК = 36 минут.
• Раскрой и плитка: чтобы без обрезков покрыть лист 120 см × 84 см самыми крупными квадратами, берут квадраты со стороной НОД(120; 84) = 12 см, всего 10 × 7 = 70 штук.
• Шестерёнки и ритмы: шестерни с 12 и 18 зубьями возвращаются в исходное положение, когда в зацеплении побывают 36 зубьев, то есть через 3 оборота малой и 2 оборота большой.
• Криптография: в RSA открытая экспонента e должна быть взаимно проста с φ(n), а закрытый ключ d является обратным к e по модулю φ(n) и находится через соотношение Безу. Для e = 17 и φ(n) = 3 120 инструмент выводит (−367) × 17 + 2 × 3 120 = 1, откуда d = −367 + 3 120 = 2 753; действительно, 17 × 2 753 = 15 × 3 120 + 1.

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

• Путать НОД и НОК: НОД никогда не больше наименьшего из чисел, а НОК никогда не меньше наибольшего. «НОД», равный 36, для 12 и 18 заведомо неверен.
• Перемножать числа, чтобы получить НОК: 12 × 18 = 216, а НОК равен 36. Произведение двух чисел совпадает с их НОК, только если они взаимно простые (17 × 31 = 527).
• Применять НОД × НОК = произведение к трём числам: для 8, 12 и 20 получаем 4 × 120 = 480, а 8 × 12 × 20 = 1 920.
• Писать «12,5» или «1 071»: запятая и пробел разделяют список, поэтому прочитаются два числа (12 и 5 или 1 и 71). Вводите целые числа без пробелов между разрядами: 1071.

Все вычисления выполняются локально в вашем браузере в точной целочисленной арифметике (BigInt): ни одно число не отправляется на сервер. Ограничения: от 2 до 20 ненулевых целых чисел длиной до 15 цифр; разложение на простые множители показывается, только если каждый простой множитель удаётся быстро найти (пробное деление до 1 000 000, затем тест простоты).