Prímszám - Prime number

Az összetett számok téglalapokba rendezhetők, de a prímszámok nem

A prímszám (vagy elsődleges ) egy természetes szám nagyobb, mint 1, amely nem a termék a két kisebb természetes számok. Az 1-nél nagyobb természetes számot, amely nem prímszám, összetett számnak nevezzük . Például az 5 prímszámú, mert az 1 × 5 vagy 5 × 1 szorzatként való írásának egyetlen módja magában foglalja az 5-öt. Azonban, 4 kompozit, mert ez egy termék ( 2 × 2 ), amelyben a két szám kisebb, mint 4. Primes központi szerepet számelmélet miatt a számelmélet alaptétele : Minden természetes szám nagyobb, mint 1, vagy egy elsődleges maga, vagy lehet szorzottmint a termék prímszám, amely egyedi akár azok sorrendjét.

A prímság tulajdonságát primalitásnak nevezzük . Egy egyszerű, de lassú módszer ellenőrzése a primality egy adott számú , az úgynevezett tárgyalás Division , tesztek akár többszöröse közötti bármely egész szám 2 és . A gyorsabb algoritmusok közé tartozik a Miller–Rabin primalitásteszt , amely gyors, de kicsi a hibalehetősége, és az AKS primalitásteszt , amely mindig polinomiális időben adja meg a helyes választ, de túl lassú ahhoz, hogy gyakorlatias legyen. Különösen gyors módszerek állnak rendelkezésre számos speciális alakzathoz, például a Mersenne-számokhoz . 2018 decemberében a legnagyobb ismert prímszám egy Mersenne-prím 24 862 048 tizedesjegyből áll . ${\displaystyle n}$${\displaystyle n}$${\displaystyle {\sqrt {n}}}$

Vannak végtelen sok prímszám, mivel bizonyítja Euclid ie 300 körül. Egyetlen ismert egyszerű képlet sem választja el a prímszámokat az összetett számoktól. A természetes számokon belüli prímszámok eloszlása ​​azonban a nagyban statisztikailag modellezhető. Az első eredmény ebben az irányban a 19. század végén bizonyított prímszámtétel , amely szerint annak valószínűsége, hogy egy véletlenszerűen kiválasztott nagy szám prím legyen, fordítottan arányos a számjegyeinek számával, vagyis a logaritmusával .

Számos történelmi kérdés a prímszámokkal kapcsolatban még mindig megválaszolatlan. Ide tartozik a Goldbach-sejtés , amely szerint minden 2-nél nagyobb páros egész két prímszám összegeként fejezhető ki, valamint az ikerprím- sejtés, miszerint végtelen sok olyan prímpár van, amelyek között csak egy páros szám van. Az ilyen kérdések ösztönözték a számelmélet különböző ágainak fejlődését, amelyek a számok analitikai vagy algebrai vonatkozásaira összpontosítottak . Prímszám használják több rutint informatikai , például nyilvános kulcsú titkosítás , amely támaszkodik a nehézségi faktoring nagyszámú be az elsődleges tényezők. Az absztrakt algebra , kifogásolja, hogy viselkedik, általánosított módon, mint a prímszámok közé elsődleges elemek és prime eszméket .

Definíció és példák

Egy természetes számot (1, 2, 3, 4, 5, 6 stb.) prímszámnak (vagy prímnek ) nevezünk, ha nagyobb 1-nél, és nem írható fel két kisebb természetes szám szorzataként. Az 1-nél nagyobb számokat, amelyek nem prímszámok, összetett számoknak nevezzük . Más szóval prím, ha az elemek nem oszthatók fel egynél több elemből álló kisebb, egyenlő méretű csoportokra, vagy ha nem lehet pontokat egynél több pont széles és több pont magas téglalap alakú rácsba rendezni. . Például az 1-től 6-ig terjedő számok között a 2, 3 és 5 a prímszámok, mivel nincs más olyan szám, amely egyenlően (maradék nélkül) osztaná el őket. Az 1 nem prímszám, mivel a definícióban kifejezetten ki van zárva. A 4 = 2 × 2 és a 6 = 2 × 3 egyaránt összetett. ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

Cuisenaire rudak bemutatása, hogy a 7 a príma , mert a 2, 3, 4, 5 vagy 6 egyike sem osztja el egyenletesen

A természetes szám osztói az egyenletesen osztódó természetes számok . Minden természetes számnak osztója van 1-nek és önmagának is. Ha van más osztója, az nem lehet prím. Ez a gondolat a prímszámok eltérő, de egyenértékű meghatározásához vezet: ezek pontosan két pozitív osztójú számok , 1 és maga a szám. Ugyanennek a kifejezésének egy másik módja az, hogy egy szám akkor prím, ha nagyobb egynél, és ha egyik szám sem osztódik egyenletesen. ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2,3,\dots ,n-1}$${\displaystyle n}$

Az első 25 prímszám (minden 100-nál kisebb prímszám):

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 ( A000040 sorozat az OEIS-ben ).

A 2-nél nagyobb páros szám nem prím, mert bármely ilyen szám kifejezhető szorzatként . Ezért minden 2-től eltérő prímszám páratlan szám , és páratlan prímnek nevezzük . Hasonlóképpen, ha a szokásos decimális rendszerben írjuk le , minden 5-nél nagyobb prímszám 1-re, 3-ra, 7-re vagy 9-re végződik. A többi számjegyre végződő számok mind összetettek: 0, 2, 4, 6-ra végződő decimális számok , vagy 8 páros, és a 0-ra vagy 5-re végződő decimális számok oszthatók 5-tel. ${\displaystyle n}$${\displaystyle 2\times n/2}$

A készlet az összes prímszám néha jelöli (a félkövér tőke P ) vagy (a táblára félkövér nagybetűvel). ${\displaystyle \mathbf {P} }$${\displaystyle \mathbb {P} }$

Történelem

A Rhind matematikai papirusz

Az ie 1550 körüli Rhind matematikai papirusz különböző formájú egyiptomi törtkiterjesztéseket tartalmaz prím- és összetett számokhoz. A prímszámok explicit tanulmányozásának legkorábbi fennmaradt feljegyzései azonban az ókori görög matematikából származnak . Euclid „s Elements (c. Ie 300) bizonyítja a végtelen prímszám és a számelmélet alaptétele , és azt mutatja, hogyan kell építeni egy tökéletes szám egy Mersenne prím . Egy másik görög találmányt, az Eratoszthenész szitáját még mindig használják prímek listáinak összeállítására.

1000 körül Ibn al-Haytham (Alhazen) iszlám matematikus megtalálta Wilson tételét , amely a prímszámokat egyenletesen osztó számokként jellemezte . Azt is sejtette, hogy minden tökéletes szám Eukleidész Mersenne-prímeket használó konstrukciójából származik, de nem tudta bizonyítani. Egy másik iszlám matematikus, Ibn al-Banna' al-Marrakushi megfigyelte, hogy Eratoszthenész szitája felgyorsítható, ha csak az osztókat teszteljük a legnagyobb vizsgálandó szám négyzetgyökéig. Fibonacci visszahozta Európába az iszlám matematikából származó újításokat. Című könyvében Liber Abaci (1202) volt az első, aki leírja tárgyalás osztály tesztelésére primality, ismét osztók csupán a négyzetgyök. ${\displaystyle n}$${\displaystyle (n-1)!+1}$

1640-ben Pierre de Fermat kijelentette (bizonyítás nélkül) Fermat kis tételét (amit később Leibniz és Euler igazolt ). Fermat is vizsgáltuk primality a Fermat számok , és Marin Mersenne tanulmányozta a Mersenne prím , prímszám a forma a maga elsődleges. Christian Goldbach egy 1742-es Euler-levélben fogalmazta meg Goldbach sejtését , miszerint minden páros szám két prímszám összege. Euler bebizonyította Alhazen sejtését (ma Euklidész–Euler-tétel ), miszerint minden tökéletes szám megszerkeszthető Mersenne-prímekből. A prímszámok végtelenségének és a prímszámok reciprokösszegének divergenciájának bizonyítása során a matematikai elemzés módszereit vezette be erre a területre . Elején a 19. században, Legendre és Gauss azt sejtette, hogy a tart végtelenbe, a szám prímszám-ig van aszimptotikus az , ahol a természetes logaritmus az . A gyengébb Ennek következtében nagy sűrűségű prímszám volt Bertrand posztulátum , hogy minden van egy fő közötti és bizonyult 1852-ben Pafnutyij Lvovics Csebisev . Bernhard Riemann ötletei a zéta-függvényről írt 1859-es tanulmányában vázlatot vázoltak fel Legendre és Gauss sejtésének bizonyítására. Bár a szorosan kapcsolódó Riemann-hipotézis továbbra is bizonyítatlan, Riemann vázlatát 1896-ban fejezte be Hadamard és de la Vallée Poussin , és az eredményt ma prímszámtételként ismerik . Egy másik fontos 19. századi eredmény Dirichlet aritmetikai sorozatokról szóló tétele volt , miszerint bizonyos számtani sorozatok végtelen sok prímszámot tartalmaznak. ${\displaystyle 2^{2^{n}}+1}$${\displaystyle 2^{p}-1}$${\displaystyle p}$ ${\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots }$${\displaystyle x}$${\displaystyle x}$${\displaystyle x/\log x}$${\displaystyle \log x}$${\displaystyle x}$${\displaystyle n>1}$${\displaystyle n}$${\displaystyle 2n}$

Sok matematikus dolgozott olyan primalitásteszteken, amelyek nagyobb számokra vonatkoznak, mint azok, ahol a próbaosztás gyakorlatilag alkalmazható. A meghatározott számformákra korlátozódó módszerek közé tartozik a Pépin-féle Fermat -teszt (1877), a Proth-tétel (1878 körül), a Lucas–Lehmer primalitásteszt (1856-ból) és az általánosított Lucas-primalitásteszt .

1951 óta az összes ismert legnagyobb prímszámot ezekkel a tesztekkel találták meg számítógépeken . Az egyre nagyobb prímszámok keresése a matematikai körökön kívül is érdeklődést váltott ki, a Great Internet Mersenne Prime Search és más elosztott számítási projektek révén. Az az elképzelés, hogy a prímszámoknak a tiszta matematikán kívül kevés alkalmazása van, az 1970 - es években összetört, amikor feltalálták a nyilvános kulcsú kriptográfiát és az RSA titkosítási rendszert, amelyek prímszámokat vettek alapul.

A számítógépes primalitásteszt és a faktorizáció megnövekedett gyakorlati jelentősége olyan továbbfejlesztett módszerek kifejlesztéséhez vezetett, amelyek nagyszámú korlátlan forma kezelésére alkalmasak. A matematikai elmélete prímszámok is előrelépett a Green-Tao-tétel (2004), hogy vannak tetszőlegesen hosszú számtani sorozat prímszámok, és Yitang Zhang „s 2013 bizonyíték, hogy létezik végtelen sok prím hiányosságok korlátos méretű.

Az egyik elsődlegessége

A legtöbb korai görög még az 1-et sem tekintette számnak, így nem tudták figyelembe venni elsődlegességét. Ebből az időből néhány matematikus a prímszámokat is a páratlan számok felosztásának tekintette, így a 2-t sem tekintették prímnek. Eukleidész és a többi görög matematikus többsége azonban a 2-t prímszámnak tekintette. A középkori iszlám matematikusok nagyrészt követték a görögöket abban, hogy az 1-et nem számnak tekintették. A középkorban és a reneszánszban a matematikusok az 1-et kezdték számként kezelni, és néhányan az első prímszámként vették fel. A 18. század közepén Christian Goldbach a Leonhard Eulerrel folytatott levelezésében az 1-et elsőszámúként jelölte meg ; maga Euler azonban nem tartotta prímnek az 1-et. A 19. században sok matematikus még mindig az 1-est tartotta prímszámnak, és az 1-est tartalmazó prímszámok listáit 1956-ban is közzétették.

Ha a prímszám definícióját úgy változtatnánk meg, hogy az 1-et prímnek nevezzük, akkor sok prímszámokat tartalmazó állítást kínosabb módon kellene átfogalmazni. Például az aritmetika alaptételét 1-nél nagyobb prímszámokká kellene átfogalmazni, mert minden számnak több faktorizálása lenne 1-nek különböző példányszámaival. Hasonlóképpen, Eratoszthenész szitája sem működne megfelelően, ha prímként kezeli az 1-et, mert az 1 összes többszörösét (vagyis az összes többi számot) kiiktatja, és csak az 1-es számot adja ki. A prímszámok egyéb technikai jellemzői szintén nem érvényesek az 1-re: pl. az Euler-féle totient függvény vagy az osztók összege függvényének képletei eltérnek prímszámokra, mint 1-re. A 20. század elejére a matematikusok egyetértettek abban, hogy az 1-et nem prímként kell feltüntetni, hanem inkább a saját speciális kategóriájában. mint " egység ".

Elemi tulajdonságok

Egyedi faktorizáció

Ha egy számot prímszámok szorzataként írunk fel , azt a szám prímtényezősségének nevezzük . Például:

${\displaystyle {\begin{aligned}34866&=2\cdot 3\cdot 3\cdot 13\cdot 149\\&=2\cdot 3^{2}\cdot 13\cdot 149.\end{aligned}}}$

A termékben szereplő kifejezéseket prímtényezőknek nevezzük . Ugyanaz a prímtényező többször is előfordulhat; ebben a példában a prímtényező két példánya van. Amikor egy prím többször előfordul, a hatványozás segítségével ugyanannak a prímszámnak több példányát csoportosíthatjuk össze: például a szorzat fenti írásának második módjában a négyzetet vagy a második hatványt jelöli. nak,-nek${\displaystyle 3.}$${\displaystyle 3^{2}}$${\displaystyle 3.}$

A prímszámok központi jelentősége a számelméletben és általában a matematikában az aritmetika alaptételéből fakad . Ez a tétel kimondja, hogy minden 1-nél nagyobb egész szám felírható egy vagy több prímszám szorzataként. Még erősebben, ez a termék abban az értelemben egyedülálló, hogy bármely két azonos számú prímtényezős változatban ugyanannak a prímszámnak ugyanannyi példánya lesz, bár sorrendjük eltérő lehet. Tehát, bár számos különböző módszer létezik a faktorizáció megtalálására egész szám faktorizációs algoritmus használatával, mindegyiknek ugyanazt az eredményt kell produkálnia. A prímek tehát a természetes számok "alapvető építőköveinek" tekinthetők.

Néhány igazolások egyediségét elsődleges factorizations alapulnak Eukleidész lemma : Ha egy prímszám és felosztja a termék egészek és akkor oszt vagy oszt (vagy mindkettő). Ezzel szemben, ha egy számnak az a tulajdonsága, hogy amikor oszt egy szorzatot, mindig elosztja a szorzat legalább egy tényezőjét, akkor prímnek kell lennie. ${\displaystyle p}$${\displaystyle p}$${\displaystyle ab}$${\displaystyle a}$${\displaystyle b,}$${\displaystyle p}$${\displaystyle a}$${\displaystyle p}$${\displaystyle b}$${\displaystyle p}$${\displaystyle p}$

Végtelenség

Vannak végtelen sok prímszám. Ennek másik módja az, hogy a sorrend

2, 3, 5, 7, 11, 13, ...

a prímszámok soha nem érnek véget. Ezt az állítást Eukleidész tételeként említik az ókori görög matematikus, Eukleidész tiszteletére , mivel ennek az állításnak az első ismert bizonyítékát neki tulajdonítják. A prímszámok végtelenségének számos további bizonyítása ismert, beleértve az Euler- féle analitikus bizonyítást , a Fermat-számokon alapuló Goldbach- bizonyítást , az általános topológiát használó Furstenberg- bizonyítást és a Kummer-féle elegáns bizonyítást.

Eukleidész bizonyítása azt mutatja, hogy a prímek minden véges listája hiányos. A kulcsötlet az, hogy tetszőleges listában összeszorozzuk a prímeket és összeadjuk Ha a lista prímekből áll, ez adja a számot ${\displaystyle 1.}$${\displaystyle p_{1},p_{2},\ldots ,p_{n},}$

${\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}$

Az alaptétel szerint prímtényezőssége van ${\displaystyle N}$

${\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}$

egy vagy több elsődleges tényezővel. egyenlően osztható ezen tényezők mindegyikével, de van egy maradéka, ha elosztjuk bármelyik prímszámmal az adott listában, így egyik prímtényezője sem lehet az adott listában. Mivel nincs véges lista az összes prímszámról, végtelenül sok prímszámnak kell lennie. ${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$

Azokat a számokat, amelyek a legkisebb prímszámok szorzatának egy hozzáadásával keletkeznek, Euklidész számoknak nevezzük . Közülük az első öt elsőszámú, de a hatodik,

${\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}$

egy összetett szám.

Képletek prímszámokhoz

A prímszámokra nem ismert hatékony képlet. Például nincs olyan nem konstans polinom , még több változóban sem, amely csak prímértékeket vesz fel . Azonban számos olyan kifejezés létezik, amely minden prímszámot vagy csak prímszámot kódol. Az egyik lehetséges képlet a Wilson-tételen alapul, és a 2-es számot sokszor, az összes többi prímszámot pedig pontosan egyszer generálja. Létezik egy kilenc változóból és egy paraméterből álló Diofantin-egyenlethalmaz is , amely a következő tulajdonsággal rendelkezik: a paraméter akkor és csak akkor prím, ha az eredményül kapott egyenletrendszernek van megoldása a természetes számok felett. Ezzel egyetlen képletet kaphatunk azzal a tulajdonsággal, hogy minden pozitív értéke prím.

A prímgeneráló formulák további példái Mills tételéből és Wright tételéből származnak . Ezek azt állítják, hogy léteznek valódi állandók és ilyenek ${\displaystyle A>1}$${\displaystyle \mu }$

${\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}} \jobbra\rpadló }$

prímszámok bármely természetes számra az első képletben, és tetszőleges számú kitevőjére a második képletben. Itt a padlófüggvényt jelöli , a legnagyobb egész szám, amely kisebb vagy egyenlő, mint a kérdéses szám. Ezek azonban nem hasznosak prímszámok generálásához, mivel először a prímeket kell generálni, hogy kiszámíthassuk a ill.${\displaystyle n}$${\displaystyle \lfloor {}\cdot {}\rfloor }$${\displaystyle A}$${\displaystyle \mu .}$

Nyitott kérdések

Sok sejtés született a prímszámokról. A gyakran elemi megfogalmazású feltételezések közül sok évtizedekig kiállt a bizonyítással: Landau mind a négy problémája 1912-ből még mindig megoldatlan. Az egyik a Goldbach-sejtés , amely azt állítja, hogy minden 2- nél nagyobb páros egész felírható két prímszám összegeként. 2014-ig ezt a sejtést minden számra igazolták egészen az ennél gyengébb állításokig, például Vinogradov tétele szerint minden kellően nagy páratlan egész szám felírható három prím összegeként. Chen tétele azt mondja, hogy minden kellően nagy páros szám kifejezhető egy prímszám és egy félprím összegeként (két prímszám szorzataként). Ezenkívül minden 10-nél nagyobb páros egész felírható hat prímszám összegeként. A számelmélet ilyen kérdéseket vizsgáló ágát additív számelméletnek nevezzük . ${\displaystyle n}$${\displaystyle n=4\cdot 10^{18}.}$

Egy másik típusú probléma a prímrésekkel , az egymást követő prímszámok közötti különbségekkel kapcsolatos. A tetszőlegesen nagy prímrések megléte látható, ha megjegyezzük, hogy a sorozat összetett számokból áll , bármely természetes szám esetén A nagy prímrések azonban sokkal korábban jelentkeznek, mint ahogy ez az érv mutatja. Például az első 8 hosszúságú prímrés a 89 és 97 prímek között van, sokkal kisebb, mint a Feltételezések szerint végtelen sok ikerprím van , olyan prímpárok, amelyek különbsége 2; ez az ikerprím sejtés . Polignac sejtés államok általában, hogy minden pozitív egész szám van végtelen sok pár egymást követő prímszám, amely különbözik Andrica sejtés , Brocard sejtés , Legendre-sejtés , és Oppermann sejtés minden arra utal, hogy a legnagyobb hiányosságok között prímszám ettől a legyen legfeljebb kb eredményeképpen amelyről ismert, hogy kövesse a Riemann-sejtés, míg a jóval erősebb Cramer sejtés készlet a legnagyobb különbség méretben Prime rések lehet általánosítani prime -tuples , minták közötti különbségek több mint két prímszám. Végtelenségük és sűrűségük az első Hardy–Littlewood sejtés tárgya , amelyet az a heurisztika motiválhat, hogy a prímszámok a prímszámtétel által megadott sűrűségű véletlenszerű számsorokhoz hasonlóan viselkednek. ${\displaystyle n!+2,n!+3,\dots ,n!+n}$${\displaystyle n-1}$${\displaystyle n.}$${\displaystyle 8!=40320.}$${\displaystyle k,}$${\displaystyle 2k.}$ ${\displaystyle 1}$${\displaystyle n}$${\displaystyle {\sqrt {n}},}$${\displaystyle O((\log n)^{2}).}$${\displaystyle k}$

Analitikai tulajdonságok

Az analitikus számelmélet a számelméletet folytonos függvények , határértékek , végtelen sorozatok , valamint a végtelen és a végtelen kicsinyek kapcsolódó matematikájának lencséjén keresztül vizsgálja .

Ez a kutatási terület Leonhard Eulerrel és első jelentős eredményével, a bázeli probléma megoldásával kezdődött . A probléma annak a végtelen összegnek az értékét kérte, amely ma a Riemann zéta függvény értékeként ismerhető fel . Ez a függvény szorosan kapcsolódik a prímszámokhoz és a matematika egyik legjelentősebb megoldatlan problémájához, a Riemann-hipotézishez . Euler megmutatta . Ennek a számnak a reciproka annak a korlátozó valószínűsége, hogy egy nagy tartományból egyenletesen kiválasztott két véletlenszám viszonylag prím (nincs közös tényezője). ${\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\pontok ,}$${\displaystyle \zeta (2)}$${\displaystyle \zeta (2)=\pi ^{2}/6}$${\displaystyle 6/\pi ^{2}}$

A prímszámok nagyban való eloszlását, például azt a kérdést, hogy hány prím kisebb egy adott, nagy küszöbnél, a prímszámtétel írja le , de a -edik prímre${\displaystyle n}$ nem ismert hatékony képlet . Dirichlet aritmetikai progresszióról szóló tétele alapvető formájában azt állítja, hogy a lineáris polinomok

${\displaystyle p(n)=a+bn}$

viszonylag prím egész számokkal, és végtelen sok prímértéket vesz fel. A tétel erősebb formái azt állítják, hogy ezeknek a prímértékeknek a reciprok összege divergál, és a különböző, azonos lineáris polinomok prímeinek aránya megközelítőleg azonos. Bár megfogalmaztak sejtéseket a magasabb fokú polinomok prímeinek arányáról, ezek továbbra is bizonyítatlanok, és nem ismert, hogy létezik-e olyan másodfokú polinom, amely (egész argumentumok esetén) végtelenül gyakran prím. ${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$

Euklidész tételének analitikai bizonyítása

Euler bizonyítása, hogy végtelen sok prím van, a prímszámok reciproka összegét veszi figyelembe ,

${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots + {\frac {1}{p}}.}$

Euler megmutatta, hogy bármely tetszőleges valós számhoz létezik olyan prím , amelyre ez az összeg nagyobb, mint . Ez azt mutatja, hogy végtelen sok prím van, mert ha véges sok prím lenne, akkor az összeg a legnagyobb prímnél érné el maximális értékét, nem pedig minden . Ennek az összegnek a növekedési ütemét pontosabban leírja Mertens második tétele . Összehasonlításképpen az összeg ${\displaystyle x}$${\displaystyle p}$${\displaystyle x}$${\displaystyle x}$

${\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}$

nem nő a végtelenbe, mint ahogy a végtelenbe megy (lásd a bázeli problémát ). Ebben az értelemben a prímszámok gyakrabban fordulnak elő, mint a természetes számok négyzete, bár mindkét halmaz végtelen. Brun tétele kimondja, hogy az ikerprímek reciprokainak összege , ${\displaystyle n}$

${\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\ frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,}$

véges. Brun tétele miatt nem lehetséges az Euler-módszerrel megoldani azt az ikerprím sejtést , hogy végtelen sok ikerprím létezik.

Egy adott korlát alatti prímszámok száma

A relatív hiba az , és a logaritmikus integrál mint közelítések a prime-számláló funkció . Mindkét relatív hiba nullára csökken a növekedés során, de a nullához való konvergencia sokkal gyorsabb a logaritmikus integrál esetében.${\displaystyle {\tfrac {n}{\log n}}}$${\displaystyle \operatorname {Li} (n)}$${\displaystyle n}$

A prímszámláló függvény a prímszámok száma nem nagyobb, mint . Például , mivel öt prímszám kisebb vagy egyenlő 11-nél. Az olyan módszerek, mint a Meissel–Lehmer algoritmus , gyorsabban képesek pontos értékeket kiszámítani , mint ahogyan az egyes prímek listázása lehetséges lenne . A prímszámtétel kimondja, hogy aszimptotikus -ra , amelyet így jelölünk ${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle \pi (11)=5}$${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle \pi (n)}$${\displaystyle n/\log n}$

${\displaystyle \pi (n)\sim {\frac {n}{\log n}},}$

és azt jelenti, hogy a jobb oldali tört aránya megközelíti az 1-et, ahogy a végtelenbe nő. Ez azt jelenti, hogy annak a valószínűsége, hogy egy véletlenszerűen kiválasztott szám kisebb, mint prím, (körülbelül) fordítottan arányos a számjegyek számával . Ez azt is jelenti, hogy a th prímszám arányos -vel, és ezért egy prímrés átlagos mérete arányos -vel . A pontosabb becslést az ofszet logaritmikus integrál adja${\displaystyle \pi (n)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n\log n}$${\displaystyle \log n}$${\displaystyle \pi (n)}$

${\displaystyle \pi (n)\sim \operátornév {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.}$

Aritmetikai progressziók

Az aritmetikai sorozat olyan véges vagy végtelen számsorozat, amelyben a sorozat egymást követő számainak ugyanaz a különbsége. Ezt a különbséget a progresszió modulusának nevezzük . Például,

3, 12, 21, 30, 39, ...,

egy végtelen aritmetikai sorozat 9-es modulussal. Egy aritmetikai sorozatban minden számnak ugyanaz a maradéka, ha elosztjuk a modulussal; ebben a példában a maradék 3. Mivel a 9. modulus és a 3. maradék is 3 többszöröse, így a sorozat minden eleme is az. Ezért ez a progresszió csak egy prímszámot tartalmaz, magát a 3-at. Általában a végtelen progresszió

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

csak akkor lehet egynél több prím, ha maradéka és modulusa viszonylag prím. Ha viszonylag prímek, akkor Dirichlet aritmetikai sorozatokra vonatkozó tétele azt állítja, hogy a sorozat végtelen sok prímszámot tartalmaz. ${\displaystyle a}$${\displaystyle q}$

Prímek a modulo 9 aritmetikai sorozatokban. A vékony vízszintes sáv minden sora a kilenc lehetséges mod 9 progresszió egyikét mutatja, pirossal jelölt prímszámokkal. A 0, 3 vagy 6 mod 9 számok progressziója legfeljebb egy prímszámot (a 3-ast) tartalmazhat; a fennmaradó 2, 4, 5, 7 és 8 mod 9 számsorok végtelen sok prímszámot tartalmaznak, és mindegyik sorozatban hasonló számú prím van

A Green–Tao tétel azt mutatja, hogy vannak tetszőlegesen hosszú véges aritmetikai sorozatok, amelyek csak prímekből állnak.

Másodfokú polinomok prímértékei

Az Ulam spirál . A prímszámok (piros) egyes átlókon csoportosulnak, másokon nem. A prímértékek kék színnel jelennek meg.${\displaystyle 4n^{2}-2n+41}$

Euler megjegyezte, hogy a függvény

${\displaystyle n^{2}-n+41}$

prímszámokat ad a -hoz , bár az összetett számok megjelennek a későbbi értékei között. A keresést egy magyarázat erre a jelenségre vezetett a mély algebrai számelmélet a Heegner számok , és az osztály számát probléma . Az F Hardy-Littlewood sejtés megjósolja a prímszámok sűrűségét az egész együtthatós másodfokú polinomok értékei között a logaritmikus integrál és a polinom együtthatók alapján. Egyetlen másodfokú polinom sem bizonyítottan végtelen sok prímértéket vesz fel. ${\displaystyle 1\leq n\leq 40}$

Az Ulam spirál a természetes számokat egy kétdimenziós rácsba rendezi, spirálisan az origót körülvevő koncentrikus négyzetekbe, kiemelve a prímszámokat. Vizuálisan úgy tűnik, hogy a prímek bizonyos átlókra csoportosulnak, másokra nem, ami arra utal, hogy egyes másodfokú polinomok gyakrabban vesznek fel prímértékeket, mint mások.

Zéta-függvény és a Riemann-hipotézis

A zéta-függvény abszolút értékeinek diagramja, bemutatva néhány jellemzőjét

A matematika egyik leghíresebb, 1859-ből származó megválaszolatlan kérdése és a Millenniumi Díj-problémák egyike a Riemann-hipotézis , amely azt kérdezi, hol találhatók a Riemann-zéta-függvény nullái . Ez a függvény a komplex számok analitikus függvénye . Olyan komplex számok esetén, amelyek valós része nagyobb, mint egy, egyenlő az összes egész szám végtelen összegével és a prímszámok végtelen szorzatával , ${\displaystyle \zeta (s)}$${\displaystyle s}$

${\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}} {\frac {1}{1-p^{-s}}}.}$

Ez az egyenlőség közötti összeget és a termék által felfedezett Euler, nevezzük Euler terméket . Az Euler-szorzat az aritmetika alaptételéből származtatható, és a zéta-függvény és a prímszámok közötti szoros kapcsolatot mutatja. Ez egy újabb bizonyítékhoz vezet, hogy végtelen sok prím van: ha csak véges sok lenne, akkor az összeg-szorzat egyenlőség is érvényes lenne -ben, de az összeg eltérne (ez a harmonikus sorozat ), míg a szorzat véges lenne. egy ellentmondás. ${\displaystyle s=1}$ ${\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\ponts }$

A Riemann-hipotézis azt állítja, hogy a zéta-függvény nullái mind negatív páros számok, vagy olyan komplex számok, amelyek valós része 1/2. A prímszámtétel eredeti bizonyítása ennek a hipotézisnek egy gyenge formáján alapult, miszerint nincsenek 1-gyel egyenlő valós részek nullák, bár találtak más elemibb bizonyítást is. A prímszámláló függvény a Riemann-féle explicit formulával olyan összegként fejezhető ki , amelyben minden tag a zéta-függvény egyik nullájából származik; ennek az összegnek a fő tagja a logaritmikus integrál, a fennmaradó tagok pedig a főtag feletti és alatti ingadozást okozzák. Ebben az értelemben a nullák szabályozzák, hogy a prímszámok milyen rendszerességgel oszlanak el. Ha igaz a Riemann-hipotézis, akkor ezek az ingadozások kicsik lesznek, és a prímszámok aszimptotikus eloszlása , amelyet a prímszámtétel adott, sokkal rövidebb intervallumokra is érvényes lesz ( amelyek számhoz közeli intervallumok négyzetgyökének megfelelőek ). ${\displaystyle x}$${\displaystyle x}$

Absztrakt algebra

Moduláris aritmetika és véges mezők

A moduláris aritmetika a szokásos aritmetikát úgy módosítja, hogy csak a számokat használja a modulusnak nevezett természetes számhoz . Bármely más természetes szám leképezhető ebbe a rendszerbe úgy, hogy a -val való osztás után a maradékával helyettesítjük . A moduláris összegek, különbségek és szorzatok kiszámítása úgy történik, hogy ugyanazt a cserét végrehajtjuk az egész számok szokásos összegének, különbségének vagy szorzatának maradékával. Az egész számok egyenlősége a moduláris aritmetika kongruenciájának felel meg : és akkor kongruensek (írt mod ), ha a -val való osztás után ugyanaz a maradékuk . Ebben a számrendszerben azonban minden nem nulla számmal való osztás akkor és csak akkor lehetséges, ha a modulus prím. Például, ha a prímszám modulus, az osztás lehetséges: , mert a nevezők törlése mindkét oldal szorzatával az érvényes képletet adja . Az összetett modulussal azonban az osztás lehetetlen. Nincs érvényes megoldás : ha a nevezőket szorozva törli a bal oldalt, akkor a jobb oldalból vagy vagy lesz . Az absztrakt algebra terminológiájában az osztás végrehajtásának képessége azt jelenti, hogy a moduláris aritmetikai modulo egy prímszám mezőt , pontosabban véges mezőt alkot , míg más modulok csak gyűrűt adnak, mezőt nem. ${\displaystyle \{0,1,2,\dots ,n-1\}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\equiv y}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 7}$${\displaystyle 3}$${\displaystyle 2/3\equiv 3{\bmod {7}}}$${\displaystyle 3}$${\displaystyle 2\equiv 9{\bmod {7}}}$${\displaystyle 6}$${\displaystyle 3}$${\displaystyle 2/3\equiv x{\bmod {6}}}$${\displaystyle 3}$${\displaystyle 2}$${\displaystyle 0}$${\displaystyle 3}$

A prímszámokról több tétel is megfogalmazható moduláris aritmetika segítségével. Például Fermat kis tétele kimondja, hogy ha (mod ), akkor (mod ). Összegezve ezt az összes választással, megkapjuk az egyenletet ${\displaystyle a\not \equiv 0}$${\displaystyle p}$${\displaystyle a^{p-1}\equiv 1}$${\displaystyle p}$${\displaystyle a}$

${\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}$

akkor érvényes, amikor elsődleges. Giuga sejtése szerint ez az egyenlet is elégséges feltétele annak , hogy prím legyen. Wilson tétele azt mondja, hogy egy egész akkor és csak akkor prím, ha a faktoriális kongruens a mod -al . Összetett számra ez nem teljesülhet, mivel az egyik tényezője osztja n-t és -t is , így lehetetlen. ${\displaystyle p}$${\displaystyle p}$${\displaystyle p>1}$ ${\displaystyle (p-1)!}$${\displaystyle -1}$${\displaystyle p}$${\displaystyle \;n=r\cdot s\;}$${\displaystyle (n-1)!}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$

p -adikus számok

A -adic érdekében az egész a másolatok számát a prímfaktorizáció az . Ugyanez a koncepció lehet hosszabbítani egész racionális számokat meghatározó -adic sorrendben töredéke lehet . Ezután bármely racionális szám -adic abszolút értékét a következőképpen definiáljuk . Ha egy egész számot megszorozunk annak -adic abszolút értékével , akkor a faktorizációjában a faktorok megszűnnek , és csak a többi prím marad meg. Ahogyan két valós szám távolsága mérhető távolságuk abszolút értékével, úgy két racionális szám távolsága mérhető -adic távolságukkal, különbségük -adikus abszolút értékével. A távolság ezen definíciójához két szám közel van egymáshoz (kis távolságuk van), ha különbségük osztható nagy hatványával . Ugyanúgy, ahogy a valós számok a racionális számokból és távolságaikból képezhetők, extra határértékek hozzáadásával egy teljes mezőt alkotva , az -adic távolságú racionális számok kiterjeszthetők egy másik teljes mezőre, az -adic-re. számok . ${\displaystyle p}$ ${\displaystyle \nu _{p}(n)}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle m/n}$${\displaystyle \nu _{p}(m)-\nu _{p}(n)}$${\displaystyle p}$${\displaystyle |q|_{p}}$${\displaystyle q}$${\displaystyle |q|_{p}=p^{-\nu _{p}(q)}}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

A sorrendről, abszolút értékről és a belőlük származó teljes mezőről alkotott kép általánosítható algebrai számmezőkre és azok értékelésére (bizonyos leképezések a mező multiplikatív csoportjából egy teljesen rendezett additív csoportra , rendeléseknek is nevezik), abszolút értékekre ( bizonyos multiplikatív leképezések a mezőről a valós számokra, amelyeket normáknak is neveznek) és helyek (kiterjesztések olyan teljes mezőkre , amelyekben az adott mező sűrű halmaz , kiegészítéseknek is nevezik). A racionális számokról a valós számokra való kiterjesztés például egy olyan hely, ahol a számok közötti távolság a különbségük szokásos abszolút értéke . A megfelelő hozzárendelés egy additív csoporthoz az abszolút érték logaritmusa lenne , bár ez nem felel meg az értékelés minden követelményének. Szerint Ostrowski tétel , akár természetes ekvivalencia fogalma, a valós számok és -adic számokról és a megrendelések és abszolút értékek, az egyetlen értékelés, abszolút értékek, és hozza a racionális számokat. A lokális-globális elv lehetővé teszi, hogy a racionális számokkal kapcsolatos bizonyos problémákat úgy oldjunk meg, hogy mindegyik helyükről összerakjuk a megoldásokat, ismét hangsúlyozva a prímszámok fontosságát a számelméletben. ${\displaystyle p}$

Alapelemek gyűrűkben

A Gauss-prímek 500-nál kisebb normával

A kommutatív gyűrű egy algebrai struktúra, ahol összeadás, kivonás és szorzás van meghatározva. Az egész egy gyűrűt, és a prímszámok az egész már általánosítható gyűrűk két különböző módon, elsődleges elemek és irreducibilis elemek . Egy gyűrű egy elemét prímnek nevezzük, ha nem nulla, nincs szorzó inverze (vagyis nem egység ), és eleget tesz a következő követelménynek: amikor két elem szorzatát osztja, akkor legalább az egyiket is osztja. vagy . Egy elem irreducibilis, ha nem egysége, és nem is két másik nem egységelem szorzata. Az egész számok gyűrűjében a prím és az irreducibilis elemek ugyanazt a halmazt alkotják, ${\displaystyle p}$${\displaystyle R}$${\displaystyle p}$${\displaystyle xy}$${\displaystyle R}$${\displaystyle x}$${\displaystyle y}$

${\displaystyle \{\pontok ,-11,-7,-5,-3,-2,2,3,5,7,11,\pontok \}\,.}$

Egy tetszőleges gyűrűben minden prímelem irreducibilis. Ennek a fordítottja nem általánosságban igaz, de igaz az egyedi faktorizációs tartományokra .

Az aritmetika alaptétele továbbra is érvényes (definíció szerint) az egyedi faktorizációs tartományokban. Példa egy ilyen tartományra a Gauss-egészek , a komplex számok gyűrűje , amelynek alakja ahol a képzeletbeli egységet jelöli, és a és tetszőleges egész számok. Elsődleges elemek ismert Gauss prímszám . Nem minden szám, amely az egész számok között prím, marad prím a Gauss-egészeknél; például a 2-es szám felírható a két Gauss-prím és a szorzataként . A 3 mod 4-el kongruens racionális prímek (az egész számok prímelemei) Gauss-prímek, de az 1 mod 4-hez kongruens racionális prímek nem. Ez Fermat két négyzet összegére vonatkozó tételének a következménye , amely kimondja, hogy egy páratlan prím két négyzet összegeként fejezhető ki , és ezért faktorizálható , amikor pontosan 1 mod 4. ${\displaystyle \mathbb {Z} [i]}$${\displaystyle a+bi}$${\displaystyle i}$${\displaystyle a}$${\displaystyle b}$${\displaystyle 1+i}$${\displaystyle 1-i}$${\displaystyle p}$${\displaystyle p=x^{2}+y^{2}}$${\displaystyle p=(x+iy)(x-iy)}$${\displaystyle p}$

Elsődleges ideálok

Nem minden gyűrű egyedi faktorizációs tartomány. Például a számok gyűrűjében (egészek és ) a számnak két faktorizációja van , ahol a négy tényező közül egyik sem csökkenthető tovább, így nincs egyedi faktorizációja. Az egyedi faktorizáció kiterjesztése érdekében a gyűrűk nagyobb osztályára, a szám fogalma helyettesíthető egy ideál fogalmával , a gyűrű elemeinek olyan részhalmazával, amely tartalmazza az elempárok összes összegét és a gyűrűk összes szorzatát. elemek gyűrű elemekkel. A prímideálok, amelyek a prímelemeket általánosítják abban az értelemben, hogy a prímelem által generált főideál prímideál, fontos eszköz és vizsgálati tárgy a kommutatív algebrában , az algebrai számelméletben és az algebrai geometriában . Az egész számok gyűrűjének elsődleges ideáljai a (0), (2), (3), (5), (7), (11), ... Az aritmetika alaptétele általánosít a Lasker–Noether tételre. , amely kifejezi minden ideális a Noetherian kommutatív gyűrű , mint egy kereszteződésben a primer eszmények , amelyek a megfelelő általánosítások elsődleges hatáskörét . ${\displaystyle a+b{\sqrt {-5}}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle 21}$${\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})}$

A gyűrű spektruma egy geometriai tér, amelynek pontjai a gyűrű elsődleges ideáljai. Az aritmetikai geometria is hasznot húz ebből a fogalomból, és számos fogalom létezik mind a geometriában, mind a számelméletben. Például a prímideálok faktorizálása vagy elágazása , amikor egy kiterjesztési mezőre emeljük, az algebrai számelmélet alapvető problémája, némi hasonlóságot mutat a geometriai elágazásokkal . Ezek a fogalmak még a kizárólag egész számokkal kapcsolatos számelméleti kérdésekben is segítséget nyújthatnak. Például a másodfokú számmezők egész számainak gyűrűjében lévő prímideálok felhasználhatók a másodfokú reciprocitás bizonyítására , amely állítás négyzetgyökök modulo egész prímszámok létezésére vonatkozik. A korai próbálkozások bizonyítani Fermat vezetett Kummer „s bevezetése rendszeres prímszám , egész prímszámok kapcsolódik az a tény, egyedi faktorizációs a körosztási egészek . Arra a kérdésre, hogy hány egész prímszám számít bele több prímideál szorzatába egy algebrai számmezőben, a Csebotarev-féle sűrűségtétel foglalkozik , amelyben (a ciklotómikus egész számokra alkalmazva) Dirichlet tétele az aritmetikai sorozatokban előforduló prímszámokról egy speciális eset.

Csoportelmélet

A véges csoportok elméletében a Sylow-tételek azt jelentik, hogy ha egy prímszám hatványa osztja egy csoport sorrendjét , akkor a csoportnak van egy rendű részcsoportja . By Lagrange-tétel , bármely csoport elsődleges megbízás egy ciklikus csoport , valamint a Burnside-tétel olyan csoport, amelynek érdekében osztható csak két prímszám van megoldható . ${\displaystyle p^{n}}$${\displaystyle p^{n}}$

Számítási módszerek

Ebben a mezőgazdasági berendezésben a kis fogaskerék 13 fogas, egy prímszám, a középső fogaskereke pedig 21, relatíve 13-hoz.

Sokáig a számelméletet általában, és különösen a prímszámok tanulmányozását a tiszta matematika kanonikus példájának tekintették, és a matematikán kívül nem volt más alkalmazás, mint a prímszámozott fogaskerekek használata a kopás egyenletes elosztására. Különösen a számelméletek, például a brit matematikus, GH Hardy büszkék voltak arra, hogy olyan munkát végeznek, amelynek egyáltalán nem volt katonai jelentősége.

A számelmélet tisztaságáról szóló vízió az 1970-es években megdőlt, amikor nyilvánosan bejelentették, hogy a prímszámokat nyilvános kulcsú kriptográfiai algoritmusok létrehozásának alapjaként lehet felhasználni . Ezek az alkalmazások a prímszámokkal történő számítási algoritmusok jelentős tanulmányozását eredményezték , és különösen a primalitástesztelési módszereket, amelyek segítségével meghatározható, hogy egy adott szám prímszám-e. A legalapvetőbb primalitástesztelési rutin, a próbaosztás túl lassú ahhoz, hogy nagy számok esetén hasznos legyen. A modern primalitástesztek egyik csoportja tetszőleges számokra alkalmazható, míg a speciális típusú számokra hatékonyabb tesztek állnak rendelkezésre. A legtöbb elsődlegességi teszt csak azt mondja meg, hogy az argumentum prím-e vagy sem. Azokat a rutinokat, amelyek az összetett argumentumok prímtényezőjét is biztosítják (vagy annak összes prímtényezőjét), faktorizációs algoritmusoknak nevezzük . A prímszámokat ellenőrző összegek , hash táblák és pszeudovéletlen számgenerátorok számításánál is használják .

Próbaosztály

A legalapvetőbb módszer ellenőrzésére primality egy adott egész szám az úgynevezett tárgyalás részlege . Ez a módszer felosztja az egyes egész szám 2-től egészen a négyzetgyöke a . Minden ilyen egész szám egyenletes osztása összetett; egyébként príma. Egész számok nagyobb, mint a négyzetgyök nem kell ellenőrizni, mivel, ha , az egyik a két tényező , és kisebb vagy egyenlő, mint a négyzetgyök a . Egy másik optimalizálás az, hogy ebben a tartományban csak a prímszámokat ellenőrizzük tényezőként. Például annak ellenőrzésére, hogy a 37 prím-e, ez a módszer elosztja a 2-től ig terjedő tartományban lévő prímekkel , amelyek 2, 3 és 5. Minden osztás nullától eltérő maradékot ad, tehát a 37 valóban prím. ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n=a\cdot b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle n}$${\displaystyle {\sqrt {37}}}$

Bár ez a módszer egyszerűen leírható, nem praktikus nagy egészek elsődlegességének tesztelésére, mivel az elvégzett tesztek száma exponenciálisan növekszik ezen egész számok számjegyeinek függvényében. Mindazonáltal próbaosztást továbbra is használnak, az osztó méretének négyzetgyökénél kisebb korláttal, hogy gyorsan felfedezzék a kis tényezőkkel rendelkező összetett számokat, mielőtt bonyolultabb módszereket alkalmaznának a szűrőn átmenő számokon.

Sziták

A szitán Eratosthenes kezdődik minden szám jelöletlen (szürke). Ismételten megtalálja az első jelöletlen számot, megjelöli elsődlegesnek (sötét színek), és négyzetét és minden későbbi többszörösét összetettnek (világosabb színek) jelöli. A 2 (piros), 3 (zöld), 5 (kék) és 7 (sárga) többszöröseinek megjelölése után az összes prímszám a táblázat méretének négyzetgyökéig feldolgozásra került, és az összes többi jelöletlen szám (11, 13) stb.) prímszámként (bíbor) vannak jelölve.

A számítógépek előtt általában matematikai táblázatokat nyomtattak, amelyek az összes prímszámot vagy prímtényezőket felsorolták egy adott határig. A prímek listájának létrehozásának legrégebbi módszerét Eratoszthenész szitájának nevezik. Az animáció ennek a módszernek egy optimalizált változatát mutatja. Egy másik aszimptotikusan hatékonyabb szitálási módszer ugyanerre a problémára az Atkin-féle szita . A haladó matematikában a szitaelmélet hasonló módszereket alkalmaz más problémákra.

Primális tesztelés versus elsődlegesség bizonyítása

A leggyorsabb modern tesztek némelyike ​​annak meghatározására, hogy egy tetszőleges adott szám prím-e, valószínűségi (vagy Monte Carlo ) algoritmusok, ami azt jelenti, hogy van egy kis véletlenszerű esélyük arra, hogy helytelen választ adnak. Például a Solovay–Strassen primalitásteszt egy adott számon véletlenszerűen választ ki egy számot , és moduláris hatványozást használ annak ellenőrzésére, hogy osztható-e -vel . Ha igen, akkor igennel válaszol, egyébként pedig nem. Ha valóban prím, akkor mindig igennel válaszol, de ha összetett, akkor legfeljebb 1/2 valószínűséggel igennel válaszol, és legalább 1/2 valószínűséggel nem. Ha ezt a tesztet ugyanazon a számon ismételjük meg, annak a valószínűsége, hogy egy összetett szám minden alkalommal át tudja menni a tesztet, legfeljebb . Mivel ez exponenciálisan csökken a tesztek számával, nagy biztonságot ad (bár nem bizonyosságot), hogy az ismételt teszten átmenő szám prímszámú. Másrészt, ha a teszt valaha is megbukik, akkor a szám minden bizonnyal összetett. Az ilyen teszten átmenő összetett számot pszeudoprímnek nevezzük . ${\displaystyle n}$${\displaystyle p}$${\displaystyle a}$${\displaystyle 2}$${\displaystyle p-2}$${\displaystyle a^{(p-1)/2}\pm 1}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$${\displaystyle n}$${\displaystyle 1/2^{n}}$

Ezzel szemben néhány más algoritmus garantálja, hogy válaszuk mindig helyes lesz: a prímszámok mindig prímek, az összetettek pedig mindig összetettek. Például ez igaz a próbafelosztásra. A garantáltan helyes kimenettel rendelkező algoritmusok közé tartoznak mind a determinisztikus (nem véletlenszerű) algoritmusok, mint például az AKS-primalitásteszt , mind a véletlenszerű Las Vegas-i algoritmusok, ahol az algoritmus által hozott véletlenszerű választások nem befolyásolják a végső választ, például az ellipszis egyes változatai. görbe elsődlegességének bizonyítása . Amikor az elliptikus görbe módszer arra a következtetésre jut, hogy egy szám prím, akkor gyorsan ellenőrizhető elsődlegességi tanúsítványt ad . Az elliptikus görbe primalitástesztje a leggyorsabb a gyakorlatban a garantált-helyes primalitástesztek közül, de futásidejű elemzése heurisztikus érveken alapul, nem pedig szigorú bizonyításokon. Az AKS primalitásteszt matematikailag igazolt időbonyolultsággal rendelkezik, de lassabb, mint a gyakorlatban az elliptikus görbe primalitás bizonyítása. Ezek a módszerek nagy véletlenszerű prímszámok generálására használhatók véletlenszámok generálásával és tesztelésével, amíg meg nem találjuk a prímszámot; amikor ezt megteszi, egy gyorsabb valószínűségi teszt gyorsan kiküszöböli a legtöbb összetett számot, mielőtt egy garantáltan helyes algoritmust használna annak ellenőrzésére, hogy a fennmaradó számok prímszámok-e.

Az alábbi táblázat felsorol néhány ilyen tesztet. Futási idejüket a tesztelendő számmal, valószínűségi algoritmusok esetén pedig az elvégzett tesztek számával adjuk meg . Ezenkívül egy tetszőlegesen kis pozitív szám, a log pedig egy meghatározatlan bázis logaritmusa . A nagy O jelölés azt jelenti, hogy minden időkorlátot meg kell szorozni egy állandó tényezővel , hogy dimenzió nélküli egységekből időegységekké alakítsuk át; ez a tényező a megvalósítás részleteitől függ, például az algoritmus futtatásához használt számítógép típusától, de nem a bemeneti paraméterektől és a . ${\displaystyle n}$${\displaystyle k}$${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle k}$

Teszt	ben fejlődött	típus	Futási idő	Megjegyzések	Hivatkozások
AKS elsődlegességi teszt	2002	meghatározó	${\displaystyle O((\log n)^{6+\varepsilon })}$
Elliptikus görbe elsődlegességének bizonyítása	1986	Las Vegas	${\displaystyle O((\log n)^{4+\varepsilon })}$ heurisztikusan
Baillie–PSW elsődlegességi teszt	1980	Monte Carlo	${\displaystyle O((\log n)^{2+\varepsilon })}$
Miller–Rabin primalitási teszt	1980	Monte Carlo	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	hiba valószínűsége ${\displaystyle 4^{-k}}$
Solovay–Strassen elsődleges teszt	1977	Monte Carlo	${\displaystyle O(k(\log n)^{2+\varepsilon })}$	hiba valószínűsége ${\displaystyle 2^{-k}}$

Speciális algoritmusok és a legnagyobb ismert prím

A fent említett teszteken kívül, amelyek bármely természetes számra vonatkoznak, egyes speciális alakzatú számok elsődlegessége gyorsabban tesztelhető. Például a Lucas–Lehmer primalitásteszt meg tudja határozni, hogy egy Mersenne-szám (egynél kisebb, mint kettő hatványa ) prím-e, determinisztikusan, a Miller–Rabin teszt egyetlen iterációjával egy időben. Ez az oka annak, hogy 1992 óta (2018 decemberétől) a legnagyobb ismert prím mindig Mersenne prím volt. Feltételezik, hogy végtelenül sok Mersenne-prím van.

A következő táblázat a különböző típusú legnagyobb ismert prímszámokat tartalmazza. Néhány ilyen prímszámot elosztott számítástechnikával találtak meg . 2009-ben a Great Internet Mersenne Prime Search projektet 100 000 USD díjjal jutalmazták egy legalább 10 millió számjegyből álló prím első felfedezéséért. Az Electronic Frontier Foundation 150 000 dollárt és 250 000 dollárt is kínál legalább 100 millió, illetve 1 milliárd számjegyű prímszámokért.

Egész faktorizáció

Adott egy kompozit egész szám , amelynek feladata, hogy egy (vagy az összes) prímosztója nevezik faktorizációja a . Ez lényegesen nehezebb, mint a primalitásteszt, és bár sok faktorizációs algoritmus ismert, ezek lassabbak, mint a leggyorsabb primalitástesztelési módszerek. A próbaosztás és a Pollard-féle rho algoritmus nagyon kis faktorok meghatározására használható , és az elliptikus görbe faktorizálása akkor lehet hatékony, ha közepes méretű tényezők vannak. Tetszőleges nagy számokhoz, amelyek nem függnek a tényezők nagyságától, alkalmas módszerek közé tartozik a másodfokú szita és az általános számmezőszita . A primalitásteszthez hasonlóan léteznek olyan faktorizációs algoritmusok is, amelyek megkövetelik, hogy a bevitelüknek speciális formájú legyen, beleértve a speciális számmező szitát is . 2019 decemberéig az általános célú algoritmus által ismert legnagyobb szám az RSA-240 , amely 240 decimális számjegyből (795 bitből) áll, és két nagy prímszám szorzata. ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

A Shor algoritmusa kvantumszámítógépen tetszőleges egész számot tud faktorálni polinomiális lépésszámban . A jelenlegi technológia azonban csak nagyon kis számoknál tudja futtatni ezt az algoritmust. 2012 októberéig a Shor algoritmust futtató kvantumszámítógép által figyelembe vett legnagyobb szám 21.

Egyéb számítási alkalmazások

Számos nyilvános kulcsú kriptográfiai algoritmus, mint például az RSA és a Diffie–Hellman kulcscsere , nagy prímszámokon alapul (a 2048 bites prímszámok gyakoriak). Az RSA arra a feltételezésre támaszkodik, hogy sokkal könnyebb (vagyis hatékonyabb) elvégezni két (nagy) szám szorzását, és mint kiszámítani és (feltételezve koprime ), ha csak a szorzat ismert. A Diffie–Hellman kulcscsere azon a tényen alapul, hogy léteznek hatékony algoritmusok a moduláris hatványozáshoz (számítás ), míg a fordított művelet (a diszkrét logaritmus ) nehéz probléma. ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle xy}$${\displaystyle a^{b}{\bmod {c}}}$

A prímszámokat gyakran használják hash táblákhoz . Például Carter és Wegman eredeti univerzális hash -módszere a hash-függvények kiszámításán alapult úgy, hogy véletlenszerű lineáris függvényeket választottak nagy prímszámokhoz. Carter és Wegman ezt a módszert -független kivonatolásra általánosította magasabb fokú polinomok, ismét modulo nagy prímek használatával. Csakúgy, mint a hash függvényben, a négyzetes vizsgáló alapú hash táblákban prímszámokat használnak a hash tábla méretéhez, hogy biztosítsák, hogy a próbasorozat lefedi a teljes táblát. ${\displaystyle k}$

Egyes ellenőrzőösszeg- módszerek a prímszámok matematikáján alapulnak. Például a nemzetközi szabványos könyvszámokban használt ellenőrző összegeket úgy határozzák meg, hogy a modulo 11 szám többi részét egy prímszámnak tekintik. Mivel a 11 az elsődleges, ez a módszer képes mind az egyszámjegyű hibákat, mind a szomszédos számjegyek transzponálását észlelni. Egy másik ellenőrző összeg módszer, az Adler-32 , a 65521 modulo aritmetikai értéket használja, a legnagyobb prímszám kisebb, mint . A prímszámokat álvéletlen számgenerátorokban is használják, beleértve a lineáris kongruenciális generátorokat és a Mersenne Twistert . ${\displaystyle 2^{16}}$

Egyéb alkalmazások

A prímszámok központi jelentőségűek a számelméletben, de számos alkalmazásuk van a matematika más területein is, beleértve az absztrakt algebrát és az elemi geometriát. Például lehetséges prímszámú pontokat elhelyezni egy kétdimenziós rácsban úgy, hogy ne legyen három egy egyenesben , vagy úgy, hogy minden három pontból álló háromszög nagy területű legyen . Egy másik példa az Eisenstein-kritérium , egy teszt arra vonatkozóan, hogy egy polinom irreducibilis- e az együtthatóinak prímszámmal és négyzetével való oszthatósága alapján.

Két prímcsomó összefüggő összege

A prímszám fogalma annyira fontos, hogy a matematika különböző ágaiban különböző módon általánosították. Általában a "prime" a minimálisságot vagy a felbonthatatlanságot jelenti, megfelelő értelemben. Például az elsődleges területen egy adott területen a legkisebb részterület, amely tartalmazza mind a 0 és 1 Ennek az lehet a racionális számok vagy egy véges mező egy prímszám elemek, innen ered a neve. A prím szó használatával gyakran egy második, járulékos jelentést is megcéloznak, mégpedig azt, hogy bármely objektum lényegében egyedi módon felbontható elsődleges összetevőire. Például csomó elmélet , a prime csomót egy csomót , ami felbonthatatlan abban az értelemben, hogy nem lehet leírni, mint a csatlakoztatott összege két triviális csomó. Bármely csomó egyedileg kifejezhető az elsődleges csomók összefüggő összegeként. A 3-sokaságok prímbontása egy másik példa erre a típusra.

A matematikán és a számítástechnikán túl a prímszámok potenciálisan kapcsolódnak a kvantummechanikához , és metaforikusan használják őket a művészetekben és az irodalomban. Az evolúciós biológiában is használták a kabócák életciklusának magyarázatára .

Konstruálható sokszögek és sokszög-partíciók

Szabályos ötszög építése egyenes éllel és iránytűvel. Ez csak azért lehetséges, mert az 5 egy Fermat prím .

A Fermat prímszámok az alak prímjei

${\displaystyle F_{k}=2^{2^{k}}+1,}$

azzal egy nem negatív egész . Pierre de Fermat-ról nevezték el őket , aki úgy sejtette, hogy minden ilyen szám prímszám. Az első öt ezeket a számokat - 3, 5, 17, 257 és 65537 - prím, de a kompozit és így az összes többi Fermat számok, amelyek igazoltan mint 2017 A rendszeres -gon van szerkeszthető segítségével vonalzó és iránytű , ha és csak akkor, ha a páratlan prímtényezők (ha vannak) külön Fermat-prímek. Hasonlóképpen, egy szabályos -gon szerkeszthető egyenes él , iránytű és szögtriszektor segítségével, akkor és csak akkor, ha a prímtényezők tetszőleges számú másolata 2-nek vagy 3-nak, valamint a különböző Pierpont-prímek (esetleg üres) halmaza . az űrlapot . ${\displaystyle k}$${\displaystyle F_{5}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2^{a}3^{b}+1}$

Lehetőség van a partíció bármely konvex sokszög kisebb konvex sokszög azonos területű és egyenlő kerülete, ha egy erejét egy prímszám , de ez nem ismert, más értékek . ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

Kvantummechanika

Kezdve a munka Hugh Montgomery és Freeman Dyson az 1970-es, a matematikusok és fizikusok úgy gondolják, hogy a nullákat a Riemann-féle zéta funkció kapcsolódik az energia szintjét kvantum rendszerek . A prímszámok a kvantuminformáció-tudományban is jelentősek , köszönhetően az olyan matematikai struktúráknak, mint a kölcsönösen elfogulatlan bázisok és a szimmetrikus, információsan teljes, pozitív operátor értékű mérőszámok .

Biológia

Az evolúciós stratégia által használt kabócák a nemzetség Magicicada él prímszám. Ezek a rovarok töltik életük nagy részét a hernyók a föld alatt. Csak 7, 13 vagy 17 év után bábozódnak be, majd bújnak ki odúikból, ekkor repülnek, szaporodnak, majd legfeljebb néhány hét múlva elpusztulnak. A biológusok elmélete szerint ezek az elsőszámú szaporodási ciklusok azért alakultak ki, hogy megakadályozzák a ragadozók szinkronizálását ezekkel a ciklusokkal. Ezzel szemben a bambusznövények virágzása közötti többéves periódusokról azt feltételezik, hogy sima számok , és csak kis prímszámokat tartalmaznak a faktorizálásukban.

Művészetek és irodalom

A prímszámok sok művészre és íróra hatással voltak. Olivier Messiaen francia zeneszerző prímszámokat használt, hogy "természeti jelenségeken" keresztül ametrikus zenét alkosson. Az olyan művekben, mint a La Nativité du Seigneur (1935) és a Quatre études de rythme (1949–50), egyszerre alkalmaz különböző prímszámok által adott hosszúságú motívumokat, hogy kiszámíthatatlan ritmust hozzon létre: a 41-es, 43-as, 47-es és 53-as prímek jelennek meg a harmadik etűd, "Neumes rythmiques". Messiaen szerint ezt a komponálási módot "a természet mozgásai, szabad és egyenlőtlen időtartamú mozgások ihlették".

Carl Sagan tudós a Kapcsolat című tudományos-fantasztikus regényében azt javasolta, hogy az elsődleges faktorizációt fel lehetne használni kétdimenziós képsíkok létrehozására az idegenekkel való kommunikáció során. Ezt az ötletet először 1975-ben, Frank Drake amerikai csillagásznál dolgozta ki informálisan . regény a Curious Incident of the Dog in the Night-Time által Mark Haddon , az elbeszélő rendez szakaszok a történet egymást követő prímszám olyan módon, hogy közvetíteni a mentális állapot a fő karakter, matematikailag tehetséges tini Asperger-szindróma . A prímszámokat a magány és az elszigeteltség metaforájaként használják Paolo Giordano The Solitude of Prime Numbers című regényében , amelyben az egész számok között "kívülállóként" szerepelnek.

Megjegyzések

Hivatkozások

Külső linkek

• "Prómszám" . Matematikai Enciklopédia . EMS Nyomja meg a gombot . 2001 [1994].
• Caldwell, Chris, The Prime Pages itt: primes.utm.edu .
• Prímszámok a Korunkban a BBC-n
• Plusz tanári és diákcsomag: prímszámok a Plus-tól, a Cambridge-i Egyetem Millenium Mathematics Projectje által készített ingyenes online matematikai magazintól.

Generátorok és számológépek

• A prímtényezők kalkulátora bármilyen pozitív egész számot 20 számjegyig faktorizálhat.
• Fast Online primalitásteszt faktorizációval az elliptikus görbe módszert használja (akár ezer számjegyű számok, Java szükséges).
• Hatalmas prímszám-adatbázis
• Prímszámok akár 1 billióig