Прости числа: дефиниция, свойства и примери
Прости числа: ясна дефиниция, ключови свойства, проверени примери и исторически факти — идеално ръководство за ученици, студенти и любопитни умове.
Просто число е естествено число по-голямо от 1, което има точно два положителни делителя — 1 и самото себе си. Ако едно естествено число има повече от два положителни делителя, то се нарича съставно число. Например, най-малкото съставно число е 4, защото 2 × 2 = 4. Числото 1 не е просто и не е съставно. Най-малкото просто число е 2; следващите прости числа са 3, 5, 7, 11 и 13. Простите числа са всички естествени числа, различни от 1, които не могат да се представят като произведение на две по-големи от 1 числа (т.е. не могат да бъдат записани като 
, с изключение на случая 1 × 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) и техните предимства и недостатъци.
Ето още един начин да мислите за простите числа. Числото 12 не е просто, защото от него може да се направи правоъгълник със страни с дължини 4 и 3. Площта на този правоъгълник е 12, защото са използвани всичките 12 блокчета. Това не може да се направи с 11. Независимо от начина на подреждане на правоъгълника, винаги ще остават излишни блокчета, с изключение на правоъгълника със страни с дължини 11 и 1. 11 следователно трябва да е просто число.
Как да намерим малки прости числа
Съществува прост метод за намиране на списък с прости числа. Създал го е Ератостен. Наречен е Сито на Ератостен. Той улавя числата, които не са прости (като сито), и пропуска простите числа.
Методът работи със списък от числа и със специално число, наречено b, което се променя по време на метода. При преминаването през метода някои числа се ограждат в кръг, а други се зачеркват. Всяко обходено число е просто, а всяко зачеркнато число е съставно. В началото всички числа са обикновени: не са закръглени и не са зачеркнати.
Методът винаги е един и същ:
- На един лист хартия напишете всички цели числа от 2 до проверяваното число. Не записвайте числото 1. Преминете към следващата стъпка.
- Започнете с b, равно на 2, и преминете към следващата стъпка.
- Обърнете кръгче b в списъка. Преминете към следващата стъпка.
- Като започнете от b, пребройте още b в списъка и зачеркнете това число. Повторете броенето на още b числа и зачеркването им до края на списъка. Преминете към следващата стъпка.
- (Например: Когато b е 2, ще закръглите 2 и ще зачеркнете 4, 6, 8 и т.н. Когато b е 3, ще закръглите 3 и ще зачеркнете 6, 9, 12 и т.н. 6 и 12 вече са зачеркнати. Зачеркнете ги отново.)
- Увеличете b с 1. Преминете към следващата стъпка.
- Ако b е зачеркнато, върнете се към предишната стъпка. Ако b е число в списъка, което не е зачеркнато, преминете към 3-та стъпка. Ако b не е в списъка, преминете към последната стъпка.
- (Това е последната стъпка.) Готови сте. Всички прости числа са закръглени, а всички съставни числа са зачеркнати.
Например този метод може да се приложи за списък с числата от 2 до 10. В края на краищата числата 2, 3, 5 и 7 ще бъдат оградени с кръгчета. Това са прости числа. Числата 4, 6, 8, 9 и 10 ще бъдат зачеркнати. Това са съставни числа.
Този метод или алгоритъм отнема твърде много време за намиране на много големи прости числа. Въпреки това той не е толкова сложен, колкото методите, използвани за много големи прости числа, като например теста за първичност на Ферма (тест, с който се проверява дали дадено число е просто или не) и теста за първичност на Милър-Рабин.
За какво се използват простите числа
Първичните числа са много важни в математиката и информатиката. Много дълги числа са трудни за решаване. Трудно е да се намерят техните прости коефициенти, затова в повечето случаи числата, които вероятно са прости, се използват за криптиране и секретни кодове. Например:
- Повечето хора имат банкова карта, с която могат да теглят пари от сметката си чрез банкомат. Тази карта е защитена със секретен код за достъп. Тъй като кодът трябва да се пази в тайна, той не може да се съхранява в явен текст на картата. За тайното съхраняване на кода се използва криптиране. При това криптиране се използват умножения, деления и намиране на остатъци от големи прости числа. В практиката често се използва алгоритъм, наречен RSA. Той използва китайската теорема за остатъците.
- Ако някой има цифров подпис за своя имейл, се използва криптиране. Това гарантира, че никой не може да фалшифицира имейл от него. Преди подписването се създава хеш стойност на съобщението. След това тя се комбинира с цифровия подпис, за да се получи подписано съобщение. Използваните методи са повече или по-малко същите като в първия случай по-горе.
- С течение на годините намирането на най-голямото известно просто число се е превърнало в своеобразен спорт. Проверката дали едно число е просто може да бъде трудна, ако числото е голямо. Най-големите първични числа, известни във всеки един момент, обикновено са първични числа на Мерсен, тъй като най-бързият известен тест за първичност е тестът на Лукас-Лемер, който разчита на специалната форма на числата на Мерсен.
Свързани страници
- Коприме
- Списък на простите числа
- Палиндромно просто число
- Първична факторизация
- Wilson prime
Въпроси и отговори
Въпрос: Какво представлява простото число?
Отговор: Простото число е естествено число, което не може да се дели на други естествени числа, освен на 1 и на самото себе си.
В: Кое е най-малкото съставно число?
О: Най-малкото съставно число е 4, защото 2 x 2 = 4.
В: Кои са следващите прости числа след 2?
О: Следващите прости числа след 2 са 3, 5, 7, 11 и 13.
В: Има ли най-голямо просто число?
О: Не, няма най-голямо просто число. Множеството на простите числа е безкрайно.
В: Какво гласи фундаменталната теорема на аритметиката?
О: Фундаменталната теорема на аритметиката гласи, че всяко цяло положително число може да се запише като произведение на първични числа по уникален начин.
В: Какво представлява предположението на Голдбах?
О: Допускането на Голдбах е нерешен проблем в математиката, който гласи, че всяко четно цяло число, по-голямо от две, може да се изрази като сума от две първични числа.
В: Кой записва доказателство, че няма най-голямо просто число?
О: Евклид е записал доказателство, че няма най-голямо просто число.
обискирам