Просто число

Просто число е естествено число, по-голямо от 1, което има точно два естествени делителя – 1 и самото себе си. Например 5 е просто, защото се дели без остатък единствено на 1 и 5, докато 6 не е, защото се дели без остатък освен на 1 и 6 и на 2 и 3. Естествените числа, по-големи от едно, които не са прости, се наричат съставни. Числата нула и едно не са нито прости, нито съставни. Простите числа са един от основните обекти, които се изучават от теорията на числата.

Първите няколко прости числа са: 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 ... Определянето на двуцифрените прости числа не е трудно, но при по-големи числа става процесът все по-трудоемък, което налага използването на компютърни програми.

Множеството на простите числа понякога се означава с ℙ или P. Тъй като 2 е единственото четно просто число, терминът нечетни прости числа се използва за означаване на всички прости числа освен 2.

Представяне на естествените числа като произведение на прости множители

Основната теорема на аритметиката гласи, че всяко цяло число, по-голямо от 1, може да се представи по единствен начин (с точност до реда на множителите) като произведение на прости числа. Например

$23244=2^{2}\times 3\times 13\times 149\,$

като всяко друго разлагане на 23244 ще бъде идентично на горното с изключение на реда на множителите. Вижте алгоритъм за разлагане на прости множители за повече подробности относно това, как на практика се разлагат големи естествени числа.

Важността на тази теорема е една от причините, поради които 1 се изключва от множеството на простите числа. Ако приемем 1 за просто, теоремата ще изисква допълнителни уточнения.

Колко са простите числа?

Има безброй много прости числа. Най-старото известно доказателство на този факт е дадено от гръцкия математик Евклид в книгата му Елементи. Твърдението на Евклид е "броят на простите числа е по-голям от всяко отнапред зададено [крайно] число", и неговото доказателство по същество е следното:

Да допуснем, че множеството на простите числа е крайно и има m на брой елемента. Да умножим всички m прости числа и към резултата да добавим едно. Тъй като полученото число е по-голямо от всяко просто, то не принадлежи на горното множество. Освен това то не се дели на нито едно от крайния брой прости, защото ако го разделим с частно и остатък на някое от тях, ще получим остатък едно, а едно не се дели на никое просто число. Следователно то трябва или да е просто, или да се дели на някое просто число, което не принадлежи на горното множество. И в двата случая получаваме, че броят на всички прости числа трябва да бъде поне m+1, което е в противоречие с първоначалното допускане. Това означава, че допускането ни не е вярно, тоест има безбройно много прости числа.

Други математици са представяли свои собствени доказателства. Едно от тях (принадлежащо на Ойлер) показва, че сумата от реципрочните на всички прости числа клони към безкрайност. Доказателството на Кумер е особено елегантно, а това на Фурстенберг използва обща топология.

Въпреки че има безбройно много прости, възникват други въпроси относно броя им – например „Колко приблизително са простите числа, по-малки от 100 000“ или „Каква е вероятността произволно стоцифрено число да е просто?“ Отговорът на тези и други въпроси се дава от закона за разпределение на простите числа, (Съвременните компютри позволяват сравнително бързо да се отговори точно на първия въпрос; отговорът е 9592, като най-голямото просто е 99991.)

Намиране на прости числа

Решетото на Ератостен е прост начин, а решетото на Аткин е бърз начин да се намери списъкът на всички прости числа, по-малки от някое отнапред зададено число.

На практика обаче по-често се налага да се провери дали дадено число е просто, отколкото да се намери списък с прости числа. Често дори е достатъчно да се знае отговорът на горния въпрос с достатъчно голяма вероятност. Възможно е бързо да се провери дали дадено голямо число (например до хиляда цифри) е просто, използвайки вероятностни тестове.

Един начин за установяване дали едно число е просто е, като се провери дали се дели на някое от простите числа, по-малки от квадратния му корен. Ако не се дели на нито едно от тях, то е просто. Това е най-елементарният известен тест, но той не е практичен за големи числа, тъй като броят на възможните делители нараства експоненциално, когато броят на цифрите на числото се увеличава.

През 2002 година индийски учени от IIT Kanpur откриват нов детерминистичен алгоритъм, който проверява дали дадено число N е просто, като времето, необходимо за изчисление, е полиномиална функция на броя на цифрите на N.

Някои свойства на простите числа

• Ако p е просто и p дели произведението ab, където a и b са цели, то p дели a или p дели b. Това твърдение е доказано от Евклид и е известно като лема на Евклид. Използва се за някои от доказателствата на единствеността на разлагане на прости множители.

Забележка: В сила е нещо повече. Нека за едно естествено число p>1 и за всеки две цели числа a и b е вярно, че ако p дели произведението ab, то p дели a или p дели b. В някои изложения на елементарната аритметика това свойство се използва за дефиниция на понятието просто число, а фактът, че простите числа имат точно два делителя, се доказва впоследствие.

• Ако p е просто и a е произволно цяло число, то a^p − a се дели на p (малка теорема на Ферма).
• Едно цяло p > 1 е просто тогава и само тогава, когато факториелът (p – 1)! + 1 се дели на p (теорема на Уилсън). Обратно, едно цяло n > 4 е съставно тогава и само тогава, когато (n – 1)! се дели на n.
• Ако n е положително цяло число, по-голямо от 1, то винаги има просто число p, за което n < p < 2n (постулат на Бертран).
• Сумата от реципрочните на всички прости е разходящ ред. (доказателство). По-точно, ако със S(x) означим сумата от реципрочните на всички прости числа p, за които p ≤ x, то S(x) = Θ(ln ln x) за x → ∞.
• За всяко просто число p > 2, съществува естествено число n такова, че p = 4n ± 1.
• За всяко просто число p > 3, съществува естествено число n такова, че p = 6n ± 1.
• Във всяка аритметична прогресия a, a + q, a + 2q, a + 3q,..., където положителните цели числа a и q ≥ 1 са взаимно прости, има безбройно много прости (теорема на Дирихле за простите числа).
• Законът за разпределение на простите числа гласи, че отношението между броя на простите числа, по-малки от x, и х е асимптотично на 1/ln x (тоест при големи x вероятността произволно избрано число, по-малко от x, да е просто е обратно пропорционална на броя на цифрите в x).

Нерешени проблеми

Има много нерешени въпроси, свързани с простите числа. Най-важният от тях е хипотезата на Риман, която в общи линии твърди, че простите числа са разпределени максимално равномерно. Повечето математици считат, че хипотезата е вярна.

Други хипотези:

• Хипотеза на Голдбах: Всяко четно число, по-голямо от 2, може да се представи като сума на две прости числа.

Малко по-слабото твърдение – така наречената тернарна хипотеза на Голдбах, твърди, че всяко нечетно число, по-голямо от 7, може да се представи като сума на три нечетни прости. Тази хипотеза е доказана от Виноградов през 1937 година.

• Хипотеза за простите близнаци: Има безбройно много прости числа близнаци, тоест двойки от прости числа с разлика 2, като например 5 и 7 или 11 и 13.

• Редицата на Фибоначи съдържа безбройно много прости числа.

• Има безбройно много прости числа от вида n² + 1.
• Хипотеза на Льожандър: Винаги има просто число между n² и (n + 1)² за всяко n.

• Хипотеза на Брокар: Винаги има поне четири прости числа между квадратите на последователни прости числа, по-големи от 2.

Най-голямото известно просто число

Най-голямото известно просто число към октомври 2024 e 2^{136 279 841} − 1, и се записва с 41 024 320 знака. То е число на Мерсен, както и следващите го единадесет най-големи прости числа.

След появата на компютрите почти всички намерени най-големи прости числа са били мерсенови числа. Това е така, защото съществува изключително бърз алгоритъм за проверка на числа от този тип. Най-голямото известно просто число, което не е мерсеново число, е единадесетото по големина.

Приложения

Изключително големи прости (тоест по-големи от 10¹⁰⁰) се използват в някои алгоритми в криптографията. Прости числа също се използват за хеш таблици и генератори на псевдослучайни числа.

Вижте също

• Решето на Ератостен