SR
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms
Прост број

Прост број

From Wikipedia, the free encyclopedia

Прост број
ДефиницијаОсновна теорема аритметикеРастављање сложених бројева на просте фактореЕратостеново ситоКриптографијаБројност простих бројеваГустина расподеле простих бројеваДирихлова теоремаЕуклидова теоремаНајвећи познати прост бројПримена простих бројеваВиди јошРеференцеЛитератураСпољашње везеГенератори и калкулатори
За другу употребу, погледајте чланак Број (вишезначна одредница).

Прост број је природан број већи од 1, дељив само бројем 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 {\displaystyle a\,} {\displaystyle a\,} је нерастављив број ако важи: a = k ⋅ l ⇒ a = k ∨ a = l {\displaystyle a=k\cdot l\Rightarrow a=k\lor a=l} {\displaystyle a=k\cdot l\Rightarrow a=k\lor a=l}. Број a {\displaystyle a\,} {\displaystyle a\,} је прост број ако важи: a {\displaystyle a\,} {\displaystyle a\,} дели p ⋅ q ⇒ a {\displaystyle p\cdot q\Rightarrow a\,} {\displaystyle p\cdot q\Rightarrow a\,} дели p {\displaystyle p\,} {\displaystyle p\,} или a {\displaystyle a\,} {\displaystyle a\,} дели q {\displaystyle q\,} {\displaystyle q\,}. Лако се може показати да ако је број прост онда је и нерастављив и обрнуто, тј. то су два еквивалентна појма. Особине простих бројева изучава област која се зове теорија бројева. Број који поред 1 (јединице) има још делилаца се назива сложен број. То је појам супротан простом, у смислу дељивости. Синоним за прост број је прим број.

Thumb
Природни бројеви од 0 до 100. Прости бројеви су означени црвеном бојом.
Thumb
Прости бројеви су природни бројеви већи од један који нису производи два мања броја.
Thumb
12 : 3 = 4 {\displaystyle 12:3=4} {\displaystyle 12:3=4}, 11 {\displaystyle 11} {\displaystyle 11} је прост број

Природни број (1, 2, 3, 4, 5, 6, etc.) се зове прост број, ако је већи од 1 и ако се не може записати као производ два природна броја која су мања од њега. Бројеви већи од 1 који нису прости бројеви се зову сложеним бројевима.[2] Другим речима, n {\displaystyle n} {\displaystyle n} је прост, ако се n {\displaystyle n} {\displaystyle n} ставки не може поделити на мање групе једнаке величине са више од једне ставке,[3] или ако није могуће организовати n {\displaystyle n} {\displaystyle n} тачки на правоугаоној решетци тако да је више од једне тачке широка или више од једне тачке висока.[4] На пример, међу бројевима од 1 до 6, бројеви 2, 3, и 5 су прости бројеви,[5] јер нема других бројева који их равномерно деле (без остатка). Исто тако, број 12 није прост, јер се 12 може поделити у 3 колоне по 4 елемента. Број 11 се може сместити само у једну или 11 колона од по 11 односно 1 елеменат, тј 11 је прост број.

Из наведеног се види да су природни бројеви подељени у три класе.

  • Број 1
  • Прости бројеви
  • Сложени бројеви

У скупу природних бројева број 1 {\displaystyle 1} {\displaystyle 1} има посебан положај, и зато је издвојен у посебну класу. Дељивост у скупу N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } може се проширити на скуп N 0 {\displaystyle \mathbb {N} _{0}} {\displaystyle \mathbb {N} _{0}} и рећи да је 0 {\displaystyle 0} {\displaystyle 0} дељива са сваким природним бројем, јер је 0 = a × 0 {\displaystyle 0=a\times 0} {\displaystyle 0=a\times 0}. Број 0 {\displaystyle 0} {\displaystyle 0} није ни прост ни сложен број.

Ово се може рећи на још један начин: број n > 1 {\displaystyle n>1} {\displaystyle n>1} је прост, ако се може написати као производ два природна броја a {\displaystyle a} {\displaystyle a} и b {\displaystyle b} {\displaystyle b}, који су већи од 1 {\displaystyle 1} {\displaystyle 1}

n = a × b {\displaystyle n=a\times b} {\displaystyle n=a\times b}

Сви прости бројеви мањи од 1000 су:

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, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997[6]

За сваки природни број n {\displaystyle n} {\displaystyle n} ( n > 1 {\displaystyle n>1} {\displaystyle n>1}) постоји јединствен растав на просте факторе n = p 1 a 1 × p 2 a 2 × . . . × p k a k {\displaystyle n={p_{1}}^{a_{1}}\times {p_{2}}^{a_{2}}\times ...\times {p_{k}}^{a_{k}}} {\displaystyle n={p_{1}}^{a_{1}}\times {p_{2}}^{a_{2}}\times ...\times {p_{k}}^{a_{k}}}

Где су p 1 < p 2 < . . . < p k {\displaystyle p_{1}<p_{2}<...<p_{k}} {\displaystyle p_{1}<p_{2}<...<p_{k}} те су сви p i {\displaystyle p_{i}} {\displaystyle p_{i}} прости бројеви.

Пример

23244 = 2 × 2 × 3 × 13 × 149 = 2 2 × 3 × 13 × 149 {\displaystyle 23244=2\times 2\times 3\times 13\times 149=2^{2}\times 3\times 13\times 149} {\displaystyle 23244=2\times 2\times 3\times 13\times 149=2^{2}\times 3\times 13\times 149}

1200 = 2 4 × 3 1 × 5 2 = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 {\displaystyle 1200=2^{4}\times 3^{1}\times 5^{2}=3\times 2\times 2\times 2\times 2\times 5\times 5=5\times 2\times 3\times 2\times 5\times 2\times 2} {\displaystyle 1200=2^{4}\times 3^{1}\times 5^{2}=3\times 2\times 2\times 2\times 2\times 5\times 5=5\times 2\times 3\times 2\times 5\times 2\times 2}

Растављање се може постићи дељењем с простим бројевима, и уз познавање неколико једноставних правила, то растављање постаје врло једноставно.

  • Ако је број паран (задња цифра му је 2, 4, 6, 8 или 0) онда је дељив с бројем 2.
  • Ако број завршава цифрама 5 или 0 онда је дељив с бројем 5.
  • Ако му је збир цифара дељив с 3, онда је тај број дељив с 3.
Главни чланак: Ератостеново сито

Ово је механички поступак проналажења простих бројева који нису већи од . Испишу се сви бројеве од 2 до н. Пође се од броја 2 и прецрта се сваки други број, затим се пође од броја 3 и прецрта се сваки трећи с тиме да се броје и прецртани бројеви, па од првог непрецртаног броја итд. Овај поступак се понавља док не дође до броја за који је . Непрецртани бројеви су прости. Пример за n = 20 {\displaystyle n=20} {\displaystyle n=20}:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Важна примена простих бројева је у области криптографије. Алгоритми за шифрирање поруке зависе од тога што не постоји ефикасан алгоритам за растављање броја на просте факторе. Тако се лако могу помножити два довољно велика проста броја, међутим, обрнути процес, тј. налажење његових простих фактора траје доста дуже. Позната шифра која на томе базира је .[7]

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

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

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

lim x → ∞ ∑ p < x 1 p   ∼   ln ⁡ ln ⁡ x {\displaystyle \lim _{x\to \infty }\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x} {\displaystyle \lim _{x\to \infty }\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x}

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

π ( x ) ∼ x ln ⁡ x − 1 {\displaystyle \pi (x)\sim {\frac {x}{\ln x-1}}} {\displaystyle \pi (x)\sim {\frac {x}{\ln x-1}}}.

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

Више информација има простих бројева ...
Мањих од броја има простих бројева π ( x ) {\displaystyle \pi (x)} {\displaystyle \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
Затвори

Посматрајмо однос густине простих бројева мањих од неког броја и реципрочне вредности природног логаритма тог броја. Густина простих бројева у скупу N {\displaystyle \mathbb {N} } {\displaystyle \mathbb {N} } опада као и реципрочна вредност природног логаритма броја , за велике вредности ( k / m → 1 {\displaystyle k/m\to 1} {\displaystyle k/m\to 1}).

Више информација , ...
k = π ( n ) / n {\displaystyle k=\pi (n)/n} {\displaystyle k=\pi (n)/n} m = 1 / l n ( n ) {\displaystyle m=1/ln(n)} {\displaystyle m=1/ln(n)} k / m {\displaystyle k/m} {\displaystyle k/m}
10 3 {\displaystyle 10^{3}} {\displaystyle 10^{3}}0,1680,14481,16022
10 6 {\displaystyle 10^{6}} {\displaystyle 10^{6}}0,0784980,07238241,08449
10 9 {\displaystyle 10^{9}} {\displaystyle 10^{9}}0,0508475340,0482549421,05372
10 12 {\displaystyle 10^{12}} {\displaystyle 10^{12}}0,0376079120180,036191206821,03914
10 24 {\displaystyle 10^{24}} {\displaystyle 10^{24}}0,0184355997673490,0180956034126351,018788
Затвори

Нека су и природни бројеви такви да је њихова мера ( d , a ) = 1 {\displaystyle (d,a)=1} {\displaystyle (d,a)=1}, тј. они су релативно прости, тада постоји бесконачно много прим бројева облика d n + a {\displaystyle dn+a} {\displaystyle dn+a}, n ∈ N 0 {\displaystyle n\in N_{0}} {\displaystyle n\in N_{0}}, tј. постоји бесконачно много прим бројева у аритметичком низу a ,   d + a ,   2 d + a ,   3 d +   a . . . {\displaystyle a,\ d+a,\ 2d+a,\ 3d+\ a...} {\displaystyle a,\ d+a,\ 2d+a,\ 3d+\ a...}

Прости бројеви 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … у аритметичким низу

1 + 2 n {\displaystyle 1+2n} {\displaystyle 1+2n}

Прости бројеви 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, … у аритметичким низу 1 + 4 n {\displaystyle 1+4n} {\displaystyle 1+4n}
Прости бројеви 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, … у аритметичким низу 3 + 4 n {\displaystyle 3+4n} {\displaystyle 3+4n}

Скуп свих простих бројева је бесконачан.

Доказ за неке опште аритметичке низове. Сваки прост број већи од 2 је непаран, те је облика 4 n + 3 {\displaystyle 4n+3} {\displaystyle 4n+3} или 4 n + 1 {\displaystyle 4n+1} {\displaystyle 4n+1}. Производ два броја облика 4 n + 1 {\displaystyle 4n+1} {\displaystyle 4n+1} такође је тог облика:

( 4 a + 1 ) ( 4 b + 1 ) = 16 a b + 4 a + 4 b + 1 = 4 ( 4 a b + a + b ) + 1 {\displaystyle (4a+1)(4b+1)=16ab+4a+4b+1=4(4ab+a+b)+1} {\displaystyle (4a+1)(4b+1)=16ab+4a+4b+1=4(4ab+a+b)+1}

Претпоставимо да постоји коначно много простих бројева

p 1 , p 2 , . . . , p n {\displaystyle p_{1},p_{2},...,p_{n}} {\displaystyle p_{1},p_{2},...,p_{n}} koji su oblika 4 n + 3 {\displaystyle 4n+3} {\displaystyle 4n+3}.
N = 4 × p 1 × p 2 × . . . × p n − 1 = 4 × ( p 1 × p 2 × . . . × p n − 1 ) + 3 {\displaystyle N=4\times p_{1}\times p_{2}\times ...\times p_{n}-1=4\times (p_{1}\times p_{2}\times ...\times p_{n}-1)+3} {\displaystyle N=4\times p_{1}\times p_{2}\times ...\times p_{n}-1=4\times (p_{1}\times p_{2}\times ...\times p_{n}-1)+3}

је прост број, или се може раставити на производ простих бројева, од којих ниједан није p 1 , p 2 , . . . , p n {\displaystyle p_{1},p_{2},...,p_{n}} {\displaystyle p_{1},p_{2},...,p_{n}} јер остатак дељења броја са неким од бројева је -1. Сви прости фактори броја не могу бити облика 4 n + 1 {\displaystyle 4n+1} {\displaystyle 4n+1}, јер није тог облика. Као што смо видели, производ бројева облика 4 n + 1 {\displaystyle 4n+1} {\displaystyle 4n+1} је такође је број тог облика.

Према томе, бар један прост фактор мора бити облика 4 n + 3 {\displaystyle 4n+3} {\displaystyle 4n+3}, што је немогуће, јер тај фактор није ниједан од бројева , за које смо претпоставили да су сви прости бројеви облика 4 n + 3 {\displaystyle 4n+3} {\displaystyle 4n+3}.

Дакле, број простих бројева таквог облика је бесконачан.

Последица Дирихлове теореме је

Ред реципрочних простих бројева облика 4 n + 3 {\displaystyle 4n+3} {\displaystyle 4n+3}

1 3 + 1 7 + 1 11 + 1 19 + . . . {\displaystyle {\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{11}}+{\frac {1}{19}}+...} {\displaystyle {\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{11}}+{\frac {1}{19}}+...} дивергира

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

Претходни највећи познати прост број је био 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). Број n такав да је binomial(n+k-1,k) k-алмоуст прајм (има тачно n простих фактора) је k-полипрост.

  • Узајамно прости бројеви
  • Списак простих бројева
  • Дељивост
  • Факторизација
  • Ератостеново сито
  • Еуклидов алгоритам
  1. [1]
    Ziegler, Günter M. (2004). „The great prime number record races”. Notices of the American Mathematical Society. 51 (4): 414—416. MR 2039814.
  2. [2]
    Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Oxford University Press. стр. 26. ISBN 978-0-19-850105-3.
  3. [3]
    Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd изд.). Routledge. стр. 62. ISBN 978-1-136-63662-2.
  4. [4]
    Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. стр. 16. OCLC 6975809.
  5. [5]
    Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. стр. 360. ISBN 978-0-7641-0768-9.
  6. [6]
    A000040
  7. [7]
    RSA . Kurs na nemačkoj gimnaziji u Berlinu Архивирано на сајту (12. новембар 2016) učitano 18.01.2014 njem.
  • Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. стр. 360. ISBN 978-0-7641-0768-9.
  • Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. стр. 16. OCLC 6975809.
  • Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd изд.). Routledge. стр. 62. ISBN 978-1-136-63662-2.
  • Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Oxford University Press. стр. 26. ISBN 978-0-19-850105-3.
Прост број на Викимедијиној остави.
  • Hazewinkel Michiel, ур. (2001). „Prime number”. Encyclopaedia of Mathematics. Springer. 978-1556080104.
  • Prime Numbers on In Our Time at the BBC.

Генератори и калкулатори

Edit in WikipediaRevision historyRead in Wikipedia

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox

Дефиниција

Основна теорема аритметике

Растављање сложених бројева на просте факторе

Ератостеново сито

Криптографија

Бројност простих бројева

Густина расподеле простих бројева

Дирихлова теорема

Еуклидова теорема

Највећи познати прост број

Примена простих бројева

Види још

Референце

Литература

Спољашње везе