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

Просто́е число́ — это натуральное число больше 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 не является простым, оно называется составным.

Представление натурального числа произведением простых

Фундаментальная теорема арифметики — важный факт; она утверждает, что каждое натуральное число представимо в виде произведения простых, причём единственным способом. Таким образом, простые числа — «элементарные строительные блоки» натуральных чисел. Важность этой теоремы — одна их причин исключения $1$ из набора простых чисел. Если бы единица считалась простым числом, формулировку теоремы пришлось бы уточнять.

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

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга 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^{20996011}-1$ (число из 6320430 цифр). Это 40-е известное число Мерсена. $M_{20996011}$ было найдено 17 ноября 2003 года группой GIMPS и было анонсировано в начале декабря 2003 года.

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

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

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