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

Простое число - это натуральное число, которое имеет ровно два натуральных делители (только 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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 ... (Последовательность A000040 с Энциклопедии целочисленных последовательностей,)

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

Основная теорема арифметики утверждает, что каждое натуральное число больше единицы (1), можно представить как произведение простых чисел, причем единственным способом с точностью до порядка множителей. Таким образом, простые числа - это элементарные ?строительные блоки" натуральных чисел.

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


2. Тесты простоты

Решето Эратосфена, решето Сундарама и решето Аткина дают простые способы составления начального списка простых чисел до определенного значения.

Однако, на практике, вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, которые решают эту задачу, называют тестами простоты. Существует множество полиномиальных тестов простоты, но большинство из них являются стохастические (например, тест Миллера - Рабина) и используются для нужд криптографии. Только в 2002 году было доказано [1], что задача проверки на простоту в общем виде можно решить за полиномиальное время, но предложенный детерминированный алгоритм имеет довольно большую сложность, что затрудняет его применение на практике.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты. Например, для проверки на простоту чисел Мерсенна используют тест Люка - Лехмер, а для проверки на простоту чисел Ферма - тест Пепино.


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

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

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

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

Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, которое обозначают как \ Pi (n) , Растет как n / \ ln (n) .


4. Больше известно простое число

Издавна ведутся записи, в ​​которых отмечают самые известные в то время простые числа. [2] Один из рекордов поставил своего времени Эйлер, найдя простое число 2 ^ {31} -1 = 2147483647 .

Самым известным простым числом по состоянию на июнь 2009 года является 2 ^ {43112609} -1 . Оно состоит из 12978189 десятичных цифр и является простым числом Мерсенна (M 43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределенному поиску простых чисел Мерсенна GIMPS. Предыдущее по величине известное простое, также является простым числом Мерсенна M 37156667, было найдено 6 сентября 2007 года участником проекта GIMPS Гансом-Михаэлем Елвенихом ( нем. Hans-Michael Elvenich ).

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты : теста Люка - Лехмер. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые известные простые.

За нахождение простых чисел из более 100 млн и 1 млрд десятичных цифр EFF назначила [3] денежные призы в 150 000 и 250 000 долларов США соответственно.


5. Некоторые свойства

  • Если p - Простое, и p делит a b , То p делит a или b . Это свойство доказал Евклид, и известна она как лемма Евклида. Ее используют при доказательстве основной теоремы арифметики.
  • Кольцо Остаток \ Mathbb {Z} _n есть полем тогда и только тогда, когда n - Простое.
  • Характеристика каждого поля - ноль или простое число.
  • Если p - Простое, a - Натуральное, то a ^ p - a делится на p ( малая теорема Ферма).
  • Если G - Конечное группа по p ^ n элементов, то G содержит элемент порядка p .
  • Если G - Конечное группа, и p ^ n - Максимальная степень p , Который делит | G | , То G имеет подгруппу порядка p ^ n , Которую называют подгруппой Силовая, более того, количество подгрупп Силовая равна pk +1 для некоторого целого k ( теоремы Силовая).
  • Натуральное p> 1 является простым тогда и только тогда, когда (P-1)! + 1 делится на p (Теорема Вильсона).
  • Если n> 1 - Натуральное, то существует простое p , Такое, что n <p <2 n (Постулат Бертрана).
  • Ряд чисел, обратных к простым, расходится. Более того, при x \ to \ infty
\ Sum_ {p <x} \ frac {1} {p} \ \ sim \ \ ln \ ln x.
  • Любая арифметическая прогрессия вида a, a + q, a + 2 q, a + 3 q ... , Где a, q> 1 - Цели взаимно простые числа, содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
  • Любое простое число больше 3, можно представить в виде 6k + 1 , Или в виде 6k - 1 , Где k - Некоторое натуральное число.
  • Если p> 3 - Простое, то p ^ 2 - 1 кратное 24.
  • Множество положительных значений многочлена
    (K +2) (1 - [wz + h + j - q] ^ 2 - [(gk + 2g + k + 1) (h + j) + h - z] ^ 2 - [2n + p + q + z - e] ^ 2 -
    [16 (k + 1) ^ 3 (k + 2) (n + 1) ^ 2 + 1 - f ^ 2] ^ 2 - [e ^ 3 (e + 2) (a + 1) ^ 2 + 1 - o ^ 2] ^ 2 - [(a ^ 2 - 1) y ^ 2 + 1 - x ^ 2] ^ 2 -
    [16r ^ 2y ^ 4 (a ^ 2 - 1) + 1 - u ^ 2] ^ 2 - [((a + u ^ 2 (u ^ 2 - a)) ^ 2 - 1) (n + 4dy) ^ 2 + 1 - (x + cu) ^ 2] ^ 2 - [n + l + v - y] ^ 2 -
    [(A ^ 2 - 1) l ^ 2 + 1 - m ^ 2] ^ 2 - [ai + k + 1 - l - i] ^ 2 - [p + l (a - n - 1) + b (2an + 2a - n ^ 2 - 2n - 2) - m] ^ 2 -
    [Q + y (a - p - 1) + s (2ap + 2a - p ^ 2 - 2p - 2) - x] ^ 2 - [z + pl (a - p) + t (2ap - p ^ 2 - 1) - pm] ^ 2)
при неотрицательных целых значениях переменных совпадает с множеством простых чисел. [4] [5] [6] Этот результат является частным случаем доказанной Юрием Матиясевича диофантности любой эффективно Счетное множества.

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

До существует много открытых вопросов относительно простых чисел, самые известные из которых были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе [7] :

  1. Проблема Гольдбаха (первая проблема Ландау): доказать или опровергнуть, что каждое четное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечетное число, большее 5, может быть представлено в виде суммы трех простых чисел.
  2. Вторая проблема Ландау: или бесконечное множество "Простых близнецов" - простых чисел, разница между которыми равно 2?
  3. Гипотеза Лежандра (третья проблема Ландау) верно, что между n ^ 2 и (N + 1) ^ 2 всегда найдется простое число?
  4. Четвертая проблема Ландау: или бесконечное множество простых чисел вида n ^ 2 + 1 ?

Открытой проблемой является также существование бесконечного множества простых чисел во многих целочисленных последовательностях, включая числа Фибоначчи, числа Ферма и т. д.


7. Применение

Большие простые числа (порядка 10 ^ {300} ) Используют в криптографии с открытым ключом. Простые числа также используют в хэш-таблицах и для генерации псевдослучайных чисел (в частности, генераторе псевдослучайных чисел Вихрь Мерсенна).


8. Вариации и обобщения

Примечания

  1. Weisstein, Eric W. AKS Primality Test (Англ.) на сайте Wolfram MathWorld.
  2. Рекорды простых чисел по годам
  3. EFF Cooperative Computing Awards (Англ.)
  4. Jones JP, Sato D., Wada H., Wiens D Diophantine Representation Of The Set Of Prime Numbers / / Amer. Math. Mon .. - Т. 83. - (1976) (6) С. 449-464.
  5. Yuri Matiyasevich, Diophantine Equations in the XX Century
  6. Matijasevic's polynomial. The Prime Glossary.
  7. Weisstein, Eric W. Landau'S Problems (Англ.) на сайте Wolfram MathWorld.