Просто число

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

В математиката просто число се нарича всяко естествено число, по-голямо от 1, което има точно два естествени делителя — 1 и самото себе си. Естествените числа, по-големи от едно, които не са прости, се наричат съставни. Числата нула и едно не са нито прости, нито съставни. Простите числа са един от основните обекти, които се изучават от теорията на числата.

Първите няколко прости числа са:

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, ...

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

Представяне на естествените числа като произведение на прости[редактиране | edit source]

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

23244 = 2^2 \times 37 \times 13 \times 149 \times 5,

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

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

Колко са простите числа?[редактиране | edit source]

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

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

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

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

Намиране на прости числа[редактиране | edit source]

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

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

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

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

Някои свойства на простите числа[редактиране | edit source]

  • Ако p е просто и p дели произведението ab , където a и b са цели, то p дели a или p дели b. Това твърдение е доказано от Евклид и е известно като лема на Евклид. Използва се за някои от доказателствата на единствеността на разлагане на прости множители.
Забележка: В сила е нещо повече. Нека за едно естествено число p>1 и за всеки две цели числа a и b е вярно, че ако p дели произведението ab , то p дели a или p дели b. В някои изложения на елементарната аритметика това свойство се използва за дефиниция на понятието просто число, а фактът, че простите числа имат точно два делителя, се доказва впоследствие.
  • Ако p е просто и a е произволно цяло число, то ap − 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).

Нерешени проблеми[редактиране | edit source]

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


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

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

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

Най-голямото известно просто число[редактиране | edit source]

Най-голямото известно просто число към януари 2013 г. е 257,885,161 − 1,[1] и се записва с 17,425,170 знака. То е число на Мерсен, както и следващите го десет най-големи прости числа.

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

  1. GIMPS Project Discovers Largest Known Prime Number, 257,885,161-1. // Mersenne Research, Inc..

Приложения[редактиране | edit source]

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

Източници[редактиране | edit source]


Вижте също[редактиране | edit source]