Что делает этот калькулятор
Инструмент принимает набор из двух или более целых положительных чисел и находит сразу три вещи: полный список делителей каждого числа, общие делители для всех чисел и наибольший общий делитель (НОД). Это пригодится при сокращении дробей, разложении выражений на множители и решении домашних заданий по теории чисел. В русскоязычной литературе используется аббревиатура НОД, тогда как в английских источниках вы встретите обозначения GCF (greatest common factor) и GCD (greatest common divisor) — это одно и то же.
Как пользоваться
Введите целые числа через запятую, например 136, 64, 24, 16, и сразу получите результат. Для каждого числа делители выводятся по возрастанию, затем показываются общие делители и единственное значение НОД. Используйте только целые положительные числа: ноль, отрицательные значения и дроби в качестве делителей не подходят.
Как это считается
Целое число d является делителем числа n, если \(n \bmod d = 0\) (то есть деление выполняется без остатка). Чтобы быстро найти все делители, мы перебираем i от 1 до квадратного корня из n: как только i делит n, делителями сразу являются и i, и \(n/i\). НОД для списка вычисляется попарно по алгоритму Евклида: пока b не равно нулю, заменяем пару (a, b) на (b, a mod b); оставшееся значение a и есть НОД. Формально:
$$\gcd(a, 0) = a, \quad \gcd(a, b) = \gcd(b, \; a \bmod b)$$
Полезный факт: общие делители всего набора — это в точности делители самого НОД:
$$\text{CommonFactors} = \{\, d : g \bmod d = 0 \,\}, \quad g = \gcd(n_1, n_2, \dots)$$
Разбор примера
Возьмём числа 136, 64, 24, 16. Делители 16: 1, 2, 4, 8, 16; делители 24: 1, 2, 3, 4, 6, 8, 12, 24; делители 64: 1, 2, 4, 8, 16, 32, 64; делители 136: 1, 2, 4, 8, 17, 34, 68, 136. По алгоритму Евклида: \(\gcd(16, 24) = 8\), затем \(\gcd(8, 64) = 8\), затем \(\gcd(8, 136) = 8\) — значит, НОД = 8. Делители числа 8: 1, 2, 4, 8 — это и есть общие делители всего набора.
Частые вопросы
НОД и GCD — это одно и то же? Да. Наибольший общий делитель (НОД), greatest common factor (GCF) и greatest common divisor (GCD) — это разные названия одной и той же величины.
А если у чисел нет общих делителей? У любого набора целых положительных чисел есть общий делитель 1, поэтому множество общих делителей всегда содержит как минимум \(\{1\}\), а НОД не меньше 1. Числа, у которых единственный общий делитель — это 1, называют взаимно простыми.
Можно ввести только одно число? Да — тогда выводятся его делители, а НОД равен самому этому числу.
Результаты НОД для разных типов наборов чисел
Наибольший общий делитель (НОД) зависит от того, как числа связаны друг с другом. В таблице показано несколько типичных случаев. Общие делители любого набора — это в точности делители его НОД.
| Числа | НОД | Общие делители | Тип связи |
|---|---|---|---|
| 8 и 15 | 1 | 1 | Взаимно простые (нет общего делителя, кроме 1) |
| 12 и 36 | 12 | 1, 2, 3, 4, 6, 12 | Кратность (36 кратно 12) |
| 18, 24, 30 | 6 | 1, 2, 3, 6 | Три числа с общим делителем |
| 17 и 31 | 1 | 1 | Два разных простых числа (всегда взаимно простые) |
| 20 и 20 | 20 | 1, 2, 4, 5, 10, 20 | Одинаковые числа (НОД равен самому числу) |
| 48 и 180 | 12 | 1, 2, 3, 4, 6, 12 | Частичное совпадение простых множителей |
Проверка для 48 и 180: \(48 = 2^4 \cdot 3\) и \(180 = 2^2 \cdot 3^2 \cdot 5\). Берём наименьшую степень каждого общего простого числа: \(2^2 \cdot 3 = 12\).
Что говорит НОД и где он применяется
- НОД = 1 означает взаимную простоту. Числа не имеют общего простого делителя. Сами они не обязаны быть простыми: 8 и 15 взаимно просты, хотя ни одно из них не является простым.
- НОД равен наименьшему числу. Это наименьшее число делит все остальные. Например, \(\gcd(12, 36) = 12\).
- Сокращение дробей. Деление числителя и знаменателя на их НОД приводит дробь к несократимому виду за один шаг. Так как \(\gcd(24, 36) = 12\), получаем \(\frac{24}{36} = \frac{24 \div 12}{36 \div 12} = \frac{2}{3}\).
- Наибольшие равные группы. Если у вас 24 ручки и 36 карандашей и вы хотите составить одинаковые группы, используя все предметы, наибольшее число групп — \(\gcd(24, 36) = 12\). В каждой группе 2 ручки и 3 карандаша.
- Квадратные плитки. Наибольшая квадратная плитка, которая точно укладывается на участок 48 см на 180 см без резки, имеет сторону \(\gcd(48, 180) = 12\) см. Это 4 плитки в одну сторону и 15 в другую.
- Связь с НОК. Для двух натуральных чисел \(\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b\). Пример: \(\gcd(12, 18) = 6\) и \(\operatorname{lcm}(12, 18) = 36\), поэтому \(6 \cdot 36 = 216 = 12 \cdot 18\). Это тождество справедливо только для двух чисел, но не для трёх и более.
Ключевые термины: делитель, общий делитель, НОД, взаимно простые
- Делитель (фактор)
- Натуральное число, которое делит данное число без остатка. Делители 12: 1, 2, 3, 4, 6 и 12.
- Кратное
- Произведение числа и любого целого числа. Кратные 4 включают 4, 8, 12 и 16. Если \(d\) — делитель \(n\), то \(n\) кратно \(d\).
- Общий делитель
- Число, которое является делителем каждого числа в наборе. Для 12 и 18 общие делители: 1, 2, 3 и 6.
- НОД (GCF / GCD / HCF)
- Наибольший общий делитель, он же наибольший общий фактор. Это наибольший из общих делителей. Все три обозначения означают одно и то же.
- Взаимно простые (относительно простые)
- Числа, единственный общий делитель которых — 1, поэтому их НОД равен 1.
- Простое число
- Целое число больше 1, единственные натуральные делители которого — 1 и оно само, например 2, 3, 5, 7, 11, 17 и 31.
- Алгоритм Евклида
- Метод, который многократно заменяет пару \((a, b)\) на \((b,\; a \bmod b)\), пока остаток не станет равен 0. Последнее ненулевое значение и есть НОД. Пример: \(\gcd(180, 48)\): \(180 = 3 \cdot 48 + 36\), затем \(48 = 1 \cdot 36 + 12\), затем \(36 = 3 \cdot 12 + 0\), значит НОД равен 12. Для более чем двух чисел применяйте его поэтапно: \(\gcd(\gcd(n_1, n_2), n_3)\).