Тапсырмалар № 25, 26 · ЕГЭ

Наибольший общий делитель

Определение и алгоритм Евклида

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

Наибольший общий делитель (НОД) двух чисел — это самое большое натуральное число, на которое делятся оба числа без остатка. Быстро находить НОД позволяет алгоритм Евклида, основанный на последовательной замене пары чисел остатком от деления.

Наибольший общий делитель чисел \(a\) и \(b\), обозначаемый \(\operatorname{НОД}(a,b)\) немесе \(\gcd(a,b)\), — наибольшее положительное целое число \(d\), такое что \(a\) и \(b\) делятся на \(d\) без остатка. Для целых чисел, не равных одновременно нулю, выполняется \(\gcd(0,a)=|a|\).

Формула и алгоритм Евклида

Если \(a=bq+r\), где \(r\) — остаток от деления \(a\) на \(b\), то общий делитель чисел \(a\) и \(b\) одновременно является общим делителем \(b\) и \(r\). Поэтому НОД не изменяется при замене пары \((a,b)\) на \((b,r)\):

\[\gcd(a,b)=\gcd(b,a\bmod b),\quad b\ne 0\]

Вычисления повторяют, пока остаток не станет равен нулю. Последний ненулевой остаток и есть НОД. Перед применением алгоритма отрицательные числа можно заменить их модулями.

№

Пример

Найдём \(\gcd(252,105)\): \(252=105\cdot2+42\); \(105=42\cdot2+21\); \(42=21\cdot2+0\). Последний ненулевой остаток равен \(21\), поэтому \(\gcd(252,105)=21\).

Не путайте с НОК

НОД показывает наибольший общий делитель, а наименьшее общее кратное — наименьшее положительное число, кратное обоим исходным числам. Для положительных \(a\) и \(b\) их связь выражается формулой \(\gcd(a,b)\cdot\operatorname{НОК}(a,b)=a\cdot b\).

Проверка

Чему равен \(\gcd(48,18)\)?

Главное за минуту

Главное

НОД — наибольшее положительное число, делящее оба исходных числа без остатка.
Алгоритм Евклида заменяет пару \((a,b)\) на \((b,a\bmod b)\) до появления нулевого остатка.
Последний ненулевой остаток является НОД; понятие опирается на делимость чисел и изучается в рамках основ теории чисел.