Cum să găsești numere prime? Numere prime misterioase.

Enumerarea divizorilor. Prin definiție, număr n este prim numai dacă nu este divizibil egal cu 2 și alte numere întregi, cu excepția lui 1 și a lui însuși. Formula de mai sus elimină pașii inutile și economisește timp: de exemplu, după ce ați verificat dacă un număr este divizibil cu 3, nu este nevoie să verificați dacă este divizibil cu 9.

• Funcția floor(x) rotunjește x la cel mai apropiat număr întreg care este mai mic sau egal cu x.

Aflați despre aritmetica modulară. Operația este „x mod y” (mod este prescurtarea pentru cuvânt latin„modulo” înseamnă „împărțiți x la y și găsiți restul”. Cu alte cuvinte, în aritmetica modulară, la atingerea unei anumite valori, care se numește modul, numerele „se transformă” din nou la zero. De exemplu, un ceas ține timpul cu un modul de 12: arată ora 10, 11 și 12 și apoi revine la 1.

• Multe calculatoare au o cheie mod. Sfârșitul acestei secțiuni arată cum se calculează manual această funcție pentru numere mari.

Numerele pot fi diferite: naturale, raționale, raționale, întregi și fracționale, pozitive și negative, complexe și simple, impare și par, reale etc. Din acest articol puteți afla ce este numere prime.

Ce numere se numesc „simple” în engleză?

De foarte multe ori, școlarii nu știu să răspundă la una dintre cele mai simple întrebări din matematică la prima vedere, despre ce este un număr prim. Ele confundă adesea numerele prime cu numerele naturale (adică numerele pe care oamenii le folosesc atunci când numără obiectele, în timp ce în unele surse încep cu zero, iar în altele cu unu). Dar sunt complet două concepte diferite. Numerele prime sunt numere naturale, adică numere întregi și numere pozitive care sunt mai mari decât unu și care au doar 2 divizori naturali. Mai mult, unul dintre acești divizori este numărul dat, iar al doilea este unul. De exemplu, trei este un număr prim, deoarece nu poate fi împărțit fără rest cu un alt număr decât el însuși și unul.

Numerele compuse

Opusul numerelor prime sunt numerele compuse. Sunt și naturali, mai mari decât unu, dar au nu doi, ci un număr mai mare de divizori. Deci, de exemplu, numerele 4, 6, 8, 9 etc. sunt naturale, compuse, dar nu numere prime. După cum puteți vedea, acestea sunt în mare parte numere pare, dar nu toate. Dar „doi” este un număr par și „primul număr” dintr-o serie de numere prime.

Urmare

Pentru a construi o serie de numere prime, este necesar să selectați dintre toate numerele naturale, ținând cont de definiția lor, adică trebuie să acționați prin contradicție. Este necesar să se ia în considerare fiecare dintre cele naturale numere pozitive pentru a vedea dacă are mai mult de doi divizori. Să încercăm să construim o serie (secvență) care constă din numere prime. Lista începe cu doi, urmat de trei, deoarece este divizibil doar cu ea însăși și unul. Luați în considerare numărul patru. Are alți divizori decât patru și unu? Da, acel număr este 2. Deci patru nu este un număr prim. Cinci este, de asemenea, prim (nu este divizibil cu niciun alt număr, cu excepția 1 și 5), dar șase este divizibil. Și, în general, dacă urmați toate numerele pare, veți observa că, cu excepția „doi”, niciunul dintre ele nu este prim. De aici concluzionăm că numerele pare, cu excepția a doi, nu sunt prime. O altă descoperire: toate numerele divizibile cu trei, cu excepția celor trei în sine, par sau impar, nu sunt nici prime (6, 9, 12, 15, 18, 21, 24, 27 etc.). Același lucru este valabil și pentru numerele care sunt divizibile cu cinci și șapte. Toată multitudinea lor nu este, de asemenea, simplă. Să rezumam. Deci, numerele simple dintr-o singură cifră includ toate numerele impare, cu excepția unu și nouă, iar „doi” chiar sunt numere pare. Zecile în sine (10, 20,... 40 etc.) nu sunt simple. Numerele prime de două cifre, trei cifre etc. pot fi determinate pe baza principiilor de mai sus: dacă nu au alți divizori decât ele și unul.

Teorii despre proprietățile numerelor prime

Există o știință care studiază proprietățile numerelor întregi, inclusiv numerelor prime. Aceasta este o ramură a matematicii numită superioară. Pe lângă proprietățile numerelor întregi, ea se ocupă și de numerele algebrice și transcendentale, precum și de funcții de diverse origini legate de aritmetica acestor numere. În aceste studii, pe lângă elementare și metode algebrice, sunt folosite și analitice și geometrice. Mai exact, „Teoria numerelor” se ocupă de studiul numerelor prime.

Numerele prime sunt „componentele de bază” ale numerelor naturale

În aritmetică există o teoremă numită teorema fundamentală. Potrivit acesteia, orice număr natural, cu excepția unuia, poate fi reprezentat ca un produs, ai cărui factori sunt numere prime, iar ordinea factorilor este unică, ceea ce înseamnă că metoda de reprezentare este unică. Se numește descompunere număr naturalîn factori primi. Există un alt nume pentru acest proces - factorizarea numerelor. Pe baza acestui fapt, numerele prime pot fi numite „ material de constructie”, „blocuri” pentru construirea numerelor naturale.

Căutați numere prime. Teste de simplitate

Mulți oameni de știință din timpuri diferite au încercat să găsească niște principii (sisteme) pentru găsirea unei liste de numere prime. Știința cunoaște sisteme numite sita Atkin, sita Sundartham și sita Eratosthenes. Cu toate acestea, ele nu produc rezultate semnificative și se folosește un test simplu pentru a găsi numerele prime. Matematicienii au creat și algoritmi. Ele sunt de obicei numite teste de primalitate. De exemplu, există un test dezvoltat de Rabin și Miller. Este folosit de criptografi. Există și testul Kayal-Agrawal-Sasquena. Cu toate acestea, în ciuda preciziei suficiente, este foarte dificil de calculat, ceea ce îi reduce semnificația practică.

Mulțimea numerelor prime are o limită?

Vechiul om de știință grec Euclid a scris în cartea sa „Elemente” că setul de numere prime este infinit. El a spus asta: „Să ne imaginăm pentru o clipă că numerele prime au o limită. Apoi să le înmulțim între ele și să adăugăm unul la produs. Numărul rezultat din acestea actiuni simple, nu poate fi împărțit la niciuna din seria de numere prime, deoarece restul va fi întotdeauna unul. Aceasta înseamnă că există un alt număr care nu este încă inclus în lista numerelor prime. Prin urmare, presupunerea noastră nu este adevărată, iar acest set nu poate avea o limită. Pe lângă demonstrația lui Euclid, există o formulă mai modernă dată de matematicianul elvețian din secolul al XVIII-lea Leonhard Euler. Potrivit acesteia, suma reciprocă a sumei primelor n numere crește nelimitat pe măsură ce numărul n crește. Și iată formula teoremei privind distribuția numerelor prime: (n) crește cu n/ln (n).

Care este cel mai mare număr prim?

Același Leonard Euler a reușit să găsească cel mai mare număr prim al timpului său. Acesta este 2 31 - 1 = 2147483647. Cu toate acestea, până în 2013, a fost calculat un alt cel mai mare cel mai precis din lista numerelor prime - 2 57885161 - 1. Se numește numărul Mersenne. Conține aproximativ 17 milioane de cifre zecimale. După cum puteți vedea, numărul găsit de un om de știință din secolul al XVIII-lea este de câteva ori mai mic decât acesta. Ar fi trebuit să fie așa, pentru că Euler a efectuat acest calcul manual, dar contemporanul nostru a fost probabil ajutat de calculator. Mai mult, acest număr a fost obținut la Facultatea de Matematică din una dintre facultățile americane. Numerele numite după acest om de știință trec testul de primalitate Luc-Lemaire. Cu toate acestea, știința nu vrea să se oprească aici. Electronic Frontier Foundation, care a fost fondată în 1990 în Statele Unite ale Americii (EFF), a oferit o recompensă bănească pentru găsirea numerelor prime mari. Și dacă până în 2013 premiul a fost acordat acelor oameni de știință care le-ar găsi dintre 1 și 10 milioane numere zecimale, atunci astăzi această cifră a ajuns de la 100 de milioane la 1 miliard. Premiile variază de la 150 la 250 de mii de dolari SUA.

Numele numerelor prime speciale

Acele numere care au fost găsite datorită algoritmilor creați de anumiți oameni de știință și au trecut testul de simplitate se numesc speciale. Iată câteva dintre ele:

1. Merssen.

4. Cullen.

6. Mills et al.

Simplitatea acestor numere, numite după oamenii de știință de mai sus, este stabilită folosind următoarele teste:

1. Luc-Lemaire.

2. Pepina.

3. Riesel.

4. Billhart - Lemaire - Selfridge și alții.

Știința modernă nu se oprește aici și, probabil, în viitorul apropiat lumea va afla numele celor care au putut primi premiul de 250.000 de dolari prin găsirea celui mai mare număr prim.

Oamenii știau în antichitate că există numere care nu sunt divizibile cu niciun alt număr. Secvența numerelor prime arată cam așa:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Dovada că există infinit de aceste numere a fost dată și de Euclid, care a trăit în anul 300 î.Hr. Cam în aceiași ani, un alt matematician grec, Eratostene, a venit cu un algoritm destul de simplu pentru obținerea numerelor prime, a cărui esență a fost să taieze succesiv numerele din tabel. Acele numere rămase care nu erau divizibile cu nimic erau prime. Algoritmul se numește „sita lui Eratosthenes” și, datorită simplității sale (nu există operații de înmulțire sau împărțire, doar adunare), este încă folosit în tehnologia informatică.

Aparent, deja în timpul lui Eratostene a devenit clar că nu exista un criteriu clar pentru a stabili dacă un număr este prim - acest lucru poate fi verificat doar experimental. Sunt diverse moduri pentru a simplifica procesul (de exemplu, este evident că numărul nu ar trebui să fie par), dar un algoritm simplu de verificare nu a fost încă găsit și cel mai probabil nu va fi găsit: pentru a afla dacă un număr este prim sau nu, trebuie să încerci să-l împărți în numere din ce în ce mai mici.

Numerele prime respectă vreo lege? Da, și sunt destul de curioși.

De exemplu, matematicianul francez Mersenneîn secolul al XVI-lea a descoperit că multe numere prime au forma 2^N - 1, aceste numere se numesc numere Mersenne. Nu cu mult înainte de aceasta, în 1588, matematicianul italian Cataldi a descoperit numărul prim 2 19 - 1 = 524287 (conform clasificării Mersen se numește M19). Astăzi acest număr pare destul de scurt, dar și acum cu un calculator ar fi nevoie de multe zile pentru a-i verifica simplitatea, dar pentru secolul al XVI-lea a fost într-adevăr o treabă uriașă.

200 de ani mai târziu, matematician Euler a găsit un alt număr prim 2 31 - 1 = 2147483647. Din nou, toată lumea își poate imagina cantitatea necesară de calcule. El a mai înaintat o ipoteză (numită mai târziu „problema Euler” sau „problema Goldbach binară”), a cărei esență este simplă: fiecare număr par mai mare de doi poate fi reprezentat ca suma a două numere prime.

De exemplu, puteți lua orice 2 numere pare: 123456 și 888777888.

Folosind un computer, puteți găsi suma lor sub forma a două numere prime: 123456 = 61813 + 61643 și 888777888 = 444388979 + 444388909. Lucrul interesant aici este că o demonstrație exactă a acestei teoreme nu a fost încă găsită, deși nu a fost încă găsită. ajutorul computerelor a fost verificat la numere cu 18 zerouri.

Există o altă teoremă a matematicianului Pierre Fermat, descoperit în 1640, care spune că dacă un număr prim are forma 4*k+1, atunci poate fi reprezentat ca suma pătratelor altor numere. Deci, de exemplu, în exemplul nostru, numărul prim 444388909 = 4*111097227 + 1. Și într-adevăr, folosind un computer, puteți găsi că 444388909 = 19197*19197 + 8710*8710.

Teorema a fost demonstrată de Euler doar 100 de ani mai târziu.

Și în sfârșit Bernhard Riemannîn 1859, a fost propusă așa-numita „Ipoteza Riemann” despre numărul de distribuții ale numerelor prime care nu depășesc un anumit număr. Această ipoteză nu a fost încă dovedită, este inclusă în lista celor șapte „probleme ale mileniului”, pentru rezolvarea fiecăreia dintre ele, Clay Institute of Mathematics din Cambridge este gata să plătească o recompensă de un milion de dolari.

Deci nu este atât de simplu cu numere prime. Există de asemenea fapte uimitoare. De exemplu, în 1883 matematicianul rus EI. Pervushin din raionul Perm a dovedit primitatea numărului 2 61 - 1 = 2305843009213693951 . Nici acum, calculatoarele de uz casnic nu pot funcționa cu numere atât de lungi, dar la acea vreme era cu adevărat o treabă gigantică și cum a fost făcută nu este foarte clar până în prezent. Deși există într-adevăr oameni care au abilități unice ale creierului - de exemplu, persoanele cu autism sunt cunoscute că sunt capabile să găsească (!) numere prime de 8 cifre în mintea lor. Cum fac acest lucru nu este clar.

Modernitatea

Mai sunt numerele prime relevante astăzi? Cum! Numerele prime stau la baza criptografiei moderne, așa că majoritatea oamenilor le folosesc în fiecare zi fără să se gândească la asta. Orice proces de autentificare, de exemplu, înregistrarea unui telefon într-o rețea, plăți bancare etc., necesită algoritmi criptografici.

Esența ideii aici este extrem de simplă și se află în centrul algoritmului RSA, propus în 1975. Expeditorul și destinatarul selectează împreună o așa-numită „cheie privată”, care este stocată într-un loc sigur. Această cheie este, după cum probabil că cititorii au ghicit deja, un număr prim. A doua parte este „cheia publică”, tot un număr simplu, generat de expeditor și transmis ca o lucrare împreună cu mesajul în text clar poate fi chiar publicat într-un ziar; Esența algoritmului este că fără a cunoaște „partea închisă”, este imposibil să obțineți textul sursă.

De exemplu, dacă luăm două numere prime 444388979 și 444388909, atunci „ cheie privată„ va fi 444388979, iar lucrarea 197481533549433911 (444388979*444388909) va fi transmisă în mod deschis. Numai cunoscând cealaltă jumătate a ta poți calcula numărul lipsă și descifra textul cu el.

Care este trucul aici? Ideea este că produsul a două numere prime nu este greu de calculat, dar operația inversă nu există - dacă nu cunoașteți prima parte, atunci o astfel de procedură poate fi efectuată numai prin forță brută. Și dacă luați numere prime cu adevărat mari (de exemplu, 2000 de caractere lungime), atunci decodarea produsului lor va dura câțiva ani chiar și pe un computer modern (până în care mesajul va fi de mult irelevant).

Geniul acestei scheme este că nu există nimic secret în algoritmul în sine - este deschis și toate datele sunt la suprafață (se cunosc atât algoritmul, cât și tabelele numerelor prime mari). Cifrul în sine, împreună cu cheie publică poate fi transmis în orice mod, în orice fel formă deschisă. Dar fără să cunoaștem partea secretă a cheii pe care a ales-o expeditorul, nu vom primi textul criptat. De exemplu, putem spune că o descriere a algoritmului RSA a fost publicată într-o revistă în 1977 și acolo a fost dat și un exemplu de cifru. Abia în 1993, cu ajutorul calculului distribuit pe calculatoarele a 600 de voluntari, s-a obţinut răspunsul corect.

Deci numerele prime s-au dovedit a nu fi deloc atât de simple, iar povestea lor în mod clar nu se termină aici.

• Traducere

Proprietățile numerelor prime au fost studiate pentru prima dată de matematicieni Grecia antică. Matematicienii școlii pitagoreice (500 - 300 î.Hr.) au fost interesați în primul rând de proprietățile mistice și numerologice ale numerelor prime. Au fost primii care au venit cu idei despre numere perfecte și prietenoase.

Un număr perfect are o sumă a propriilor divizori egală cu el însuși. De exemplu, divizorii proprii ai numărului 6 sunt 1, 2 și 3. 1 + 2 + 3 = 6. Împărțitorii numărului 28 sunt 1, 2, 4, 7 și 14. Mai mult, 1 + 2 + 4 + 7 + 14 = 28.

Numerele sunt numite prietenoase dacă suma divizorilor proprii ai unui număr este egală cu altul și invers - de exemplu, 220 și 284. Putem spune că un număr perfect este prietenos cu el însuși.

Pe vremea Elementelor lui Euclid în 300 î.Hr. Mai multe fapte importante despre numerele prime au fost deja dovedite. În Cartea a IX-a a Elementelor, Euclid a demonstrat că există un număr infinit de numere prime. Acesta, apropo, este unul dintre primele exemple de utilizare a demonstrației prin contradicție. El demonstrează, de asemenea, Teorema fundamentală a aritmeticii - fiecare număr întreg poate fi reprezentat în mod unic ca un produs al numerelor prime.

El a mai arătat că dacă numărul 2n-1 este prim, atunci numărul 2n-1 * (2n-1) va fi perfect. Un alt matematician, Euler, a reușit să arate în 1747 că toate sunt egale numere perfecte poate fi scris în această formă. Până în prezent nu se știe dacă există numere perfecte impare.

În anul 200 î.Hr. Greacul Eratosthenes a venit cu un algoritm pentru găsirea numerelor prime numit Sita lui Eratosthenes.

Și apoi a avut loc o mare pauză în istoria studiului numerelor prime, asociată cu Evul Mediu.

Următoarele descoperiri au fost făcute deja la începutul secolului al XVII-lea de către matematicianul Fermat. El a demonstrat conjectura lui Albert Girard că orice număr prim de forma 4n+1 poate fi scris unic ca sumă a două pătrate și a formulat, de asemenea, teorema că orice număr poate fi scris ca sumă a patru pătrate.

S-a dezvoltat noua metoda factorizarea numerelor mari și a demonstrat-o pe numărul 2027651281 = 44021 × 46061. El a demonstrat și Teorema Mică a lui Fermat: dacă p este un număr prim, atunci pentru orice număr întreg a va fi adevărat că a p = a modulo p.

Această afirmație dovedește jumătate din ceea ce era cunoscut sub numele de „conjectura chineză” și datează de 2000 de ani: un număr întreg n este prim dacă și numai dacă 2 n -2 este divizibil cu n. A doua parte a ipotezei s-a dovedit a fi falsă - de exemplu, 2.341 - 2 este divizibil cu 341, deși numărul 341 este compus: 341 = 31 × 11.

Mica Teoremă a lui Fermat a servit drept bază pentru multe alte rezultate în teoria numerelor și metode pentru a testa dacă numerele sunt numere prime - dintre care multe sunt încă folosite astăzi.

Fermat a corespuns foarte mult cu contemporanii săi, mai ales cu un călugăr pe nume Maren Mersenne. Într-una dintre scrisorile sale, el a emis ipoteza că numerele de forma 2 n +1 vor fi întotdeauna prime dacă n este o putere a doi. El a testat acest lucru pentru n = 1, 2, 4, 8 și 16 și a fost încrezător că, în cazul în care n nu este o putere a doi, numărul nu este neapărat prim. Aceste numere se numesc numerele lui Fermat și numai 100 de ani mai târziu Euler a arătat că următorul număr, 2 32 + 1 = 4294967297, este divizibil cu 641 și, prin urmare, nu este prim.

Numerele de forma 2 n - 1 au făcut, de asemenea, obiectul cercetării, deoarece este ușor de arătat că dacă n este compus, atunci numărul în sine este și compus. Aceste numere sunt numite numere Mersenne pentru că le-a studiat pe larg.

Dar nu toate numerele de forma 2 n - 1, unde n este prim, sunt prime. De exemplu, 2 11 - 1 = 2047 = 23 * 89. Acesta a fost descoperit pentru prima dată în 1536.

Timp de mulți ani, numerele de acest fel au oferit matematicienilor cele mai mari numere prime cunoscute. Că M 19 a fost dovedit de Cataldi în 1588 și timp de 200 de ani a fost cel mai mare număr prim cunoscut, până când Euler a dovedit că M 31 era și prim. Acest record a durat încă o sută de ani, apoi Lucas a arătat că M 127 este prim (și acesta este deja un număr de 39 de cifre), iar după aceea cercetările au continuat odată cu apariția computerelor.

În 1952, a fost dovedită caracterul prim al numerelor M 521, M 607, M 1279, M 2203 și M 2281.

Până în 2005, au fost găsite 42 de numere prime Mersenne. Cel mai mare dintre ele, M 25964951, este format din 7816230 de cifre.

Lucrarea lui Euler a avut un impact imens asupra teoriei numerelor, inclusiv asupra numerelor prime. El a extins Teorema Mică a lui Fermat și a introdus funcția φ. S-a factorizat al 5-lea număr Fermat 2 32 +1, a găsit 60 de perechi de numere prietenoase și a formulat (dar nu a putut dovedi) legea reciprocității pătratice.

El a fost primul care a introdus metode analiză matematicăși a dezvoltat teoria analitică a numerelor. El a demonstrat că nu numai seria armonică ∑ (1/n), ci și o serie de formă

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Diverge și rezultatul obținut prin suma reciprocelor numerelor prime. Suma n termeni ai seriei armonice crește aproximativ ca log(n), iar a doua serie diverge mai lent ca log[ log(n) ]. Aceasta înseamnă că, de exemplu, suma reciprocelor tuturor numerelor prime găsite până în prezent va da doar 4, deși seria încă diverge.

La prima vedere, se pare că numerele prime sunt distribuite destul de aleatoriu între numere întregi. De exemplu, printre cele 100 de numere imediat înainte de 10000000 există 9 numere prime, iar dintre cele 100 de numere imediat după această valoare sunt doar 2. Dar pe segmente mari numerele prime sunt distribuite destul de uniform. Legendre și Gauss s-au ocupat de problemele distribuției lor. Gauss i-a spus odată unui prieten că în orice 15 minute libere el numără întotdeauna numărul de numere prime din următoarele 1000 de numere. Până la sfârșitul vieții, numărase toate numerele prime până la 3 milioane. Legendre și Gauss au calculat în mod egal că pentru n mare densitatea primului este 1/log(n). Legendre a estimat numărul de numere prime în intervalul de la 1 la n ca

π(n) = n/(log(n) - 1,08366)

Și Gauss este ca o integrală logaritmică

π(n) = ∫ 1/log(t) dt

Cu un interval de integrare de la 2 la n.

Afirmația despre densitatea primei 1/log(n) este cunoscută sub numele de Teorema distribuției prime. Ei au încercat să demonstreze acest lucru de-a lungul secolului al XIX-lea, iar progresul a fost realizat de Cebyshev și Riemann. Au legat-o cu ipoteza Riemann, o ipoteză încă nedovedită despre distribuția zerourilor funcției zeta Riemann. Densitatea numerelor prime a fost demonstrată simultan de Hadamard și Vallée-Poussin în 1896.

Există încă multe întrebări nerezolvate în teoria numerelor prime, unele dintre ele vechi de sute de ani:

• Ipoteza prime gemene este despre un număr infinit de perechi de numere prime care diferă între ele cu 2
• Conjectura lui Goldbach: orice număr par, începând cu 4, poate fi reprezentat ca suma a două numere prime
• Există un număr infinit de numere prime de forma n 2 + 1?
• Este întotdeauna posibil să găsim un număr prim între n 2 și (n + 1) 2? (faptul că există întotdeauna un număr prim între n și 2n a fost demonstrat de Cebyshev)
• Numărul primelor Fermat este infinit? Există numere prime Fermat după 4?
• există oare progresie aritmetică de numere prime consecutive pentru orice lungime dată? de exemplu, pentru lungimea 4: 251, 257, 263, 269. Lungimea maximă găsită este 26.
• Există un număr infinit de mulțimi de trei numere prime consecutive într-o progresie aritmetică?
• n 2 - n + 41 este un număr prim pentru 0 ≤ n ≤ 40. Există un număr infinit de astfel de numere prime? Aceeași întrebare pentru formula n 2 - 79 n + 1601. Aceste numere sunt prime pentru 0 ≤ n ≤ 79.
• Există un număr infinit de numere prime de forma n# + 1? (n# este rezultatul înmulțirii tuturor numerelor prime mai mici decât n)
• Există un număr infinit de numere prime de forma n# -1?
• Există un număr infinit de numere prime de forma n? + 1?
• Există un număr infinit de numere prime de forma n? – 1?
• dacă p este prim, 2 p -1 nu conține întotdeauna pătrate prime printre factorii săi?
• secvența Fibonacci conține un număr infinit de numere prime?

Cele mai mari numere prime gemene sunt 2003663613 × 2 195000 ± 1. Sunt formate din 58711 cifre și au fost descoperite în 2007.

Cel mai mare număr prim factorial (de tipul n! ± 1) este 147855! - 1. Este format din 142891 de cifre și a fost găsit în 2002.

Cel mai mare număr prim primar (un număr de forma n# ± 1) este 1098133# + 1.

Toate numerele naturale, cu excepția unuia, sunt împărțite în numere prime și compuse. Un număr prim este un număr natural care are doar doi divizori: unul și el însuși. Toate celelalte sunt numite compozite. Studiul proprietăților numerelor prime este realizat de o ramură specială a matematicii - teoria numerelor. În teoria inelelor, numerele prime sunt legate de elemente ireductibile.

Iată o succesiune de numere prime care pornesc de la 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, ... etc.

Conform teoremei fundamentale a aritmeticii, fiecare număr natural mai mare decât unu poate fi reprezentat ca produs de numere prime. În același timp, aceasta este singura modalitate de a reprezenta numerele naturale până la ordinea factorilor. Pe baza acestui fapt, putem spune că numerele prime sunt părțile elementare ale numerelor naturale.

Această reprezentare a unui număr natural se numește descompunerea unui număr natural în numere prime sau factorizarea unui număr.

Una dintre cele mai vechi și moduri eficiente Calculul numerelor prime este „sita lui Erasstophenes”.

Practica a arătat că după calcularea numerelor prime folosind sita Erastofenilor, este necesar să se verifice dacă numărul dat este prim. În acest scop, au fost dezvoltate teste speciale, așa-numitele teste de simplitate. Algoritmul acestor teste este probabilistic. Ele sunt cel mai des folosite în criptografie.

Apropo, pentru unele clase de numere există teste de primalitate eficiente specializate. De exemplu, pentru a verifica primalitatea numerelor Mersenne se folosește testul Luc-Lehmer, iar pentru a verifica primalitatea numerelor Fermat se folosește testul Pepin.

Știm cu toții că există o infinitate de numere. Pe bună dreptate se pune întrebarea: câte numere prime există atunci? Există, de asemenea, un număr infinit de numere prime. Cea mai veche dovadă a acestei propoziții este dovada lui Euclid, care este prezentată în Elemente. Dovada lui Euclid arată astfel:

Să ne imaginăm că numărul de numere prime este finit. Să le înmulțim și să adăugăm una. Numărul rezultat nu poate fi împărțit la niciunul din setul finit de numere prime, deoarece restul împărțirii cu oricare dintre ele dă unul. Astfel, numărul trebuie să fie divizibil cu un număr prim care nu este inclus în această mulțime.

Teorema distribuției numerelor prime afirmă că numărul de numere prime mai mici decât n, notat cu π(n), crește ca n / ln(n).

După mii de ani de studiu a numerelor prime, cel mai mare număr prim cunoscut este 243112609 − 1. Acest număr are 12.978.189 de cifre zecimale și este numărul prim Mersenne (M43112609). Această descoperire a fost făcută pe 23 august 2008 la Facultatea de Matematică a Universității uCLA, ca parte a căutării distribuite pentru numere prime Mersenne proiect GIMPS.

Acasă trăsătură distinctivă Numerele Mersenne sunt prezența unui test de primalitate Luc-Lemaire extrem de eficient. Odată cu acesta, numerele prime Mersenne sunt, pe o perioadă lungă de timp, cele mai mari numere prime cunoscute.

Cu toate acestea, până în prezent, multe întrebări referitoare la numerele prime nu au primit răspunsuri precise. La cel de-al 5-lea Congres Internațional de Matematică, Edmund Landau a formulat principalele probleme din domeniul numerelor prime:

Problema lui Goldbach sau prima problemă a lui Landau este că este necesar să se demonstreze sau să se infirme că fiecare număr par mai mare de 2 poate fi reprezentat ca sumă a două numere prime și fiecare număr impar mai mare de 5 poate fi reprezentat ca o sumă. trei simple numere.
A doua problemă a lui Landau necesită găsirea unui răspuns la întrebarea: există un set infinit de „gemeni prime” - numere prime a căror diferență este 2?
Conjectura lui Legendre sau a treia problemă a lui Landau este: este adevărat că între n2 și (n + 1)2 există întotdeauna un număr prim?
A patra problemă a lui Landau: mulțimea numerelor prime de forma n2 + 1 este infinită?
Pe lângă problemele de mai sus, există și problema determinării unui număr infinit de numere prime în multe secvențe întregi, cum ar fi numărul Fibonacci, numărul Fermat etc.