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

Простое число имеет ровно два делителя — единицу и само себя: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … Число 1 не считается ни простым, ни составным. Единственное чётное простое число — 2. Составное число имеет больше двух делителей: 4, 6, 8, 9, 10, 12, …

Любое составное число единственным образом раскладывается на простые множители (это утверждение называют основной теоремой арифметики): \(360 = 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5 = 2^3\cdot 3^2\cdot 5\). Раскладывать удобно «столбиком»: делим на наименьшее простое число, пока это возможно, затем на следующее.

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

Пример. Найдите НОД и НОК чисел 36 и 60.
Решение. \(36 = 2^2\cdot 3^2\), \(60 = 2^2\cdot 3\cdot 5\). НОД \(= 2^2\cdot 3 = 12\), НОК \(= 2^2\cdot 3^2\cdot 5 = 180\). Проверка: \(36\cdot 60 = 2160 = 12\cdot 180\) — произведение чисел всегда равно произведению их НОД и НОК.

Где это нужно: общий знаменатель дробей — это НОК знаменателей, а сокращают дробь делением числителя и знаменателя на их НОД.