Простое число

Просто́е число́ — это натуральное число больше 1, которое не имеет делителей, отличных от 1 и самого себя. Последовательность простых чисел начинается с

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, 101, 103, 107, 109, 113 (см. список простых чисел для первых 500 простых).

Свойство числа являться простым называется примарность. Если число превышающее 1 не является простым, оно называется составным.

Разложение натуральных чисел в произведение простых

Основная теорема арифметики утверждает, что каждое натуральное число представимо в виде произведения простых чисел, причём единственным способом. Таким образом, простые числа — «элементарные строительные блоки» натуральных чисел.

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестно полиномиальных алгоритмов факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На алгоритмической сложности задачи задачи факторизации базируется криптосистема RSA.

Сколько существует простых чисел?

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма всех чисел, обратных к простым, расходится.

Хотя количество простых чисел бесконечно, можно задавать вопросы типа: «сколько простых чисел меньших 100 000?» или «А простое ли случайное число, состоящее из 100 цифр?». На эти и подобные вопросы отвечает теорема простых чисел.

Поиск простых чисел

Решето Эратосфена — это простой способ нахождения списка простых чисел до некоторого значения.

На практике, обычно возникает необходимость проверить, является ли число простым, а не получать список простых чисел. Часто, достаточно бывает проверить, является ли число простым с некоторой большой вероятностью. Существет возможность быстро проверить, является ли данное большое число (скажем, из 100 цифр) простым используя вероятностные тесты на примарность.

Некоторые свойства простых чисел

• Если $p$ — простое, и $p$ делит $ab$, то $p$ делит $a$ или $b$. Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется для доказательства единственности разложения на простые множители.
• Кольцо вычетов $\mathbb {Z} _{n}$ является полем тогда и только тогда, когда $n$ — простое.
• Характеристика каждого поля — это ноль или простое число.
• Если $p$ — простое, а $a$ — натуральное, то $a^{p}-a$ делится на $p$ (малая теорема Ферма).
• Если $G$ — конечная группа, и $p^{n}$ — самая большая степень $p$, которая делит порядок группы $G$, то $G$ имеет подгруппу порядка $p^{n}$.
• Если $G$ — конечная группа с $p^{n}$ элементов, то $G$ содержит элемент порядка $p$.
• Натуральное $p>1$ является простым тогда и только тогда, когда факториал $(p-1)!+1$ делится на $p$ (теорема Вильсона). Обратно, натуралное $n>4$ — составное тогда и только тогда, когда $(n-1)!$ делится на $n$.
• Если $n$ — нутуральное, то существует простое $p$, такое что $n<p<2n$ (постулат Бертрана).
• Ряд чисел, обратных к простым, расходится. Более точно: если $S(x)$ означает сумму всех обратных чисел к простым $p<x$, то $S(x)\sim \ ln\ ln\ x$ при $x\to \infty$.
• Любая послодовательность вида $a,a+q,a+2q,a+3q,...$, где $a,q>1$ взаимно просты содержит бесконечное число нулей (теорема Дирихле).

Открытые вопросы

До сих пор существует много открытых вопросов относительно простых чисел. Например:

• Проблема Гольдбаха — может ли быть каждое чётное число больше двух представлено в виде суммы двух простых чисел?
• Проблема простых чисел-близнецов. Простые числа-близницы — простые, разница между которыми равна 2. Найдётся ли бесконечное число близнецов?
• Содержит ли последовательность чисел Фибоначчи бесконечное число простых?
• Существует ли бесконечно много простых Ферма?
• Всегда ли есть простое число между $n^{2}$ и $(n+1)^{2}$?
• Найдётся ли бесконечно много простых вида $n^{2}+1$?

Наибольшее известное простое

Наибольшее известное простое — $2^{24036583}-1$ (число из 7235733 десятичных цифр). Это 41-е известное число Мерсена. $M_{24036583}$ было найдено 15 мая 2004 года группой GIMPS.

Следующее самое больше простое число — $2^{20996011}-1$ (число из 6320430 десятичных цифр) — 40-е число Мерсена также было найдено GIMPS 17 ноября 2003 и анонсировано в начале декабря 2003 года после двойной проверки. До активного использования компьютеров самыми большими известными простыми числами были также числа Мерсена, потому что существует быстрый тест на примарность для чисел Мерсена — тест Люкаса-Лемера.

Приложения простых чисел

Очень большие простые числа (порядка $10^{100}$) используются в криптографии с публичным ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел. tokipona:nanpa lawa