Просте число

Основна теорема арифметики стверджує, що кожне натуральне число більше одиниці (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}$.

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

7 січня 2016 був поставлений новий рекорд: проект GIMPS знайшов ще більше просте число: ${\displaystyle 2^{74207281}-1}$, що складається з 22 338 618 десяткових цифр. Нове просте число також є простим числом Мерсенна — M_74207281. Нове просте число було обчислене множенням 74 207 281 двійок та відніманням 1. Перевірка простоти тривала 31 добу безперервних обчислень на комп'ютері з процесором Intel I7-4790. Результати перевірки були незалежно підтверджені іншими розробниками з використанням іншого апаратного та програмного забезпечення[3].

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

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

• Якщо ${\displaystyle p}$ — просте, і ${\displaystyle p}$ ділить ${\displaystyle ab}$, то ${\displaystyle p}$ ділить ${\displaystyle a}$ або ${\displaystyle b}$. Цю властивість довів Евклід, і відома вона як лема Евкліда. Її використовують при доведенні основної теореми арифметики.
• Кільце остач ${\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}$ — цілі взаємно-прості числа, містить нескінченно багато простих чисел (Теорема Діріхле про прості числах в арифметичній прогресії).
• Будь-яке просте число більше 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})}$

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

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

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

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

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

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

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

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

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

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

• Онлайн-утиліта для перевірки простих чисел
• The Prime Pages (англ.) — База даних найбільших відомих простих чисел
• PrimeGrid prime lists — всі прості числа, знайдені в рамках проекту PrimeGrid
• Геометрія простих і досконалих чисел (ісп.)
• Прості числа
• Нетрадиційні магічні квадрати з простих чисел
• Найменші магічні квадрати з простих чисел
• Geometrical connection between natural numbers and their factors
• Ю. Матіясевіч. Формули для простих чисел // Квант. — 1975. — № 5. — С. 5-13.