Арифметика
Простые числа
Охотники за простыми числами
В 1588 году итальянский математик **Пьетро Катальди** нашёл простое число 524287 = 2¹⁹ − 1. Он потратил на это годы ручных вычислений. Сегодня добровольцы проекта **GIMPS** (Great Internet Mersenne Prime Search) используют тысячи компьютеров для поиска гигантских простых чисел.
Простые числа - не просто математическая игрушка. RSA-шифрование, защищающее банковские транзакции и секретную переписку, основано на сложности разложения больших чисел на простые множители.
Банковский пароль защищён простыми числами. RSA-шифрование основано на том, что перемножить два огромных простых числа легко, а разложить результат обратно - практически невозможно. Простые числа - основа современной криптографии.
- **Криптография:** RSA, защита банковских транзакций
- **Хеширование:** проверка целостности данных
- **Музыка:** интервалы и гармонии связаны с простыми числами
Определение простого числа
Число 12 можно разбить: 12 = 3 × 4 = 2 × 6 = 2 × 2 × 3. А число 7? Только 7 = 1 × 7. Такие «неразбиваемые» числа называются **простыми**.
**Простое число** - натуральное число больше 1, которое делится только на 1 и на себя. Простые: 2, 3, 5, 7, 11, 13, 17, 19, 23... Составные: 4, 6, 8, 9, 10, 12, 14, 15...
Простые числа - «атомы» арифметики. Любое целое число можно разложить на простые множители, как молекулу на атомы. И это разложение единственно!
Какое из чисел является простым?
Проверка на простоту
Как проверить, простое ли число 97? Делить на все числа от 2 до 96? Есть способ лучше!
**Почему до √n достаточно:** Если n = a × b, один из множителей не превосходит √n. Для 100: √100 = 10. Если 100 составное, один из делителей ≤ 10. 100 = 10 × 10 = 4 × 25 = 2 × 50 В каждой паре есть делитель ≤ 10.
Для очень больших чисел (сотни цифр) используют вероятностные тесты. Они не дают 100% гарантии, но работают за секунды.
До какого числа достаточно проверять делители для проверки простоты 143?
Решето Эратосфена
Как найти ВСЕ простые числа до 100? Древнегреческий математик Эратосфен придумал элегантный метод - «решето», отсеивающее составные числа.
**Эффективность решета:** Для нахождения всех простых до n: • Наивный метод: ~n² операций • Решето Эратосфена: ~n log log n операций Для n = 1 000 000 - разница в тысячи раз!
Решето - пример алгоритма, который проще понять визуально. Составные числа «проваливаются» через решето, простые - остаются.
В решете Эратосфена для чисел до 50, после вычёркивания кратных 7, какое следующее число нужно обработать?
Бесконечность простых чисел
Простых чисел бесконечно много. Это доказал Евклид более 2300 лет назад одним из самых красивых доказательств в математике.
**Открытые вопросы о простых:** • Гипотеза Гольдбаха: каждое чётное число > 2 - сумма двух простых? • Гипотеза о простых-близнецах: бесконечно ли пар (p, p+2)? • Гипотеза Римана: о распределении простых (миллион долларов за решение!)
Простые числа - одна из глубочайших тем математики. Они кажутся случайными, но подчиняются тонким закономерностям, которые мы до сих пор не полностью понимаем.
Формула p₁×p₂×...×pₙ + 1 всегда даёт простое число
Эта формула даёт число, не делящееся на известные простые, но оно может быть составным
2×3×5×7×11×13 + 1 = 30031 = 59 × 509. Число не простое, но его множители (59 и 509) - новые простые, не из списка. Доказательство Евклида всё равно работает!
Если все простые - это 2, 3, 5, то число 2×3×5 + 1 = 31...
Ключевые идеи
- Простое число делится только на 1 и себя (1 - не простое!)
- Для проверки достаточно делителей до √n
- Решето Эратосфена находит все простые до n
- Простых чисел бесконечно много (теорема Евклида)
Связанные темы
Простые числа - центр теории чисел:
- Факторизация — Разложение на простые
- Криптография — RSA и защита данных
- Специальные простые — Близнецы, Мерсенна, Софи Жермен
Вопросы для размышления
- Почему 2 - единственное чётное простое число?
- Как компьютеры находят простые числа с сотнями цифр?
- Почему простые числа кажутся «случайными» в своём распределении?