Историческая справка

Простые числа изучаются с древних времен. Древнегреческий математик Евклид (III век до н.э.) доказал, что простых чисел бесконечно много. В его работе «Начала» содержится доказательство этого факта, а также основы теории делимости.

Основная теорема арифметики была впервые четко сформулирована и доказана Карлом Фридрихом Гауссом в его работе «Арифметические исследования» (1801 г.), хотя отдельные случаи были известны еще Евклиду.

Простые и составные числа

Простое число — натуральное число, большее 1, которое делится только на 1 и на само себя.

Составное число — натуральное число, большее 1, которое имеет делители, отличные от 1 и самого себя.

Число 1 не является ни простым, ни составным — это единица.

Примеры:

Простые числа: $2, 3, 5, 7, 11, 13, 17, 19, \ldots$

Составные числа: $4, 6, 8, 9, 10, 12, 14, 15, \ldots$

Основная теорема арифметики

Любое натуральное число $n > 1$ можно представить в виде произведения простых чисел, причем это представление единственно с точностью до порядка множителей.

$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$

где $p_1, p_2, \ldots, p_k$ — различные простые числа, $\alpha_1, \alpha_2, \ldots, \alpha_k$ — натуральные числа.

Такое представление называется каноническим разложением числа на простые множители.

Примеры:

$60 = 2^2 \cdot 3 \cdot 5$

$100 = 2^2 \cdot 5^2$

$210 = 2 \cdot 3 \cdot 5 \cdot 7$

Формулы для делителей

Если $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$ — каноническое разложение числа $n$, то:

Количество натуральных делителей

$d(n) = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$

Сумма натуральных делителей

$\sigma(n) = \frac{p_1^{\alpha_1+1} — 1}{p_1 — 1} \cdot \frac{p_2^{\alpha_2+1} — 1}{p_2 — 1} \cdots \frac{p_k^{\alpha_k+1} — 1}{p_k — 1}$

Произведение натуральных делителей

$P(n) = n^{d(n)/2}$

Пример для $n = 60$:

$60 = 2^2 \cdot 3^1 \cdot 5^1$

Количество делителей: $d(60) = (2+1)(1+1)(1+1) = 3 \cdot 2 \cdot 2 = 12$

Сумма делителей: $\sigma(60) = \frac{2^3-1}{2-1} \cdot \frac{3^2-1}{3-1} \cdot \frac{5^2-1}{5-1} = 7 \cdot 4 \cdot 6 = 168$

Произведение делителей: $P(60) = 60^{12/2} = 60^6$

Таблица простых чисел до 100

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
Начинаем с наименьшего простого числа 2.
2
Делим исходное число на 2, пока оно делится нацело. Каждое успешное деление дает множитель 2.
3
Переходим к следующему простому числу (3) и повторяем процесс.
4
Продолжаем с возрастающими простыми числами, пока частное не станет равно 1.
5
Если на каком-то шаге квадрат текущего простого числа больше оставшегося числа, то оставшееся число простое.

Пример: разложим число 84

$84 \div 2 = 42$ → множитель $2$

$42 \div 2 = 21$ → множитель $2$

$21 \div 3 = 7$ → множитель $3$

$7 \div 7 = 1$ → множитель $7$

Результат: $84 = 2^2 \cdot 3 \cdot 7$

Попробуйте сами:

Задачи на количество делителей
1. Найдите количество делителей числа: а) 2024; б) 2025; в) 1 000 000 000. («Физтех», 2014, 7–8)

Решение:

а) $2024 = 2^3 \cdot 11 \cdot 23$, количество делителей: $(3+1)(1+1)(1+1) = 4\cdot2\cdot2 = 16$

б) $2025 = 3^4 \cdot 5^2$, количество делителей: $(4+1)(2+1) = 5\cdot3 = 15$

в) $10^9 = (2\cdot5)^9 = 2^9 \cdot 5^9$, количество делителей: $(9+1)(9+1) = 100$

Проверьте свои знания:

Совет: Для быстрого подсчета используйте формулу $d(n) = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$

Задачи на сумму делителей
1. Натуральное число a раскладывается в произведение трех различных простых делителей. Сумма всех его делителей равна 72. Найти число a. («Росатом», 2019, 9.2)

Решение:

Пусть $a = pqr$, где $p, q, r$ — различные простые.

Сумма делителей: $\sigma(a) = (1+p)(1+q)(1+r) = 72$

Подходит вариант: $(1+2)(1+3)(1+5) = 3\cdot4\cdot6 = 72$

Ответ: $a = 2\cdot3\cdot5 = 30$

Попробуйте решить:

Напоминание: $\sigma(n) = \frac{p_1^{\alpha_1+1} — 1}{p_1 — 1} \cdot \frac{p_2^{\alpha_2+1} — 1}{p_2 — 1} \cdots \frac{p_k^{\alpha_k+1} — 1}{p_k — 1}$

Задачи на произведение делителей
1. Найти все натуральные числа n от 1 до 100 такие, что если перемножить все делители числа n (включая 1 и n), получим число $n^3$. («Высшая проба», 2017, 7.3)

Решение:

Произведение всех делителей: $n^{d(n)/2} = n^3 \Rightarrow d(n) = 6$

Числа с 6 делителями: $p^5$ или $p^2 q$

Ответ: $12, 18, 20, 28, 32, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, 99$

Проверьте понимание:

Формула: $P(n) = n^{d(n)/2}$, где $d(n)$ — количество делителей числа $n$