Наибольший общий делитель трёх чисел

Что такое НОД трёх чисел

Наибольший общий делитель трёх чисел — это наибольшее натуральное число, на которое все три делятся без остатка. В англоязычных учебниках он же зовётся GCD, GCF или HCF — величина одна и та же. Он существует всегда, потому что на единицу делится что угодно, и никогда не бывает больше наименьшего из трёх чисел.

Откуда берётся формула

Любое целое число больше единицы единственным образом раскладывается в произведение простых, и d делит a ровно тогда, когда каждый простой множитель числа d входит в a не меньше раз. Чтобы делить все три числа сразу, d может содержать каждый простой множитель лишь столько раз, сколько его содержит самое бедное из трёх, — а если взять именно столько, получится наибольший такой делитель.

Множитель, которого нет хотя бы у одного числа, выпадает из произведения целиком — поэтому добавление третьего числа может ответ только уменьшить, но никогда не увеличить.

Как считать: три шага

1. Разложите все три числа на простые множители, например 12 = 2² × 3, 18 = 2 × 3² и 30 = 2 × 3 × 5.
2. Оставьте только те простые множители, которые есть во всех трёх разложениях, взяв каждый наименьшее число раз: одну двойку и одну тройку.
3. Перемножьте оставшееся: 2 × 3 = 6. Это и есть наибольший общий делитель.

Разложение против алгоритма Евклида: разбор на одном примере

К одному и тому же ответу ведут два пути, и их стоит увидеть рядом на числах 12, 18 и 30. Первый раскладывает степени простых в таблицу и читает минимум каждой строки:

Пятёрка не даёт ничего: её нет у двух чисел из трёх, значит ни один общий делитель нести её не может. Второй путь не раскладывает ничего. Он опирается на ассоциативность — НОД(a, b, c) = НОД(НОД(a, b), c) — и дважды применяет алгоритм Евклида:

Евклид описал эту процедуру в «Началах» около 300 года до нашей эры, и именно она делает попарный ход выигрышным на больших числах: он только делит с остатком и раскладывать ничего не обязан. Зато таблица показывает, почему ответ именно такой, — а от школьного решения обычно требуется как раз это.

Ходовые тройки и их НОД

Где три числа встречаются на практике

• Сокращение отношения трёх величин — 12 : 18 : 24, делённое на НОД 6, превращается в 2 : 3 : 4
• Раскрой без отходов — доски 12 м, 18 м и 30 м режутся на равные куски без остатка только при длине, делящей 6 м
• Раскладка по одинаковым коробкам — 12, 18 и 30 предметов трёх видов заполняют не больше 6 одинаковых коробок без остатка
• Замощение прямоугольника — наибольшая квадратная плитка, укладывающаяся в три стороны без подрезки, и есть их наибольший общий делитель
• Пересчёт рецепта — 12 г, 18 г и 30 г, поделённые на 6, сохраняют пропорции нетронутыми
• Школьные задачи — «наибольшее число, на которое делятся 12, 18 и 30» — это дословно данное вычисление

Границы применимости и оговорки

• Порядок чисел не важен. НОД(12, 18, 24), НОД(24, 12, 18) и НОД(18, 24, 12) — одно и то же число 6, поэтому у калькулятора одна страница на неупорядоченную тройку.
• Ответ никогда не больше наименьшего из чисел, а равен ему ровно тогда, когда это число делит два других: НОД(6, 12, 18) = 6.
• Единица среди трёх чисел делает ответ единицей, потому что ничто больше единицы единицу не делит.
• Попарная взаимная простота — не то же самое, что взаимная простота в совокупности. У 6, 10 и 15 НОД равен 1, хотя каждая пара общий множитель имеет, — то есть «НОД равен 1» не значит, что числа не имеют ничего общего попарно.
• НОД делит любую разность. Для 12, 18 и 30 он делит 18 − 12 = 6 и 30 − 18 = 12 — быстрый способ проверить ответ вручную.