Просте число

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Просте число  — це натуральне число, яке має рівно два різних натуральних дільники (лише 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), можна представити як добуток простих чисел, причому, в єдиний спосіб з точністю до порядку множників. Таким чином, прості числа — це елементарні «будівельні блоки» натуральних чисел.

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

Тести простоти[ред.ред. код]

Докладніше: Тест простоти

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

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

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

Скільки існує простих чисел?[ред.ред. код]

Простих чисел нескінченно багато. Найдавніший відомий доказ цього факту було дано Евклідом в «Началах» (книга IX, твердження 20). Його доказ може бути коротко відтворено так:

Уявімо, що кількість простих чисел скінченна. Перемножимо їх і додамо одиницю. Отримане число не ділиться ні на одне зі скінченного набору простих чисел, тому що залишок від ділення на будь-яке з них дає одиницю. Значить, добуток має ділитись на деяке просте число, не включене до цього набору.

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

Відома теорема про розподіл простих чисел стверджує, що кількість простих чисел менших за n, яке позначають як \pi (n), росте як n / \ln (n) .

Найбільше відоме просте число[ред.ред. код]

Здавна ведуться записи, в яких відзначають найбільші відомі на той час прості числа.[2] Один з рекордів поставив свого часу Ейлер, знайшовши просте число 2^{31}-1 = 2147483647.

Найбільшим відомим простим числом станом на червень 2009 року є 2^{43112609}-1. Воно складається з 12 978 189 десяткових цифр і є простим числом Мерсена (M43112609). Його знайшли 23 серпня 2008 року на математичному факультеті університету UCLA в рамках проекту по розподіленому пошуку простих чисел Мерсена GIMPS. Попереднє за величиною відоме просте, також є простим числом Мерсенна M37156667, було знайдено 6 вересня 2007 року учасником проекту GIMPS Гансом-Міхаелем Елвеніхом (нім. Hans-Michael Elvenich).

Числа Мерсена вигідно відрізняються від решти наявністю ефективного тесту простоти: тесту Люка — Лемера. Завдяки йому прості числа Мерсена давно утримують рекорд як найбільші відомі прості.

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

Деякі властивості[ред.ред. код]

  • Якщо  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.
при невід'ємних цілих значеннях змінних збігається з множиною простих чисел.[4][5][6] Цей результат є окремим випадком доведенною Юрієм Матіясевічем діофантності будь-якої ефективно зліченної множини.
  • Якщо натуральий ряд чисел згрупувати по 2 в стовпчику ось так:
    1357091113151719212325272931
    2468101214161820222426283032...

то там де просте число повторюється 2 рази в стовпчику до наступного такого випадку (просте число повторюється два рази підряд в стовпчику) завжди кратне трьом (на великих значеннях це треба ще перевірити, але на малих значеннях це так)[Джерело?].

Відкриті питання[ред.ред. код]

Досі існує багато відкритих запитань відносно простих чисел, найвідоміші з яких були перераховані Едмундом Ландау на П'ятому Міжнародному математичному конгресі [7] :

  1. Проблема Гольдбаха (перша проблема Ландау): довести або спростувати, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел.
  2. Друга проблема Ландау : чи нескінченна множина «простих близнюків» — простих чисел, різниця між якими дорівнює 2?
  3. Гіпотеза Лежандра (третя проблема Ландау) чи вірно, що між n^2 і (n + 1)^2 завжди знайдеться просте число?
  4. Четверта проблема Ландау: чи нескінченна множина простих чисел виду n^2 + 1 ?

Відкритою проблемою є також існування нескінченної кількості простих чисел у багатьох цілочисельних послідовностях, включаючи числа Фібоначчі, числа Ферма і т. д.

Застосування[ред.ред. код]

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

Варіації і узагальнення[ред.ред. код]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  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.

Література[ред.ред. код]

  • Трост Эрнст. Простые числа / Перевод с немецкого. — Москва: Государственное издательство физико-математической литературы, 1959. — 136 с.
  • Мир математики: В 40 томах. — Т. 3: Энрике Грасиан. Простые числа. Долгая дорога к бесконечности / Перевод с аглийского. — Москва: Де Агостини, 2014. — 144 с.

Посилання[ред.ред. код]

Статті з математики, пов'язані з числами

Число | Натуральні числа | Цілі числа | Раціональні числа | Ірраціональні числа | Constructible numbers | Алгебраїчні числа | Трансцендентні числа | Computable numbers | Дійсні числа | Комплексні числа | Подвійні числа | Дуальні числа | Бікомплексні числа | Гіперкомплексні числа | Кватерніони | Октоніони | Седеніони | Superreal numbers | Hyperreal numbers | Surreal numbers | Nominal numbers | Ординальні числа | Кардинальні числа | P-адичні числа | Послідовності натуральних чисел | Математичні константи | Великі числа | Нескінченність