Арифметика
Особые простые числа
Женщина под маской: как Софи Жермен обманула математиков Парижа
**Марен Мерсенн** (1588 - 1648) - французский монах, который переписывался с величайшими умами эпохи: Декартом, Ферма, Паскалем. Он изучал числа вида 2ᵖ−1 и пытался понять, какие из них простые. Его записки породили охоту, которая длится 400 лет.
Математика - это язык, на котором Бог написал Вселенную. - Галилео Галилей
Простые Софи Жермен сегодня защищают ваши банковские транзакции. **Безопасные простые** (2p+1) используются в криптографии Диффи-Хеллмана. А близнецы? После 2500 лет мы до сих пор не знаем, бесконечно ли их много. В 2013 году Итан Чжан совершил прорыв: доказал, что существует бесконечно много пар простых с разрывом меньше 70 миллионов. Разрыв 2 - близнецы - пока за горизонтом.
Простые числа - атомы арифметики. Но даже среди них есть «знаменитости»: числа Мерсенна дают крупнейшие известные простые, близнецы упорно появляются парами, а простые Софи Жермен защищают вашу интернет-коммуникацию. Каждый тип - своя история и нерешённые проблемы.
- **Криптография:** RSA, Диффи-Хеллман используют особые простые
- **Распределённые вычисления:** GIMPS ищет простые Мерсенна
- **Математика:** открытые проблемы с миллионными призами
Простые Мерсенна
**Простые Мерсенна** - простые числа вида 2ᵖ - 1. Они связаны с совершенными числами и являются рекордсменами по размеру среди известных простых.
**Определение:** Число Mₚ = 2ᵖ - 1 - простое Мерсенна, если: • p - простое • Mₚ - простое **Примеры:** M₂ = 3, M₃ = 7, M₅ = 31, M₇ = 127
Проект GIMPS объединяет миллионы компьютеров для поиска простых Мерсенна. Последние 20+ рекордов - их заслуга.
Почему 2¹¹ - 1 = 2047 - не простое Мерсенна?
Простые близнецы
**Простые близнецы** - пары простых чисел, отличающихся на 2. Это минимально возможный разрыв между простыми (кроме 2 и 3).
**Тройки и четвёрки:** • (5, 7, 11) - нет, 7 и 11 не близнецы • (5, 7), (11, 13), (17, 19) - три подряд пары • «Кузины»: разрыв 4 (например, 7 и 11) • «Sexy primes»: разрыв 6 (например, 5 и 11)
Близнецы становятся всё реже с ростом чисел, но никто не доказал, что они заканчиваются.
Какая из пар - простые близнецы?
Простые Софи Жермен
**Простое Софи Жермен** - простое p, для которого 2p + 1 тоже простое. Названы в честь математика Софи Жермен (1776-1831).
**Софи Жермен (1776-1831):** Французский математик, работала под псевдонимом «Месье Леблан» из-за дискриминации женщин в науке. Внесла вклад в: • Теорию чисел (теорема Ферма) • Теорию упругости • Философию математики
Неизвестно, бесконечно ли много простых Софи Жермен. Эвристика предсказывает, что да, но доказательства нет.
Является ли 11 простым Софи Жермен?
Разрывы между простыми
**Разрыв** (gap) - расстояние между соседними простыми числами. Разрывы становятся в среднем больше, но ведут себя хаотично.
**Рекорды разрывов:** • Первый разрыв 8: после 89 (до 97) • Первый разрыв 20: после 887 (до 907) • Первый разрыв 100: после 396 733 (до 396 833) • Первый разрыв 1000: после числа с ~200 цифрами
Разрывы могут быть огромными, но близнецы (разрыв 2) тоже встречаются среди больших чисел. Это одна из загадок простых чисел.
Простые числа распределены равномерно или по формуле
Простые числа распределены хаотично, но со статистическими закономерностями
Разрывы между простыми варьируются от 2 (близнецы) до сколь угодно больших. Нет формулы, дающей все простые. Но теорема о простых числах предсказывает среднюю плотность: π(n) ≈ n/ln(n). Хаос на микроуровне, порядок на макроуровне.
Почему n! + 2, n! + 3, ..., n! + n - все составные?
Ключевые идеи
- Мерсенна: 2ᵖ - 1, дают крупнейшие простые
- Близнецы: разрыв 2, бесконечность не доказана
- Софи Жермен: p и 2p+1 оба простые
- Разрывы: растут в среднем как ln(p)
Связанные темы
Особые простые связаны с общей теорией простых чисел:
- Простые числа — Базовые понятия
- Совершенные числа — Связь с Мерсенна
- Модулярная арифметика — Тест Люка-Лемера
Вопросы для размышления
- Почему крупнейшие известные простые - числа Мерсенна?
- Как доказать (или опровергнуть), что близнецов бесконечно много?
- Почему безопасные простые важны в криптографии?