Наибольший общий делитель (НОД) — это самое большое число, на которое делятся без остатка все числа набора. Калькулятор быстро находит НОД двух или трёх чисел по алгоритму Евклида и подходит для проверки домашних заданий и олимпиадных задач.
Делитель — число, на которое данное число делится без остатка. Например, делители числа 12: 1, 2, 3, 4, 6 и 12. Общий делитель — число, которое делит сразу все числа набора: у 12 и 18 это 1, 2, 3 и 6. Наибольший общий делитель — самый большой из общих, поэтому НОД(12, 18) = 6.
НОД нужен при сокращении дробей, разложении на множители и решении задач на равные группы. Два числа, у которых НОД равен 1, называют взаимно простыми.
Идея проста: НОД двух чисел не меняется, если большее число заменить остатком от деления на меньшее. Остаток считают как a − b × floor(a / b). Деление повторяют, пока остаток не станет нулём; тогда делитель и есть НОД.
Пример 1. НОД(48, 36): 48 − 36 = 12, далее НОД(36, 12) = 12, потому что 36 делится на 12 нацело. Ответ: 12.
Пример 2. НОД(240, 156): 240 − 156 = 84; 156 − 84 = 72; 84 − 72 = 12; 72 делится на 12. Ответ: 12.
Для набора чисел алгоритм применяют последовательно: сначала находят НОД первых двух, затем НОД результата и третьего числа. Порядок чисел на результат не влияет.
Пример 3. НОД(12, 18, 24): НОД(12, 18) = 6, затем НОД(6, 24) = 6. Ответ: 6.
НОД для часто встречающихся пар чисел
| Пара чисел | Общие делители | НОД |
|---|---|---|
| 12 и 18 | 1, 2, 3, 6 | 6 |
| 48 и 36 | 1, 2, 3, 4, 6, 12 | 12 |
| 17 и 5 | 1 | 1 |
| 240 и 156 | 1, 2, 3, 4, 6, 12 | 12 |
Да. Раскладывают каждое число на простые множители, выбирают общие и перемножают их. Алгоритм Евклида просто быстрее, поэтому для больших чисел удобнее он.
Это числа, у которых наибольший общий делитель равен единице. Например, 17 и 5 взаимно просты, потому что не имеют общих делителей кроме 1.
Если большее число делится на меньшее без остатка, НОД равен меньшему числу. Например, НОД(36, 12) = 12.
На НОД делят числитель и знаменатель, чтобы сократить дробь до несократимого вида. Чем больше НОД, тем короче получается запись.