Просто число е естествено число, по-голямо от 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 ще бъде идентично на горното с изключение на реда на множителите. Вижте алгоритъм за разлагане на прости множители за повече подробности относно това, как на практика се разлагат големи естествени числа.
Важността на тази теорема е една от причините, поради които 1 се изключва от множеството на простите числа. Ако приемем 1 за просто, теоремата ще изисква допълнителни уточнения.
Има безброй много прости числа. Най-старото известно доказателство на този факт е дадено от гръцкия математик Евклид в книгата му Елементи. Твърдението на Евклид е "броят на простите числа е по-голям от всяко отнапред зададено [крайно] число", и неговото доказателство по същество е следното:
Други математици са представяли свои собствени доказателства. Едно от тях (принадлежащо на Ойлер) показва, че сумата от реципрочните на всички прости числа клони към безкрайност. Доказателството на Кумер е особено елегантно, а това на Фурстенберг използва обща топология.
Въпреки че има безбройно много прости, възникват други въпроси относно броя им – например „Колко приблизително са простите числа, по-малки от 100 000“ или „Каква е вероятността произволно стоцифрено число да е просто?“ Отговорът на тези и други въпроси се дава от закона за разпределение на простите числа, (Съвременните компютри позволяват сравнително бързо да се отговори точно на първия въпрос; отговорът е 9592, като най-голямото просто е 99991.)
Решетото на Ератостен е прост начин, а решетото на Аткин е бърз начин да се намери списъкът на всички прости числа, по-малки от някое отнапред зададено число.
На практика обаче по-често се налага да се провери дали дадено число е просто, отколкото да се намери списък с прости числа. Често дори е достатъчно да се знае отговорът на горния въпрос с достатъчно голяма вероятност. Възможно е бързо да се провери дали дадено голямо число (например до хиляда цифри) е просто, използвайки вероятностни тестове.
Един начин за установяване дали едно число е просто е, като се провери дали се дели на някое от простите числа, по-малки от квадратния му корен. Ако не се дели на нито едно от тях, то е просто. Това е най-елементарният известен тест, но той не е практичен за големи числа, тъй като броят на възможните делители нараства експоненциално, когато броят на цифрите на числото се увеличава.
През 2002 година индийски учени от IIT Kanpur откриват нов детерминистичен алгоритъм, който проверява дали дадено число N е просто, като времето, необходимо за изчисление, е полиномиална функция на броя на цифрите на N.
Има много нерешени въпроси, свързани с простите числа. Най-важният от тях е хипотезата на Риман, която в общи линии твърди, че простите числа са разпределени максимално равномерно. Повечето математици считат, че хипотезата е вярна.
Други хипотези:
Малко по-слабото твърдение – така наречената тернарна хипотеза на Голдбах, твърди, че всяко нечетно число, по-голямо от 7, може да се представи като сума на три нечетни прости. Тази хипотеза е доказана от Виноградов през 1937 година.
Най-голямото известно просто число към октомври 2019 г. е 282 589 933 − 1, и се записва с 24 862 048 знака. То е число на Мерсен, както и следващите го единадесет най-големи прости числа.
След появата на компютрите почти всички намерени най-големи прости числа са били мерсенови числа. Това е така, защото съществува изключително бърз алгоритъм за проверка на числа от този тип. Най-голямото известно просто число, което не е мерсеново число, е единадесетото по големина.
Изключително големи прости (тоест по-големи от 10100) се използват в някои алгоритми в криптографията. Прости числа също се използват за хеш таблици и генератори на псевдослучайни числа.
This article uses material from the Wikipedia Български article Просто число, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Съдържанието е достъпно под условията на лиценза CC BY-SA 4.0, освен ако не е посочено друго. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Български (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.