Перегляд вихідного коду сторінки Просте число

''' Просте число '''&nbsp;— це [[натуральне число]], яке має рівно два різних натуральних [[Подільність|дільники]] (лише [[1 (число)|1]] і саме число). Решту чисел, окрім одиниці, називають [[складене число|складеними]]. Таким чином, всі натуральні числа, більші від одиниці, розбивають на прості і складені. [[Теорія чисел]] вивчає властивості простих чисел. В [[Кільце (алгебра)|теорії кілець]] простим числам відповідають [[Незвідний елемент|незвідні елементи]].

Послідовність простих чисел починається так:
: [[2 (число)|2]], [[3 (число)|3]], [[5 (число)|5]], [[7 (число)|7]], [[11 (число)|11]], [[13 (число)|13]], [[17 (число)|17]], [[19 (число)|19]], [[23 (число)|23]], [[29 (число)|29]], [[31 (число)|31]], [[37 (число)|37]], [[41 (число)|41]], [[43 (число)|43]], [[47 (число)|47]], [[53 (число)|53]], [[59 (число)|59]], [[61 (число)|61]], [[67 (число)|67]], [[71 (число)|71]], [[73 (число)|73]], [[79 (число)|79]], [[83 (число)|83]], [[89 (число)|89]], [[97 (число)|97]], [[101 (число)|101]], [[103 (число)|103]], [[107 (число)|107]], [[109 (число)|109]], [[113 (число)|113]] , [[127 (число)|127]], [[131 (число)|131]], [[137 (число)|137]], [[139 (число)|139]], [[149 (число)|149]] … ({{OEIS|A000040}})

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

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

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

== Тести простоти ==
{{Main|Тест простоти}}

[[Файл:Eratosthenes.jpg|thumb|150px| [[Ератосфен|Ератосфен Киренський]].]]

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

Однак на практиці замість отримання списку простих чисел найчастіше потрібно перевірити, чи є дане число простим. Алгоритми, які вирішують це завдання, називають [[тест простоти|тестами простоти]]. Існує безліч [[поліноміальний алгоритм|поліноміальних]] тестів простоти, але більшість з них є [[стохастичні алгоритми|стохастичними]] (наприклад, [[Тест простоти Міллера–Рабіна|тест Міллера — Рабина]]) і [[випадкове просте число|використовуються]] для потреб [[криптографія|криптографії]]. Тільки в [[2002]] році було [[тест простоти AKS|доведено]]<ref>{{ MathWorld | title = AKS Primality Test | urlname = AKSPrimalityTest}}</ref>, що завдання перевірки на простоту в загальному вигляді можна розв'язати за поліноміальний час, але запропонований [[детермінований алгоритм]] має досить велику [[Обчислювальна складність|складність]], що ускладнює його застосування на практиці.

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

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

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

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

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

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

<math>\frac{\pi(n)}{n/\ln n} \to 1, \quad n\to \infty.</math>

== Найбільше відоме просте число ==
{{Main|Найбільше відоме просте число}}

Здавна ведуться записи, в яких відзначають найбільші відомі на той час прості числа.<ref>[http://primes.utm.edu/notes/by_year.html Рекорди простих чисел по роках]</ref> Один з рекордів поставив свого часу Ейлер, знайшовши просте число <math>2^{31}-1 = 2147483647</math>.

Найбільшим відомим простим числом станом на червень 2009 року є <math>2^{43 112 609}-1</math>. Воно складається з 12&nbsp;978&nbsp;189 [[десяткова система числення|десяткових цифр]] і є простим [[Число Мерсенна|числом Мерсена]] (M<sub>43112609</sub>). Його знайшли [[23 серпня]] [[2008]] року на математичному факультеті університету [[Каліфорнійський університет у Лос-Анджелесі|UCLA]] в рамках проекту по розподіленому пошуку простих чисел Мерсена [[GIMPS]]. Попереднє за величиною відоме просте, також є простим числом Мерсена M<sub>37156667</sub>, було знайдено [[6 вересня]] [[2007]] року учасником проекту [[GIMPS]] Гансом-Міхаелем Елвеніхом ({{lang-de|Hans-Michael Elvenich}}).

7 січня 2016 був поставлений новий рекорд: проект GIMPS знайшов ще більше просте число: <math>2^{74 207 281}-1</math>, що складається з {{formatnum:22338618}} десяткових цифр. Нове просте число також є простим числом Мерсена&nbsp;— M<sub>74207281</sub>. Нове просте число було обчислене множенням {{formatnum:74207281}} двійок та відніманням 1. Перевірка простоти тривала 31 добу безперервних обчислень на комп'ютері з процесором [[Intel Core i7|Intel I7-4790]]. Результати перевірки були незалежно підтверджені іншими розробниками з використанням іншого апаратного та програмного забезпечення<ref>{{cite web
 | url = http://www.mersenne.org/primes/?press=M74207281
 | title = GIMPS Project Discovers Largest Known Prime Number: 2<sup>74,207,281</sup>-1.
 | publisher = Great Internet Mersenne Prime Search (GIMPS)
 | accessdate = 20 січня 2016 }}</ref>.

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

За знаходження простих чисел з понад 100&nbsp;000&nbsp;000 та 1&nbsp;000&nbsp;000&nbsp;000 десяткових цифр [[Electronic Frontier Foundation|EFF]] призначила<ref>[http://www.eff.org/awards/coop.php EFF Cooperative Computing Awards] {{Webarchive|url=https://web.archive.org/web/20040604053354/http://www.eff.org/awards/coop.php |date=4 червень 2004 }} {{ref-en}}</ref> грошові призи в 150&nbsp;000 та 250&nbsp;000 [[долар США|доларів США]] відповідно.

== Деякі властивості ==
* Якщо <math> p </math>&nbsp;— просте, і <math>p</math> ділить <math>a b</math>, то <math>p</math> ділить <math>a</math> або <math>b</math>. Цю властивість довів Евклід, і відома вона як [[лема Евкліда]]. Її використовують при доведенні [[Основна теорема арифметики|основної теореми арифметики]].
* [[Кільце (алгебра)|Кільце]] [[остача|остач]] <math>\mathbb{Z}_n</math> є [[Поле (алгебра)|полем]] тоді і тільки тоді, коли <math>n</math>&nbsp;— просте.
* [[Характеристика (алгебра)|Характеристика]] кожного [[Поле (алгебра)|поля&nbsp;]]— нуль або просте число.
* Якщо <math>p</math>&nbsp;— просте, <math>a</math>&nbsp;— натуральне, то <math>a^p - a</math> ділиться на <math>p</math> ([[мала теорема Ферма]]).
* Якщо <math>G</math>&nbsp;— [[скінченна група]] з <math>p^n</math> елементів, то <math>G</math> містить елемент [[Порядок елемента групи|порядку]] <math>p</math>.
* Якщо <math>G</math>&nbsp;— скінченна група, і <math>p^n</math>&nbsp;— максимальний степінь <math>p</math> , який ділить <math>| G |</math> , то <math>G</math> має підгрупу порядку <math>p^n</math>, яку називають підгрупою Силова, більше того, кількість підгруп Силова дорівнює <math>pk+1</math> для деякого цілого <math>k</math> ([[теореми Силова]]).
* Натуральне <math> p > 1 </math> є простим тоді і тільки тоді, коли <math>(p-1)! + 1</math> ділиться на <math>p</math> ([[теорема Вілсона]]).
* Якщо <math>n > 1</math>&nbsp;— натуральне, то існує просте <math> p </math> , Таке, що <math> n < p < 2 n </math> ([[постулат Бертрана]]).
* [[Ряд (математика)|Ряд]] чисел, обернених до простих є розбіжним. Більше того, при <math>x \to \infty</math>
: <math>\sum_{p<x} \frac{1}{p}\ \sim\ \ln \ln x.</math>
* Будь-яка [[арифметична прогресія]] виду <math> a, a + q, a + 2 q, a + 3 q, ... </math>, , де <math>a, q > 1</math>&nbsp;— цілі [[взаємно-прості числа]], містить нескінченно багато простих чисел ([[Теорема Діріхле про арифметичні прогресії|Теорема Діріхле про прості числах в арифметичній прогресії]]).
* Будь-яке просте число більше 3, можна представити у вигляді <math>6k + 1</math>, або у вигляді <math>6k - 1</math>, де <math>k</math>&nbsp;— деяке натуральне число.
* Якщо <math>p > 3</math>&nbsp;— просте, то <math>p^2 - 1</math> кратне 24.
* Множина додатних значень [[Многочлен|многочлена]]
*: <math>(k+2) (1 - [wz + h + j - q]^2 - [(gk + 2g + k + 1)(h + j) + h - z]^2 - [2n + p + q + z - e]^2 - </math>
*: <math>[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 - </math>
*: <math>[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 - </math>
*: <math>[(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 - </math>
*: <math>[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) </math>
: при невід'ємних цілих значеннях змінних збігається з множиною простих чисел.<ref>
{{ cite journal | author = Jones JP,
Sato D., Wada H., Wiens D | year = 1976 | title = Diophantine representation of the set of prime numbers | journal = Amer. Math. Mon. | volume = 83 | issue = 6 | pages = 449-464 | url = http://mathdl.maa.org/images/upload_library/22/Ford/JonesSatoWadaWiens.pdf | archiveurl = https://web.archive.org/web/20100331232439/http://mathdl.maa.org/images/upload_library/22/Ford/JonesSatoWadaWiens.pdf | archivedate = 2010-03-31 | accessdate = 2010-03-23 | deadurl = yes }}
</ref><ref>Yuri Matiyasevich, [http://www.inf.unisi.ch/guest-lectures/matiyas/Lugano_public1_print.pdf Diophantine Equations in the XX Century]{{Недоступне посилання|date=квітень 2019 |bot=InternetArchiveBot }}</ref><ref> [http://primes.utm.edu/glossary/page.php?sort=MatijasevicPoly Matijasevic's polynomial]. The Prime Glossary.</ref> Цей результат є окремим випадком доведенною [[Юрій Матіясевіч|Юрієм Матіясевічем]] діофантності будь-якої ефективно зліченної множини.

== Відкриті питання ==
Досі існує багато [[гіпотеза|відкритих запитань]] щодо простих чисел, найвідоміші з яких були перераховані [[Едмунд Ландау|Едмундом Ландау]] на П'ятому [[Міжнародний конгрес математиків|Міжнародному математичному конгресі]]<ref>{{ MathWorld | title = Landau's Problems | urlname = LandausProblems }}</ref> :

# [[Проблема Гольдбаха]] (''перша проблема Ландау''): довести або спростувати, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел.
# '' Друга проблема Ландау '': чи нескінченна множина [[прості близнюки|«простих близнюків»]]&nbsp;— простих чисел, різниця між якими дорівнює 2?
# '' Гіпотеза [[Лежандр]]а '' (''третя проблема Ландау'') чи правильно, що між <math>n^2</math> і <math>(n + 1)^2</math> завжди знайдеться просте число?
# ''Четверта проблема Ландау'': чи нескінченна множина простих чисел виду <math>n^2 + 1 </math>?

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

== Застосування ==
Великі прості числа (порядку <math>10^{300}</math>) [[Випадкове просте число|використовують]] в [[криптографія|криптографії]] з [[відкритий ключ|відкритим ключем]]. Прості числа також використовують в [[хеш-таблиця]]х і для генерації [[псевдовипадкове число|псевдовипадкових чисел]] (зокрема, в [[Генератор псевдовипадкових чисел|генераторі псевдовипадкових чисел]] [[Вихор Мерсенна]]).

== Варіації і узагальнення ==
* В [[Кільце (математика)|теорії кілець]], у розділі [[Абстрактна алгебра|абстрактної алгебри]], визначено поняття [[Простий елемент|простого елемента]] та [[Простий ідеал|простого ідеалу]].
* В [[вузол (топологія)|теорії вузлів]] існує поняття '' простого вузла '', який, у певному сенсі, не може бути розбитий на простіші вузли.

==Історія==
[[File:Rhind Mathematical Papyrus.jpg|thumb|Математичний [[Папірус Рінда]]|alt=Математичний Папірус Рінда]]
Математичний [[Папірус Рінда]], що має вік близько від 1550 р.до.н.е, описує різні форми розкладання [[Єгипетський дріб|єгипетських дробів]] для простих і [[Складене число|складених чисел]].<ref>Bruins, Evert Marie, review in ''Mathematical Reviews'' of {{cite journal | last = Gillings | first = R. J. | doi = 10.1007/BF01307175 | journal = Archive for History of Exact Sciences | mr = 0497458 | pages = 291–298 | title = The recto of the Rhind Mathematical Papyrus. How did the ancient Egyptian scribe prepare it? | volume = 12 | year = 1974}}</ref> Однак, самим раннім відомим записом про явне дослідження простих чисел відноситься до [[Давньогрецька математика|математики Стародавньої Греції]]. [[Евклід]] у своїй роботі ''[[Начала Евкліда|Елементи]]'' (близько 300 р.до.н.е.) довів {{нп|Теорема Евкліда|нескінченність простих чисел|en|Euclid's theorem}} і [[Основна теорема арифметики|основну теорему арифметики]], і показав як побудувати [[досконале число]] із [[Число Мерсенна|Числа Мерсенна]].<ref name="stillwell-2010-p40">{{cite book|title=Mathematics and Its History|series=Undergraduate Texts in Mathematics|first=John|last=Stillwell|authorlink=John Stillwell|edition=3rd|publisher=Springer|year=2010|isbn=9781441960528|page=40|url=https://books.google.com/books?id=V7mxZqjs5yUC&pg=PA40}}</ref>
===Число один===
Більшість філософів стародавньої Греції навіть не розглядали 1 як число,<ref name="crxk-34">{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Reddick | first2 = Angela | last3 = Xiong | first3 = Yeng | last4 = Keller | first4 = Wilfrid | issue = 9 | journal = [[Journal of Integer Sequences]] | mr = 3005523 | page = Article 12.9.8 | title = The history of the primality of one: a selection of sources | url = https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html | volume = 15 | year = 2012 | ref=harv}} 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.</ref><ref>{{cite book|title=Speusippus of Athens: A Critical Study With a Collection of the Related Texts and Commentary|volume=39|series=Philosophia Antiqua : A Series of Monographs on Ancient Philosophy|first=Leonardo|last=Tarán|publisher=BRILL|year=1981|isbn=9789004065055|pages=35–38|url=https://books.google.com/books?id=cUPXqSb7V1wC&pg=PA35}}</ref> тому вони навіть не розглядали чи є воно простим. Декілька математиків тих часів вважали, що прості числа є підмножиною непарних чисел, тому вони також не розглядали випадок що число 2 може бути простим. Однак, Евклід і більшість інших Грецьких математиків розглядали 2 як просте число. Ісламські математики середньовіччя здебільшого наслідували Греків і також не розглядали число 1 як число.<ref name="crxk-34"/>
У середні віки і в часи Ренесансу математики почали ставитися до 1 як до числа, і деякі з них відносили його до першого простого числа.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, pp. 7–13. See in particular the entries for Stevin, Brancker, Wallis, and Prestet.</ref> У середині 18-го століття [[Християн Гольдбах]] перелічив число 1 як просте у своєму листуванні з [[Леонард Ейлер|Леонардом Ейлером]]; однак сам Ейлер не розглядав 1 як просте.<ref>{{harvnb|Caldwell|Reddick|Xiong|Keller|2012}}, p. 15.</ref> В 19-му столітті багато математиків досі продовжували вважати число 1 простим,<ref name="cx"/> а переліки простих чисел, в яких включали 1 продовжували публікувати до 1956 р.<ref>{{cite book | last=Riesel | first=Hans | authorlink= Hans Riesel | title=Prime Numbers and Computer Methods for Factorization | publisher=Birkhäuser | location=Basel, Switzerland | isbn=978-0-8176-3743-9 | year=1994|page=36|edition=2nd|mr=1292250|url=https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA36 | ref=harv}}</ref><ref name="cg-bon-129-130">{{cite book | last1=Conway | first1=John Horton | author1-link=John Horton Conway | last2=Guy | first2=Richard K. | author2-link=Richard K. Guy | title=The Book of Numbers | publisher=Copernicus | location=New York | isbn=978-0-387-97993-9 | year=1996 | pages = 129–130 | mr=1411676 | ref=harv}}</ref>

Якби визначення простих чисел було змінене, так щоб до них віднести одиницю, багато тверджень, які стосуються простих чисел необхідно було б переформулювати у досить не зручний спосіб. Наприклад, основну теорему арифметики необхідно було б перефразувати так щоб розкладання виконувалося у прості множники що більші за 1, оскільки кожне число мало б множину способів розкладання із різною кількістю повторених 1.<ref name="cx">{{cite journal | last1 = Caldwell | first1 = Chris K. | last2 = Xiong | first2 = Yeng | issue = 9 | journal = [[Journal of Integer Sequences]] | mr = 3005530 | page = Article 12.9.7 | title = What is the smallest prime? | url = https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.pdf | volume = 15 | year = 2012}}</ref> Аналогічно, не правильно б працювало [[Решето Ератосфена]] якби число 1 вважалося простим, оскільки в ньому усі числа є кратними 1 і результатом було б лише одне число 1.<ref name="cg-bon-129-130"/> Деякі інші властивості простих чисел також не виконуються для випадку з 1: наприклад, формули для [[Функція Ейлера|Функції Ейлера]] або для [[Функція дільників|суми функції дільників]] відрізняються для простих чисел і для 1.<ref>For the totient, see {{harvnb|Sierpiński|1988}}, [https://books.google.com/books?id=ktCZ2MvgN3MC&pg=PA245 p. 245]. For the sum of divisors, see {{cite book|title=How Euler Did It|series=MAA Spectrum|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2007|isbn=9780883855638|page=59|url=https://books.google.com/books?id=sohHs7ExOsYC&pg=PA59|ref=harv}}</ref> До початку 20-го століття, математики дійшли згоди, що число 1 не повинне відноситися до простих чисел, а скоріше відноситься до своєї власної окремої категорії "[[Оборотний елемент|одиниці]]".<ref name="cx"/>

== Див. також ==
* [[Список простих чисел]]
* [[Складене число]]
* [[Решето Ератосфена]]
* [[Відкриті математичні проблеми]]
* [[7919 Прайм]]&nbsp;— астероїд, назва якого означає просте число ({{lang-en|prime number}}&nbsp;— просте число), названий на честь числа 7919, яке є тисячним простим числом.

== Примітки ==
{{reflist}}

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

== Посилання ==
{{Портал|Математика}}
* [http://ru.numberempire.com/primenumbers.php Онлайн-утиліта для перевірки простих чисел]
* [http://primes.utm.edu/ The Prime Pages] {{ ref-en }}&nbsp;— База даних найбільших відомих простих чисел
* [https://web.archive.org/web/20100530071550/http://primegrid.com/orig/torrent.php PrimeGrid prime lists]&nbsp;— всі прості числа, знайдені в рамках проекту [https://web.archive.org/web/20100530071550/http://primegrid.com/orig/torrent.php PrimeGrid]
* [http://www.polprimos.com Геометрія простих і досконалих чисел] {{ ref-es }}
* [http://www.natalimak1.narod.ru/prost.htm Прості числа]
* [http://www.natalimak1.narod.ru/netrpr.htm Нетрадиційні магічні квадрати з простих чисел]
* [http://www.natalimak1.narod.ru/sqmin1.htm Найменші магічні квадрати з простих чисел]
* [http://www.youtube.com/watch?v=sbjPwyPT1AI Geometrical connection between natural numbers and their factors]
* {{ стаття | автор = Ю. Матіясевіч | title = Формули для простих чисел | видання =  [[Квант (журнал)|Квант]] | рік = 1975 | номер = 5 | сторінки = 5-13 | посилання = http://kvant.mccme.ru/1975/05/formuly_dlya_prostyh_chisel.htm }}

{{Quantity}}

[[Категорія:Прості числа| ]]
[[Категорія:Теорія чисел]]
[[Категорія:Цілочисельні послідовності]]
[[Категорія:Нерозв'язані проблеми математики]]