Прости числа

Простите числа са числата, които се делят само на единица и на себе си. Свойствата на простите числа често се използват например в криптографията.

Определение и примери

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

Редицата на първите няколко прости числа: 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…

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

Провери дали едно число е просто

Свойства на простите числа

• Простите числа са безкрайно много. Доказателството е в статията за доказателство от противното.
• За всяко цяло число z>1 в интервала (z; 2z) има поне едно просто число. Пример: за z = 2 имаме интервала (2; 4). Единственото цяло число в този интервал е 3 и то е просто число. За z = 5 получаваме интервала (5; 10), т.е. числата 6, 7, 8, 9. Числото 7 е просто. Подобно е и за по-големи z.
• Простото число на Мерсен е просто число, което е с единица по-малко от някаква целочислена степен на числото 2. Простото число на Мерсен M има вид M = 2^z − 1, където z е някакво естествено число. Пример е простото число 3, защото 2² − 1 = 3. Или 7, защото 2³ − 1 = 7.
• Най-големите известни прости числа обикновено са именно числата на Мерсен. Например на 23 август 2008 г. е намерено простото число на Мерсен M_43112609, където долният индекс е показателят z. Става дума за простото число 2^43112609 − 1, което има 12 978 189 цифри и по това време е било най-голямото известно просто число.

Редица без прости числа

Може да се намери произволно дълга крайна редица от последователни естествени числа, между които няма нито едно просто число. Такава редица може да има вида k!+2, k!+3, …, k!+k и съдържа k − 1 последователни съставни числа (удивителният знак означава факториел).

Например за k = 6 получаваме пет последователни съставни числа във вида: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Тези числа се делят съответно на две, три, четири, пет и шест, защото числото 6! = 720 със сигурност се дели на всички тези числа, тъй като е получено като тяхно произведение: 6! = 6 · 5 · 4 · 3 · 2. Ако числото 720 се дели на три, то и числото 720 + 3 трябва да се дели на три. Подобно е и при останалите.

Малка теорема на Ферма

За всяко просто число p и за всяко цяло число z числото z^p − z се дели на простото число p.

Пример: вземаме простото число p = 3 и цялото число z = 4. Пресмятаме стойността на числото 4³ − 4. То е равно на 60. При това 60/3 = 20, т.е. числото три дели 60 без остатък, което съответства на теоремата на Ферма. Друг пример: p = 7, z = 10. Пресмятаме междинния резултат 10⁷ − 10 = 9999990 и разделяме това число на седем: 9999990/7 = 1428570. Отново получихме резултат без остатък.

Нерешени въпроси

С простите числа са свързани много известни хипотези, които все още (2011 г.) не са били нито доказани, нито опровергани. Две от най-известните са:

• Безкрайност на простите числа близнаци: двойка прости числа близнаци е двойка числа (z; z + 2), като и двете числа са прости. Например (3; 5) или (29; 31). Въпросът е дали тези двойки са безкрайно много. Предполага се, че са, но доказателство няма.
• Хипотеза на Риман: всички нетривиални нули на дзета-функцията на Риман имат реална част, равна на $\frac{1}{2}$. Хипотезата е свързана с разпределението на простите числа и е един от така наречените проблеми на хилядолетието, а за решаването ѝ те очаква награда от един милион долара.