Просто число е естествено число по-голямо от 1, което има точно два положителни делителя — 1 и самото себе си. Ако едно естествено число има повече от два положителни делителя, то се нарича съставно число. Например, най-малкото съставно число е 4, защото 2 × 2 = 4. Числото 1 не е просто и не е съставно. Най-малкото просто число е 2; следващите прости числа са 3, 5, 7, 11 и 13. Простите числа са всички естествени числа, различни от 1, които не могат да се представят като произведение на две по-големи от 1 числа (т.е. не могат да бъдат записани като {\displaystyle m\times n}, с изключение на случая 1 × p). Множеството на простите числа често се означава с {\displaystyle \mathbb {P} }.

Фундаментална роля и основни свойства

Фундаменталната теорема на аритметиката гласи, че всяко положително цяло число > 1 може да се запише по единствен (с точност до реда на множителите) начин като произведение на прости числа. Това прави простите числа „строителните блокове“ на целите числа. Например: 84 = 2^2 × 3 × 7.

Някои важни свойства:

  • 1 не е просто. По историческа и аритметична причина 1 се изключва от множеството на простите числа.
  • 2 е единственото четно просто число. Всички други прости числа са нечетни (защото всяко четно число > 2 се дели на 2).
  • Прости числа са безкрайни — Евклид дава просто доказателство за това; вижте и историческите секиции по-долу.

Разпределение и известни теореми

Разпределението на простите числа сред естествените е тема на дълбоки изследвания. Теоремата за простите числа дава аппроксимация за броя на простите ≤ n: тя показва, че плътността на простите около n е приблизително 1 / ln(n). И все пак поведенито на простите на по-дребни разстояния и конкретни закономерности остава предмет на много изследвания.

Съществуват и важни нерешени проблеми, свързани с простите числа. Един от най-известните е предположението на Голдбах, според което всяко четно число по-голямо от 2 може да се представи като сума на две прости числа.

Как се проверява дали едно число е просто

За малки числа най-простият метод е делене на всички прости числа до квадратния корен на числото (т.нар. метод на пробното деление). Практически алгоритми и техники включват:

  • Ератостеново сито — ефективен начин за намиране на всички прости числа до дадено ограничение.
  • Пробно деление — проверява делимост само с прости делители ≤ √n.
  • Вероятностни тестове, като тестовете на Ферма, Майкълсън(Милър–Рабин) — бързи и практични, дават висока сигурност, но са вероятностни.
  • Детерминистични полиномни тестове, например алгоритъмът AKS — доказателствено полиномиално време за определяне на простота.

Примери

  • Първите прости числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
  • Пример за проверка: за да докажем, че 29 е просто, проверяваме делимост само с прости числа ≤ √29 (т.е. 2, 3, 5) — 29 не се дели на никое от тях, следователно е просто.
  • Пример за разлагане на съставно число по прости множители: 360 = 2^3 × 3^2 × 5.

История и големи прости числа

Евклид (Евклид) предоставя класическо доказателство за безкрайността на простите числа. Идеята му е да предположи, че има краен брой прости числа, да образува продукт на всички тях плюс 1 и да получи противоречие — полученото число ще има нов прост делител, различен от изброените.

На практика търсенето на много големи прости числа (особено мерсенски прости числа с формата 2^p − 1, където p е просто) продължава чрез големи международни проекти като GIMPS (Great Internet Mersenne Prime Search). Най-големите известни прости числа обикновено са мерсенски и се намират чрез комбиниране на ефективни тестове за простота и разпределени изчисления.

Защо простите числа са важни

Освен теоретичния интерес, простите числа имат практическо приложение, най-вече в криптографията — например в RSA криптосистемата, където големи прости числа и тяхното уникално разлагане са основа за сигурността. Изследванията върху свойствата и разпределението на простите също водят до развитие на алгоритми и числени методи, които намират приложения в различни области на науката и техниката.

Ако желаете, мога да добавя още примери за методи за разлагане, подробности за доказателството на Евклид, или описание на конкретни алгоритми (Ератостеново сито, Милър–Рабин, AKS) и техните предимства и недостатъци.