Сначала изучите: Признаки делимости, НОД и НОК
Простые числа — «атомы» натуральных чисел: любое число единственным образом собирается из них как произведение. Число делителей, сумма делителей, НОД и НОК — всё начинается с разложения на простые множители. Простые числа лежат и в основе современного шифрования (например, защищённых соединений в интернете): там используется то, что разложить большое число на простые множители очень трудно. В этом уроке разобраны определения, проверка на простоту, основная теорема арифметики, формулы для делителей и типичные задачи олимпиадного стиля.
До 100 ровно 25 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Почему 1 не считают простым? Иначе разложение на множители не было бы единственным: 6 = 2·3 = 1·2·3 = 1·1·2·3. Определение выбрано именно так, чтобы работала основная теорема.
Простые числа, кроме 2 и 5, оканчиваются цифрами 1, 3, 7, 9; любое простое число больше 3 имеет вид 6k ± 1 (числа 6k, 6k ± 2, 6k + 3 делятся на 2 или на 3).
Чтобы проверить, простое ли n, достаточно делить его на простые числа, не превосходящие √n. Причина: если n = a·b и a ≤ b, то a · a ≤ a · b = n, то есть a ≤ √n. Значит, у составного числа обязательно есть делитель, не превосходящий √n.
Решето Эратосфена: выписываем числа от 2 до n и последовательно вычёркиваем кратные 2, 3, 5 (кроме самих этих чисел); оставшиеся — простые. Можно остановиться, дойдя до простого числа больше √n: все невычеркнутые числа простые.
Признаки делимости ускоряют проверку: на 2 — последняя цифра чётная; на 3 — сумма цифр делится на 3; на 5 — последняя цифра 0 или 5; на 11 — разность сумм цифр, взятых через одну, делится на 11.
Простое ли число 221?
Каждое натуральное число больше 1 раскладывается на простые множители единственным образом (с точностью до порядка):
n = p₁^a₁ · p₂^a₂ · … · p_k^a_k
Способ разложения: последовательно делим число на его наименьший простой делитель.
360 = 2·180 = 2·2·90 = 2·2·2·45 = 2³·3²·5.
Простых чисел бесконечно много (Евклид). Пусть их конечное число: p₁, p₂, …, p_k. Рассмотрим N = p₁p₂…p_k + 1. Оно не делится ни на одно pᵢ (остаток 1). Но у N > 1 есть какой-то простой делитель — значит, существует простое число, которого нет в списке. Противоречие.
Внимание: само N не обязано быть простым: 2·3·5·7·11·13 + 1 = 30031 = 59·509. Доказательство показывает лишь существование простого делителя вне списка.
Число делителей: τ(n) = (a₁ + 1)(a₂ + 1)…(a_k + 1)
Сумма делителей: σ(n) = (1 + p₁ + … + p₁^a₁)(1 + p₂ + … + p₂^a₂)…
Почему? Каждый делитель имеет вид p₁^b₁·p₂^b₂…, где b₁ можно выбрать из 0, 1, …, a₁ — a₁ + 1 вариант; выборы независимы, поэтому перемножаются. Если раскрыть скобки в формуле суммы, каждый делитель появится ровно один раз.
Сколько натуральных делителей у 360 и сколько из них нечётных?
Раскладываем оба числа на простые множители:
НОД — произведение общих простых множителей в наименьших степенях
НОК — произведение всех встречающихся простых множителей в наибольших степенях
НОД(a, b) · НОК(a, b) = a · b
Последняя формула следует из того, что для каждого простого min + max равно сумме двух показателей.
Найдите НОД и НОК чисел 360 и 84.
a и b взаимно просты, если у них нет общих простых множителей (НОД = 1). Два соседних натуральных числа всегда взаимно просты: их общий делитель должен делить и разность, то есть 1.
Простые числа-близнецы: отличаются на 2: (3, 5), (5, 7), (11, 13), …. Единственная тройка, где простые все три числа p, p + 2, p + 4, — это 3, 5, 7 (из трёх последовательных нечётных чисел одно обязательно делится на 3).
Типичная идея: проверять простое число по остаткам от деления на 3 (или на 2, 4, 6).
p и p² + 2 — оба простые. Найдите p.