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

Зачем это нужно

Все натуральные числа «собраны» из особых чисел-кирпичиков — простых. Как любое вещество состоит из атомов, так любое число больше 1 раскладывается в произведение простых чисел, причём единственным образом. Зная это разложение, легко найти все делители числа, НОД и НОК, сократить дробь.

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

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

• Натуральное число называют простым, если у него ровно два делителя: 1 и само число. Например: 2, 3, 5, 7, 11, 13.
• Число называют составным, если у него больше двух делителей. Например, $12$: делители 1, 2, 3, 4, 6, 12.
• Число 1 — ни простое, ни составное: у него только один делитель.

Единственное чётное простое число — 2. Все остальные чётные числа делятся на 2 и поэтому составные.

Решето Эратосфена

Как найти все простые числа до 100? Древнегреческий учёный Эратосфен (III век до н. э.) придумал способ — решето:

1. Выпишите числа от 2 до 100.
2. Обведите 2 — оно простое — и вычеркните все кратные 2: 4, 6, 8, …
3. Первое невычеркнутое число — 3. Обведите его и вычеркните все кратные 3.
4. Следующее невычеркнутое — 5, затем 7. Повторите.
5. После 7 можно остановиться: $11 \cdot 11 = 121 > 100$, так что все составные числа до 100 уже вычеркнуты. Все оставшиеся числа — простые.

Простых чисел до 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.

Первые из них — до 30 — полезно помнить наизусть.

Как проверить, простое ли число

Чтобы проверить, простое ли число $n$, достаточно попробовать разделить его на простые числа 2, 3, 5, 7, 11, …, квадрат которых не больше $n$. Если ни на одно не делится — число простое.

Пример. 97: $10^2 = 100 > 97$, значит, проверяем 2, 3, 5, 7. Не делится ни на одно (последняя цифра 7; сумма цифр 16; $97 : 7 = 13$ (ост. 6)). Значит, 97 — простое.

Почему этого достаточно? Если $n = a \cdot b$ и оба множителя больше $\sqrt{n}$, то их произведение было бы больше $n$. Значит, хотя бы один множитель не больше $\sqrt{n}$ — его мы бы нашли.

Разложение на простые множители

Любое составное число можно разложить в произведение простых множителей, и такое разложение единственно (если не обращать внимания на порядок множителей). Это основная теорема арифметики.

Как раскладывать: «столбиком»

Делим число на наименьший простой делитель, затем частное — снова на наименьший простой делитель, и так до единицы.

Разобранный пример 1

Разложите на простые множители число 360.

$360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^3 \cdot 3^2 \cdot 5.$

Проверка: $8 \cdot 9 \cdot 5 = 72 \cdot 5 = 360$. Верно.

Повторяющиеся множители удобно записывать степенью.

Разобранный пример 2

Найдите все делители числа 36 с помощью разложения.

1. $36 = 2^2 \cdot 3^2$.
2. Любой делитель — это $2^a \cdot 3^b$, где $a$ может быть 0, 1 или 2, и $b$ — 0, 1 или 2.
3. Вариантов $3 \cdot 3 = 9$: 1, 2, 4, 3, 6, 12, 9, 18, 36.

Ответ: 9 делителей: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Немного удивительного

• Простых чисел бесконечно много. Это доказал Евклид около 2 300 лет назад.
• Простые числа-близнецы отличаются на 2: (3; 5), (11; 13), (41; 43). Бесконечно ли их много — до сих пор не доказано.
• Гипотеза Гольдбаха: любое чётное число больше 2 — сумма двух простых ($10 = 3 + 7$, $28 = 11 + 17$). Её проверили на компьютерах для огромных чисел, но доказать пока никто не смог.

Типичные ошибки

• Считать 1 простым числом. У простого числа ровно два делителя.
• Считать все нечётные числа простыми: 9, 15, 21, 27 — составные.
• Оставлять в разложении составные множители: $360 = 4 \cdot 9 \cdot 10$ — это не разложение на простые.
• Пропускать повторяющиеся множители: $360 = 2 \cdot 3 \cdot 5$ — неверно.
• Проверять, простое ли число, делением только на 2 и 3.

Что дальше

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