Прост број

Из Википедије, слободне енциклопедије
Disambig.svg
За другу употребу, погледајте чланак Број (вишезначна одредница).

Прост број је природан број већи од 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,...


Број a\, је нерастављив број ако важи: a=k \cdot l \Rightarrow a=k \lor a=l.

Број a \, је прост број ако важи: a \, дели p \cdot q \Rightarrow a \, дели p \, или a \, дели q \,.

Лако се може показати да ако је број прост онда је и нерастављив и обрнуто, тј. то су два еквивалентна појма! Особине простих бројева изучава област која се зове теорија бројева.

Број који поред 1 (јединице) има још делилаца се назива сложен број. То је појам супротан простом, у смислу дељивости.

Синоним за прост број је прим број.

Бројност простих бројева[уреди]

Простих бројева има бесконачно много. Ово је први доказао Еуклид у својим Елементима, књига X, Теорема 20. Његов доказ је следећи:

Претпоставимо да је број простих бројева коначан. Помножимо их све и додајмо 1. Добићемо број који дељен са било којим простим бројем даје остатак 1. Дакле добили смо број који нема делитеља међу постојећим бројевима. То јесте прост број већи од претходних.

Математичари су открили још особина које су везане за бројност простих бројева. Ојлер је открио да ред реципрочних простих бројева дивергира. Чак је нађена асимптотска формула за збир простих бројева мањих од неког датог

\lim_{x\to\infty} \sum_{p<x} \frac{1}{p}\ \sim\ \ln \ln x

У математици постоји функција \pi (x) \, чија је вредност једнака броју простих бројева у интервалу (1, x] \,. Она даје одговор на питање колико има простих бројева мањих од неког датог. Тако је \pi (100000) = 9592\,. Функција се за веће бројеве може апроксимирати следећим изразом

\pi (x) \sim \frac{x}{\ln x - 1}.

Број простих бројева у неком опсегу се може видети из следеће таблице

Мањих од броја има простих бројева \pi (x)
10 4
100 25
1.000 168
10.000 1.229
100.000 9.592
1.000.000 78.498
10.000.000 664.579
100.000.000 5.761.455
1.000.000.000 50.847.534
10.000.000.000 455.052.511
100.000.000.000 4.118.054.813
1.000.000.000.000 37.607.912.018
10.000.000.000.000 346.065.536.839
100.000.000.000.000 3.204.941.750.802
1.000.000.000.000.000 29.844.570.422.669
10.000.000.000.000.000 279.238.341.033.925
100.000.000.000.000.000 2.623.557.157.654.233
1.000.000.000.000.000.000 24.739.954.287.740.860
10.000.000.000.000.000.000 234.057.667.276.344.607
100.000.000.000.000.000.000 2.220.819.602.560.918.840
1.000.000.000.000.000.000.000 21.127.269.486.018.731.928
10.000.000.000.000.000.000.000 201.467.286.689.315.906.290

Највећи познати прост број[уреди]

Тренутно највећи познати прост број је 230.402.457 − 1 (овај број има 9.152.052 цифара). Израчунали су га 15. децембра 2005. године два професора са Мисури државног универзитета. Означава се са М30402457 и представља 43. Мерсенов прост број.

Претходни највећи познати прост број је био M25964951 = 225.964.951 − 1 (42. познати Мерсенов прост број, 7.816.230 цифара) а пре њега M24036583 = 224.036.583 − 1 (41. познати Мерсенов прост број, 7.235.733 цифара)

Постоји добар практичан разлог зашто су сви велики прости бројеви облика Мерсенових простих бројева. То је релативно једноставан метод за проверу сложености броја (Лукас-Лемер тест). За остале бројеве је метода временски захтевна.

Највећи прост број који није овог облика је 27.653 × 29.167.433 + 1 (2.759.677 цифара) и шести је по величини на листи највећих познатих простих бројева.

За налажење простог броја са 107 децималних цифара постоји награда од 100000 долара.

Примена простих бројева[уреди]

Чињеница да је проблем налажења свих делитеља великог броја је довео до проналажења метода за шифровање који се користи великим простим бројевима. У оваквој криптографији са јавним кључем је изузетно важно имати метод за генерисање великог простог броја (реда 10300).

Види још[уреди]

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Прост број