Просто число

от Уикипедия, свободната енциклопедия

В математиката, просто число се нарича всяко естествено число по-голямо от 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.

Съдържание

1 Представяне на естествените числа като произведение на прости
2 Колко са простите числа?
3 Намиране на прости числа
4 Някои свойства на простите числа
5 Нерешени проблеми
6 Най-голямото известно просто число
7 Приложения
8 Вижте също

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

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

$23244 = 2^2 \times 3 \times 13 \times 149 \,$

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

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

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

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

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

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

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

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

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

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

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

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

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

Ако p е просто и p дели произведението ab , където a и b са цели, то p дели a или p дели b. Това твърдение е доказано от Евклид и е известно като Лема на Евклид. Използва се за някои от доказателствата на единствеността на разлагане на прости множители.

Забележка: В сила е нещо повече. Нека за едно естествено число p>1 и за всеки две цели числа a и b, е вярно, че ако p дели произведението ab , то p дели a или p дели b. Тогава p e просто число. В някои изложения на елементарната аритметика, това свойство се използва за дефиниция на понятието просто число, а фактът, че простите числа имат точно два делителя се доказва в последствие.

Ако p е просто и a е произволно цяло, то a^p − 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 and q ≥ 1 са взаимнопрости, има безброй много прости (теорема на Дирихле за простите числа).
Законът за разпределение на простите числа гласи, че отношението между броя на простите числа по-малки от x и х е асимптотично на 1/ln x (тоест при големи x вероятността произволно избрано число по-малко от x да е просто е обратно пропорционална на броя на цифрите в x).

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

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

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

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

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

Хипотеза за простите близнаци: Има безброй много прости числа близнаци, тоест двойки от прости с разлика 2, като например 5 и 7, или 11 и 13.
Редицата на Фибоначи съдържа безброй много прости.
Има безброй много прости от вида n² + 1.
Хипотеза на Льожандър: Винаги има просто число межд n² и (n + 1)² за всяко n.
Хипотеза на Брокар: Винаги има поне четири прости числа между квадратите на последователни прости по-големи от 2.

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

Най-голямото известно просто число, към септември 2006 г. е $232582657 - 1$ (това число има 9 808 358 десетични цифри). То е 44-тото известно просто число на Мерсен M_32582657. е открито на 4 септември, 2006г. от Къртис Купър и Стивън Буун, професори, в Central Missouri State University.

От появата на компютрите почти всички най-големи прости са били мерсенови числа. Това е така, защото съществува изключително бърз алгоритъм за проверка на числа от този тип. Най-голямото известно просто, което не е мерсеново число е 27653 × 2^9167433 + 1 (2 759 677 цифри). То е шестото най-голямо просто число.

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

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