Простые числа, НОД и НОК

Простое число имеет ровно два натуральных делителя: 1 и само себя (2, 3, 5, 7, 11, 13, …). Число 1 не простое и не составное. Основная теорема арифметики: каждое натуральное число, большее 1, единственным образом (с точностью до порядка) раскладывается в произведение простых множителей.

Через разложение находят НОД — произведение общих простых множителей в наименьших степенях — и НОК — произведение всех множителей в наибольших степенях. Для любых натуральных \(a\) и \(b\)

\[\text{НОД}(a, b) \cdot \text{НОК}(a, b) = ab.\]

Пример. Найдите НОД и НОК чисел 84 и 90.
Решение. \(84 = 2^2 \cdot 3 \cdot 7\), \(90 = 2 \cdot 3^2 \cdot 5\). НОД \(= 2 \cdot 3 = 6\), НОК \(= 2^2 \cdot 3^2 \cdot 5 \cdot 7 = 1260\). Проверка: \(6 \cdot 1260 = 7560 = 84 \cdot 90\).

Когда числа большие, разложение ищут долго. Алгоритм Евклида находит НОД делением с остатком: \(\text{НОД}(a, b) = \text{НОД}(b, r)\), где \(r\) — остаток от деления \(a\) на \(b\).

Пример. \(\text{НОД}(1071, 462)\): \(1071 = 462 \cdot 2 + 147\); \(462 = 147 \cdot 3 + 21\); \(147 = 21 \cdot 7\). Последний ненулевой остаток — 21, это и есть НОД.

Число делителей: если \(n = p_1^{k_1} p_2^{k_2} \cdots\), то делителей у \(n\) ровно \((k_1 + 1)(k_2 + 1)\cdots\). У \(360 = 2^3 \cdot 3^2 \cdot 5\) их \(4 \cdot 3 \cdot 2 = 24\).