Простые числа
2, 3, 5, 7, 11… — «атомы» арифметики, решето Эратосфена и число из 41 миллиона цифр
Простое число делится без остатка только на единицу и на само себя: 2, 3, 5, 7, 11, 13… Любое другое натуральное число больше единицы можно разложить на простые множители, и только одним способом, — поэтому простые числа называют «атомами» арифметики. Ещё Евклид около 300 года до н. э. доказал, что простых чисел бесконечно много. Найти их помогает решето Эратосфена — способ, который придумали больше двух тысяч лет назад. Самое большое известное простое число найдено в 2024 году: в нём 41 024 320 цифр. А на свойствах простых чисел держится шифрование в интернете.
Что такое простое число
Число называется простым, если у него ровно два делителя: единица и оно само. Например, 7 делится только на 1 и на 7. А 6 — составное: оно делится ещё на 2 и на 3[1].
Начало ряда простых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47…
2 — единственное чётное простое число: все остальные чётные числа делятся на 2. По той же причине простые числа больше 5 оканчиваются только на 1, 3, 7 или 9[2].
Единица — не простое и не составное. У неё только один делитель[1].
«Атомы» арифметики
Любое натуральное число больше единицы — либо простое, либо его можно записать как произведение простых:
12 = 2 · 2 · 3, 30 = 2 · 3 · 5, 1001 = 7 · 11 · 13.
Важно, что такое разложение единственное — с точностью до порядка множителей. Это основная теорема арифметики. Как молекулы складываются из атомов, так и все числа складываются из простых[1].
Если бы единица считалась простой, разложение перестало бы быть единственным: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3 — и так без конца. Поэтому единицу к простым не относят[1]. Хотя так было не всегда: в XVII веке некоторые математики считали её первым простым числом, а в XVIII веке Гольдбах в переписке с Эйлером ещё включал её в список простых[2].
Решето Эратосфена
Как найти все простые числа, скажем, до 100? Древнегреческий учёный Эратосфен Киренский придумал способ, который работает и сегодня[3]:
- Выпишите подряд числа от 2 до 100.
- 2 — простое. Зачеркните все числа, кратные 2: 4, 6, 8…
- Следующее незачёркнутое — 3. Оно простое; зачеркните все кратные 3.
- Следующее — 5, потом 7. Каждый раз зачёркивайте кратные.
- Всё, что осталось незачёркнутым, — простые числа.
Хватит дойти до 7: следующее простое, 11, в квадрате даёт уже 121 — больше 100, и все составные числа к этому времени зачёркнуты[3].
Во времена Эратосфена писали на дощечках, покрытых воском. Составные числа не зачёркивали, а прокалывали — и дощечка становилась похожа на решето, через которое «просеивались» составные числа, а простые оставались [3].
Простых чисел бесконечно много
Около 300 года до н. э. Евклид в «Началах» доказал, что простых чисел бесконечно много[1] [2]. Идея доказательства понятна даже без формул:
Предположим, что простых чисел конечное число. Перемножим их все и прибавим единицу. Новое число не делится ни на одно из них — от деления всегда остаётся остаток 1. Значит, у него есть какой-то другой простой делитель, которого нет в нашем «полном» списке. Получили противоречие: список не может быть полным.
Самое большое известное простое
Самого большого простого числа нет, а вот самое большое известное есть. На октябрь 2026 года это 2^136 279 841 − 1 — в десятичной записи у него 41 024 320 цифр. Его нашли 12 октября 2024 года участники проекта GIMPS — добровольцы, которые отдают мощность своих компьютеров на поиск простых чисел [4].
Числа вида 2ⁿ − 1 называют числами Мерсенне — в честь французского монаха Марена Мерсенна. Их удобно проверять на простоту, поэтому все последние рекорды — именно такие числа[4][1].
Простые числа и шифрование
Долго считалось, что простые числа нужны только чистой математике. Всё изменилось в 1970-х, когда появилось шифрование с открытым ключом: первые такие системы построены на простых числах[1][2]. Перемножить два больших простых числа легко, а вот разложить результат обратно на множители — очень трудно: быстрых способов для этого не известно[1].
Иногда пишут, что поиск рекордных простых чисел нужен для более надёжного шифрования. Это не так: в шифрах используют простые числа из сотен цифр, а не из миллионов[4].
Загадки, которые не решены
- Гипотеза Гольдбаха. В 1742 году Кристиан Гольдбах написал Эйлеру: любое чётное число больше 2 — это сумма двух простых. 4 = 2 + 2, 10 = 3 + 7, 100 = 47 + 53. Доказательства до сих пор нет[2].
- Простые-близнецы. Пары простых, отличающихся на 2: 11 и 13, 17 и 19, 29 и 31. Бесконечно ли их много — неизвестно[2].
О других знаменитых числах — в статьях «Число π» и «Числа Фибоначчи».
Частые вопросы
Почему 1 не считается простым числом?
У единицы только один делитель, а у простого числа их ровно два. Кроме того, если бы единица была простой, разложение чисел на простые множители перестало бы быть единственным: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3…
Какое самое большое простое число?
Самого большого не существует: простых чисел бесконечно много, это доказал Евклид. Самое большое из известных — 2^136 279 841 − 1. В нём 41 024 320 цифр, его нашли 12 октября 2024 года.
Может ли простое число оканчиваться на 5 или чётную цифру?
Только 5 и 2. Все остальные числа, оканчивающиеся на 0, 2, 4, 6, 8, делятся на 2, а на 0 или 5 — делятся на 5. Поэтому простые числа больше 5 оканчиваются только на 1, 3, 7 или 9.
Источники
- Википедия. Простое число, ru.wikipedia.org. ru.wikipedia.org
- Wikipedia. Prime number, en.wikipedia.org. en.wikipedia.org
- Википедия. Решето Эратосфена, ru.wikipedia.org. ru.wikipedia.org
- Wikipedia. Largest known prime number, en.wikipedia.org. en.wikipedia.org
Обсуждение
Комментариев пока нет — начните обсуждение первым.
Чтобы написать комментарий или ответить, войдите на сайт: