Любые натуральные числа имеют общий делитель 1, а некоторые — и другие общие делители. Например, у 18 и 30 общие делители 1, 2, 3 и 6. Самый большой из них, 6, называют наибольшим общим делителем чисел 18 и 30 и пишут: НОД(18, 30) = 6.
НОД можно найти перебором делителей меньшего числа или делителей разности чисел. Для больших чисел удобнее разложение на простые множители. Найдём НОД(1980, 2772):
1980 = 2 · 2 · 3 · 3 · 5 · 11, 2772 = 2 · 2 · 3 · 3 · 7 · 11.
Оба числа делятся на произведение общих множителей 2 · 2 · 3 · 3 · 11 = 396, а на большее общее число — нет: оставшиеся множители 5 и 7 разные. Значит, НОД(1980, 2772) = 396.
Алгоритм нахождения НОД: 1) разложить числа на простые множители; 2) выписать произведение всех общих простых множителей (каждый — столько раз, сколько он входит во все разложения); 3) вычислить это произведение.
Пример 1. 84 = 2 · 2 · 3 · 7, 126 = 2 · 3 · 3 · 7, 210 = 2 · 3 · 5 · 7; НОД(84, 126, 210) = 2 · 3 · 7 = 42.
Пример 2. 36 = 2 · 2 · 3 · 3 и 540 = 2 · 2 · 3 · 3 · 3 · 5: все множители 36 входят в разложение 540, то есть 540 делится на 36. Тогда НОД(36, 540) = 36.