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

У каждого натурального числа свой список делителей, и у двух чисел эти списки часто пересекаются. Выпишем делители числа 24: 1, 2, 3, 4, 6, 8, 12, 24. Теперь делители числа 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. В обоих списках стоят 1, 2, 3, 4, 6 и 12 — такие числа называют общими делителями чисел 24 и 36. Самое крупное из них — 12 (рис. 1).

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

Записывают его коротко: НОД (24; 36) = 12. В общем виде для чисел a и b пишут НОД (a; b). Так же нетрудно проверить, что НОД (8; 20) = 4, НОД (14; 35) = 7, а НОД (9; 16) = 1.

Вернись к рис. 1: общие делители 1, 2, 3, 4, 6, 12 — это в точности все делители числа 12. Так бывает всегда.

Свойство. Всякий общий делитель двух чисел делит нацело и их НОД. Поэтому, найдя НОД, ты знаешь и все остальные общие делители: это его делители.

Выписывать все делители удобно, пока числа маленькие: у трёхзначного числа список длинный и легко ошибиться. Быстрее другой путь — разложить оба числа на простые множители и найти общую часть.

Пример 1. Найдём НОД (84; 126).

Решение. Разложим оба числа: 84 = 2 · 2 · 3 · 7 126 = 2 · 3 · 3 · 7 Двойка есть в обеих строках, но во второй она одна — в общую часть она идёт один раз. С тройкой то же самое: у 84 она единственная. Семёрка есть и там, и там. Выходит, оба числа делятся нацело на 2, на 3 и на 7, а значит, и на произведение 2 · 3 · 7 = 42. Больше брать нечего (рис.