Просте число

Натуральні числа від нуля до ста. Прості числа позначено червоним кольором.

Просте число — це натуральне число, яке має рівно два різні натуральні дільники (лише 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 … (послідовність A000040 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Розклад натуральних чисел на добуток простих

Основна теорема арифметики стверджує, що кожне натуральне число більше одиниці (1), можна представити як добуток простих чисел, причому, в єдиний спосіб з точністю до порядку множників. Таким чином, прості числа — це елементарні «будівельні блоки» натуральних чисел.

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

Тести простоти

Ератосфен Киренський.

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

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

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

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

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

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

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

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

${\displaystyle {\frac {\pi (n)}{n/\ln n}}\to 1,\quad n\to \infty .}$

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

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

Найефективнішим з відомих тестів простоти є тест Люка — Лемера для чисел Мерсенна. У зв'язку з цим більшість з останніх знайдених великих простих чисел — числа Мерсенна.

Найбільшим відомим простим числом станом на жовтень 2024 року є ${\displaystyle 2^{136279841}-1}$, яке містить 41 024 320 десяткових цифр у своєму записі. Воно було знайдене 12 жовтня 2024 року в рамках проєкту з розподіленого пошуку простих чисел Мерсенна GIMPS[3].

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

Деякі властивості

• Якщо ${\displaystyle p}$ — просте, і ${\displaystyle p}$ ділить ${\displaystyle ab}$, то ${\displaystyle p}$ ділить щонайменше одне з них. Цю властивість довів Евклід, і відома вона як лема Евкліда. Її використовують при доведенні основної теореми арифметики.
• Кільце остач ${\displaystyle \mathbb {Z} _{n}}$ є полем тоді і тільки тоді, коли ${\displaystyle n}$ — просте.
• Характеристика кожного поля — нуль або просте число.
• Якщо ${\displaystyle p}$ — просте, ${\displaystyle a}$ — натуральне, то ${\displaystyle a^{p}-a}$ ділиться на ${\displaystyle p}$ (мала теорема Ферма).
• Якщо ${\displaystyle G}$ — скінченна група з ${\displaystyle p^{n}}$ елементів, то ${\displaystyle G}$ містить елемент порядку ${\displaystyle p}$.
• Якщо ${\displaystyle G}$ — скінченна група, і ${\displaystyle p^{n}}$ — максимальний степінь ${\displaystyle p}$, який ділить ${\displaystyle |G|}$, то ${\displaystyle G}$ має підгрупу порядку ${\displaystyle p^{n}}$, яку називають підгрупою Силова, більше того, кількість підгруп Силова дорівнює ${\displaystyle pk+1}$ для деякого цілого ${\displaystyle k}$ (теореми Силова).
• Натуральне ${\displaystyle p>1}$ є простим тоді і тільки тоді, коли ${\displaystyle (p-1)!+1}$ ділиться на ${\displaystyle p}$ (теорема Вілсона).
• Якщо ${\displaystyle n>1}$ — натуральне, то існує просте ${\displaystyle p}$, таке, що ${\displaystyle n<p<2n}$ (постулат Бертрана).
• Ряд чисел, обернених до простих, є розбіжним. Більше того, при ${\displaystyle x\to \infty }$

${\displaystyle \sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x.}$

• Будь-яка арифметична прогресія виду ${\displaystyle a,a+q,a+2q,a+3q,...}$, де ${\displaystyle a,q>1}$ — цілі взаємно прості числа, містить нескінченно багато простих чисел (Теорема Діріхле про прості числах в арифметичній прогресії).
• Теорема Ґріна — Тао. Існують як завгодно довгі скінченні арифметичні прогресії, що складаються з простих чисел[5].
• Будь-яке просте число більше 3, можна представити у вигляді ${\displaystyle 6k+1}$, або у вигляді ${\displaystyle 6k-1}$, де ${\displaystyle k}$ — деяке натуральне число.
• Якщо ${\displaystyle p>3}$ — просте, то ${\displaystyle p^{2}-1}$ кратне 24.
• Множина додатних значень многочлена

  ${\displaystyle (k+2)(1-[wz+h+j-q]^{2}-[(gk+2g+k+1)(h+j)+h-z]^{2}-[2n+p+q+z-e]^{2}-}$

  ${\displaystyle [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}-}$

  ${\displaystyle [16r^{2}y^{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}-}$

  ${\displaystyle [(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}-}$

  ${\displaystyle [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})}$

при невід'ємних цілих значеннях змінних збігається з множиною простих чисел.[6][7][8] Цей результат є окремим випадком доведеної Юрієм Матіясевічем діофантності будь-якої ефективно зліченної множини.

Відкриті питання

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

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

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

Застосування

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

Програма обчислення простих чисел на C++

#include <iostream>

bool is_prime(int const num)

{

  if (num <= 3)

  {

      return num > 1;

  }

  else if (num % 2 == 0 || num % 3 == 0)

  {

      return false;

  }

  else

  {

      for (int i = 5; i * i <= num; i += 6)

      {

        if (num % i == 0 || num % (i + 2) == 0)

        {

            return false;

        }

      }

      return true;

  }

}

Варіації і узагальнення

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

Історія

Математичний Папірус Рінда

Математичний Папірус Рінда, що має вік близько від 1550 р. до н.е., описує різні форми розкладання єгипетських дробів для простих і складених чисел.[10] Однак, найбільш ранній відомий запис про явне дослідження простих чисел належить до математики Стародавньої Греції. Евклід у своїй роботі Елементи (близько 300 р. до н. е.) довів нескінченність простих чисел і основну теорему арифметики, і показав як побудувати досконале число із Числа Мерсенна.[11]

Число один

Більшість філософів стародавньої Греції навіть не розглядали 1 як число,[12][13] тому вони навіть не розглядали чи є воно простим. Декілька математиків тих часів вважали, що прості числа є підмножиною непарних чисел, тому вони також не розглядали випадок що число 2 може бути простим. Однак, Евклід і більшість інших Грецьких математиків розглядали 2 як просте число. Ісламські математики середньовіччя здебільшого наслідували Греків і також не розглядали число 1 як число.[12] У середні віки і в часи Ренесансу математики почали ставитися до 1 як до числа, і деякі з них відносили його до першого простого числа.[14] У середині 18-го століття Християн Гольдбах перелічив число 1 як просте у своєму листуванні з Леонардом Ейлером; однак сам Ейлер не розглядав 1 як просте.[15] В 19-му столітті багато математиків досі продовжували вважати число 1 простим,[16] а переліки простих чисел, в яких включали 1 продовжували публікувати до 1956 р.[17][18]

Якби визначення простих чисел було змінене, так щоб до них віднести одиницю, багато тверджень, які стосуються простих чисел необхідно було б переформулювати у досить не зручний спосіб. Наприклад, основну теорему арифметики необхідно було б перефразувати так щоб розкладання виконувалося у прості множники що більші за 1, оскільки кожне число мало б множину способів розкладання із різною кількістю повторених 1.[16] Аналогічно, не правильно б працювало Решето Ератосфена якби число 1 вважалося простим, оскільки в ньому усі числа є кратними 1 і результатом було б лише одне число 1.[18] Деякі інші властивості простих чисел також не виконуються для випадку з 1: наприклад, формули для Функції Ейлера або для суми функції дільників відрізняються для простих чисел і для 1.[19] До початку XX століття математики дійшли згоди, що число 1 не повинне належати до простих чисел, а скоріше належить до своєї власної окремої категорії «одиниці».[16]

Див. також

• Список простих чисел
• Інтервали між простими числами
• Стала простих чисел
• Константа Майсселя — Мертенса
• Складене число
• Решето Ератосфена
• Простий множник
• Прайморіальне просте число
• Степінь простого числа
• Відкриті математичні питання
• Гіпотеза Андріци
• Функція розподілу простих чисел
• 7919 Прайм — астероїд, назва якого означає просте число (англ. prime number — просте число), названий на честь числа 7919, яке є тисячним простим числом.

Примітки

1. Weisstein, Eric W. AKS Primality Test(англ.) на сайті Wolfram MathWorld.
2. Рекорди простих чисел по роках. Архів оригіналу за 5 червня 2020. Процитовано 23 березня 2010.
3. GIMPS Discovers Largest Known Prime Number: 2^136,279,841-1. Mersenne Research, Inc. 21 жовтня 2024. Процитовано 21 жовтня 2024.
4. EFF Cooperative Computing Awards [Архівовано 4 червня 2004 у Wayback Machine.] (англ.)
5. Weisstein, Eric W. Теорема Ґріна — Тао(англ.) на сайті Wolfram MathWorld.
6. Jones JP, Sato D., Wada H., Wiens D (1976). Diophantine representation of the set of prime numbers (PDF). Amer. Math. Mon. 83 (6): 449—464. Архів оригіналу (PDF) за 31 березня 2010. Процитовано 23 березня 2010.
7. Yuri Matiyasevich, Diophantine Equations in the XX Century^[недоступне посилання з квітня 2019]
8. Matijasevic's polynomial [Архівовано 6 серпня 2010 у Wayback Machine.]. The Prime Glossary.
9. Weisstein, Eric W. Landau's Problems(англ.) на сайті Wolfram MathWorld.
10. Bruins, Evert Marie, review in Mathematical Reviews of Gillings, R. J. (1974). The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it?. Archive for History of Exact Sciences. 12: 291—298. doi:10.1007/BF01307175. ISSN 0003-9519. MR 0497458.
11. Stillwell, John (2010). Mathematics and Its History. Undergraduate Texts in Mathematics (вид. 3rd). Springer. с. 40. ISBN 9781441960528. Архів оригіналу за 27 липня 2021. Процитовано 3 квітня 2018.
12. Caldwell, Chris K.; Reddick, Angela; Xiong, Yeng; Keller, Wilfrid (2012). The history of the primality of one: a selection of sources. Journal of Integer Sequences. 15 (9): Article 12.9.8. MR 3005523. Архів оригіналу за 12 квітня 2018. Процитовано 3 квітня 2018. For a selection of quotes from and about the ancient Greek positions on this issue, see in particular pp. 3–4. For the Islamic mathematicians, see p. 6.
13. Tarán, Leonardo (1981). Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary. Philosophia Antiqua : A Series of Monographs on Ancient Philosophy. Т. 39. BRILL. с. 35—38. ISBN 9789004065055. Архів оригіналу за 23 березня 2019. Процитовано 3 квітня 2018.
14. Caldwell та ін., 2012, pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.
15. Caldwell та ін., 2012, p. 15.
16. Caldwell, Chris K.; Xiong, Yeng (2012). What is the smallest prime? (PDF). Journal of Integer Sequences. 15 (9): Article 12.9.7. MR 3005530. Архів оригіналу (PDF) за 12 квітня 2018. Процитовано 3 квітня 2018.
17. Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization (вид. 2nd). Basel, Switzerland: Birkhäuser. с. 36. ISBN 978-0-8176-3743-9. MR 1292250. Архів оригіналу за 23 березня 2019. Процитовано 3 квітня 2018.
18. Conway, John Horton; Guy, Richard K. (1996). The Book of Numbers. New York: Copernicus. с. 129–130. ISBN 978-0-387-97993-9. MR 1411676.
19. For the totient, see Sierpiński, 1988, p. 245 [Архівовано 23 березня 2019 у Wayback Machine.]. For the sum of divisors, see Sandifer, C. Edward (2007). How Euler Did It. MAA Spectrum. Mathematical Association of America. с. 59. ISBN 9780883855638. Архів оригіналу за 23 березня 2019. Процитовано 3 квітня 2018.

Посилання

• Онлайн-утиліта для перевірки простих чисел [Архівовано 17 квітня 2010 у Wayback Machine.]
• The Prime Pages [Архівовано 27 травня 2009 у Wayback Machine.] (англ.) — База даних найбільших відомих простих чисел
• PrimeGrid prime lists — всі прості числа, знайдені в рамках проекту PrimeGrid
• Геометрія простих і досконалих чисел [Архівовано 28 січня 2022 у Wayback Machine.] (ісп.)
• Прості числа [Архівовано 25 лютого 2010 у Wayback Machine.]
• Нетрадиційні магічні квадрати з простих чисел [Архівовано 29 червня 2010 у Wayback Machine.]
• Найменші магічні квадрати з простих чисел [Архівовано 29 червня 2010 у Wayback Machine.]
• Geometrical connection between natural numbers and their factors [Архівовано 24 липня 2013 у Wayback Machine.]
• Ю. Матіясевіч. Формули для простих чисел // Квант. — 1975. — № 5. — С. 5-13.