Numerele prime: istorie și fapte. Cum să găsești numere prime

Teorema.

Există un număr infinit de numere prime.

Dovada.

Să presupunem că nu este cazul. Adică, să presupunem că există numai n numere prime, iar aceste numere prime sunt p 1, p 2, ..., p n. Să arătăm că putem găsi întotdeauna un număr prim diferit de cele indicate.

Se consideră numărul p egal cu p 1 ·p 2 ·…·p n +1. Este clar că acest număr este diferit de fiecare dintre numerele prime p 1, p 2, ..., p n. Dacă numărul p este prim, atunci teorema este demonstrată. Dacă acest număr este compus, atunci în virtutea teoremei anterioare există un divizor prim al acestui număr (îl notăm p n+1). Să arătăm că acest divizor nu coincide cu niciunul dintre numerele p 1, p 2, ..., p n.

Dacă nu ar fi așa, atunci, conform proprietăților de divizibilitate, produsul p 1 ·p 2 ·…·p n ar fi împărțit la p n+1. Dar numărul p este și divizibil cu p n+1, egal cu suma p 1 ·p 2 ·…·p n +1. Rezultă că p n+1 trebuie să împartă al doilea termen al acestei sume, care este egal cu unul, dar acest lucru este imposibil.

Astfel, s-a dovedit că se poate găsi întotdeauna un număr prim nou care nu este inclus între niciun număr de numere prime predeterminate. Prin urmare, există infinit de numere prime.

Deci, datorită faptului că există un număr infinit de numere prime, atunci când alcătuiești tabele cu numere prime, te limitezi întotdeauna de sus la un număr, de obicei 100, 1.000, 10.000 etc.

Sita lui Eratosthenes

Acum vom discuta modalități de a crea tabele de numere prime. Să presupunem că trebuie să facem un tabel cu numere prime până la 100.

Cea mai evidentă metodă de rezolvare a acestei probleme este verificarea succesivă a numerelor întregi pozitive, începând de la 2 și terminând cu 100, pentru prezența unui divizor pozitiv care este mai mare decât 1 și mai mic decât numărul testat (din proprietățile divizibilității pe care le cunoaștem că valoarea absolută a divizorului nu depășește valoarea absolută a dividendului, diferit de zero). Dacă nu se găsește un astfel de divizor, atunci numărul testat este prim și este introdus în tabelul numerelor prime. Dacă se găsește un astfel de divizor, atunci numărul testat este compus; NU este introdus în tabelul numerelor prime. După aceasta, există o tranziție la următorul număr, care este verificat în mod similar pentru prezența unui divizor.

Să descriem primii pași.

Începem cu numărul 2. Numărul 2 nu are alți divizori pozitivi decât 1 și 2. Prin urmare, este simplu, prin urmare, îl introducem în tabelul numerelor prime. Aici trebuie spus că 2 este cel mai mic număr prim. Să trecem la numărul 3. Posibilul său divizor pozitiv, altul decât 1 și 3, este numărul 2. Dar 3 nu este divizibil cu 2, prin urmare, 3 este un număr prim și, de asemenea, trebuie inclus în tabelul numerelor prime. Să trecem la numărul 4. Divizorii săi pozitivi, alții decât 1 și 4, pot fi numerele 2 și 3, să le verificăm. Numărul 4 este divizibil cu 2, prin urmare, 4 este un număr compus și nu trebuie inclus în tabelul numerelor prime. Vă rugăm să rețineți că 4 este cel mai mic număr compus. Să trecem la numărul 5. Verificăm dacă cel puțin unul dintre numerele 2, 3, 4 este divizorul său. Deoarece 5 nu este divizibil cu 2, 3 sau 4, atunci este prim și trebuie notat în tabelul numerelor prime. Apoi, există o tranziție la numerele 6, 7 și așa mai departe până la 100.

Această abordare de a compila un tabel de numere prime este departe de a fi ideală. Într-un fel sau altul, el are dreptul să existe. Rețineți că, cu această metodă de construire a unui tabel de numere întregi, puteți utiliza criterii de divizibilitate, care vor accelera ușor procesul de găsire a divizorilor.

Există o modalitate mai convenabilă de a crea un tabel de numere prime, numită. Cuvântul „sită” prezent în nume nu este întâmplător, deoarece acțiunile acestei metode ajută, parcă, la „cernerea” numerelor întregi și a unităților mari prin sita lui Eratostene pentru a separa cele simple de cele compuse.

Să arătăm sita lui Eratostene în acțiune atunci când alcătuim un tabel cu numere prime până la 50.

Mai întâi, notează numerele 2, 3, 4, ..., 50 în ordine.

Primul număr scris, 2, este prim. Acum, de la numărul 2, ne deplasăm secvențial la dreapta cu două numere și tăiem aceste numere până ajungem la sfârșitul tabelului cu numere în curs de compilare. Acest lucru va elimina toate numerele care sunt multipli de doi.

Primul număr care urmează după 2 care nu este tăiat este 3. Acest număr este prim. Acum, de la numărul 3, ne deplasăm succesiv la dreapta cu trei numere (ținând cont de numerele deja tăiate) și le tăiem. Acest lucru va elimina toate numerele care sunt multipli de trei.

Primul număr care urmează după 3 care nu este tăiat este 5. Acest număr este prim. Acum de la numărul 5 ne deplasăm în mod constant la dreapta cu 5 numere (luăm în considerare și numerele tăiate mai devreme) și le tăiem. Acest lucru va elimina toate numerele care sunt multipli de cinci.

Apoi, tăiem numerele care sunt multiplii lui 7, apoi multiplii lui 11 și așa mai departe. Procesul se termină când nu mai sunt numere de tăiat. Mai jos este tabelul completat al numerelor prime până la 50, obținute folosind sita lui Eratostene. Toate numerele neîncrucișate sunt prime și toate numerele tăiate sunt compuse.

Să formulăm și să demonstrăm și o teoremă care va grăbi procesul de compilare a unui tabel de numere prime folosind sita lui Eratostene.

Teorema.

Cel mai mic divizor pozitiv al unui număr compus a care este diferit de unul nu depășește , unde este de la a .

Dovada.

Să notăm cu litera b cel mai mic divizor al unui număr compus a care este diferit de unul (numărul b este prim, după cum reiese din teorema demonstrată chiar la începutul paragrafului precedent). Atunci există un număr întreg q astfel încât a=b·q (aici q este un număr întreg pozitiv, care decurge din regulile de înmulțire a numerelor întregi) și (pentru b>q condiția ca b este cel mai mic divizor al lui a este încălcată , întrucât q este și un divizor al numărului a datorită egalității a=q·b ). Înmulțind ambele părți ale inegalității cu un pozitiv și un număr întreg mai mare decât unu (ne este permis să facem acest lucru), obținem , din care și .

Ce ne oferă teorema dovedită cu privire la sita lui Eratostene?

În primul rând, tăierea numerelor compuse care sunt multipli ai unui număr prim b ar trebui să înceapă cu un număr egal cu (aceasta rezultă din inegalitate). De exemplu, tăierea numerelor care sunt multipli de doi ar trebui să înceapă cu numărul 4, multiplii de trei cu numărul 9, multiplii de cinci cu numărul 25 și așa mai departe.

În al doilea rând, alcătuirea unui tabel de numere prime până la numărul n folosind sita lui Eratostene poate fi considerată completă atunci când toate numerele compuse care sunt multipli de numere prime nu depășesc . În exemplul nostru, n=50 (deoarece facem un tabel cu numere prime până la 50) și, prin urmare, sita lui Eratostene ar trebui să elimine toate numerele compuse care sunt multiple ai numerelor prime 2, 3, 5 și 7 care nu nu depășește rădăcina pătrată aritmetică a lui 50. Adică, nu mai trebuie să căutăm și să tăiem numere care sunt multipli de numere prime 11, 13, 17, 19, 23 și așa mai departe până la 47, deoarece acestea vor fi deja tăiate ca multipli de numere prime mai mici 2. , 3, 5 și 7 .

Acest număr este prim sau compus?

Unele sarcini necesită a afla dacă un anumit număr este prim sau compus. În general, această sarcină este departe de a fi simplă, mai ales pentru numerele a căror scriere constă dintr-un număr semnificativ de caractere. În cele mai multe cazuri, trebuie să căutați o modalitate specifică de a o rezolva. Cu toate acestea, vom încerca să dăm direcție trenului de gândire pentru cazuri simple.

Desigur, puteți încerca să utilizați teste de divizibilitate pentru a demonstra că un anumit număr este compus. Dacă, de exemplu, un test de divizibilitate arată că un anumit număr este divizibil cu un număr întreg pozitiv mai mare decât unu, atunci numărul inițial este compus.

Exemplu.

Demonstrați că 898.989.898.989.898.989 este un număr compus.

Soluţie.

Suma cifrelor acestui număr este 9·8+9·9=9·17. Deoarece numărul egal cu 9·17 este divizibil cu 9, atunci prin divizibilitate cu 9 putem spune că și numărul inițial este divizibil cu 9. Prin urmare, este compozit.

Un dezavantaj semnificativ al acestei abordări este că criteriile de divizibilitate nu permit să se dovedească caracterul prim al unui număr. Prin urmare, atunci când testați un număr pentru a vedea dacă este prim sau compus, trebuie să faceți lucrurile diferit.

Cea mai logică abordare este de a încerca toți divizorii posibili ai unui număr dat. Dacă niciunul dintre divizorii posibili nu este un adevărat divizor al unui număr dat, atunci acest număr va fi prim, în caz contrar va fi compus. Din teoremele demonstrate în paragraful precedent rezultă că divizorii unui număr dat a trebuie căutați între numerele prime care nu depășesc . Astfel, un număr dat a poate fi împărțit succesiv la numere prime (care sunt luate în mod convenabil din tabelul numerelor prime), încercând să găsim divizorul numărului a. Dacă se găsește un divizor, atunci numărul a este compus. Dacă printre numerele prime care nu depășesc , nu există niciun divizor al numărului a, atunci numărul a este prim.

Exemplu.

Număr 11 723 simplu sau compus?

Soluţie.

Să aflăm până la ce număr prim pot fi divizorii numărului 11.723. Pentru a face acest lucru, să evaluăm.

Este destul de evident că , deoarece 200 2 =40.000 și 11.723<40 000 (при необходимости смотрите статью compararea numerelor). Astfel, posibilii factori primi ai lui 11.723 sunt mai mici de 200. Acest lucru ne face deja sarcina mult mai ușoară. Dacă nu am ști asta, atunci ar trebui să trecem prin toate numerele prime nu până la 200, ci până la numărul 11.723.

Dacă doriți, puteți evalua mai precis. Deoarece 108 2 =11.664 și 109 2 =11.881, atunci 108 2<11 723<109 2 , следовательно, . Astfel, oricare dintre numerele prime mai mici de 109 este potențial un factor prim al numărului dat 11.723.

Acum vom împărți succesiv numărul 11.723 în numere prime 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 . Dacă numărul 11.723 este împărțit la unul dintre numerele prime scrise, atunci va fi compus. Dacă nu este divizibil cu niciunul dintre numerele prime scrise, atunci numărul inițial este prim.

Nu vom descrie întreg acest proces monoton și monoton de divizare. Să spunem imediat că 11.723

număr prim

un număr natural mai mare decât unu și care nu are alți divizori decât el însuși și unul: 2, 3, 5, 7, 11, 13... Numărul numerelor prime este infinit.

număr prim

un întreg pozitiv mai mare decât unu, care nu are alți divizori decât el însuși și unul: 2, 3, 5, 7, 11, 13,... Conceptul de număr este fundamental în studiul divizibilității naturale (numere întregi pozitive). ) numere; Și anume, teorema principală a teoriei divizibilității stabilește că fiecare număr întreg pozitiv, cu excepția lui 1, este descompus unic în produsul unui număr de numere (nu se ia în considerare ordinea factorilor). Există infinit de numere prime (această propunere era cunoscută de matematicienii greci antici; dovezile sale sunt disponibile în a 9-a carte a Elementelor lui Euclid). Întrebările privind divizibilitatea numerelor naturale și, prin urmare, întrebările legate de numerele prime, sunt importante în studiul grupurilor; în special, structura unui grup cu un număr finit de elemente este strâns legată de modul în care acest număr de elemente (ordinea grupului) este descompus în factori primi. Teoria numerelor algebrice tratează problemele de divizibilitate a numerelor întregi algebrice; Conceptul de număr parțial s-a dovedit a fi insuficient pentru a construi o teorie a divizibilității, ceea ce a condus la crearea conceptului de ideal. P. G. L. Dirichlet a stabilit în 1837 că progresia aritmetică a + bx pentru x = 1, 2,... cu numere întregi coprime a și b conține infinit de numere prime.Determinarea distribuției numerelor prime în seria naturală a numerelor este foarte dificilă. problema in teoria numerelor. Se formulează ca un studiu al comportamentului asimptotic al funcției p(x), care denotă numărul de numere parțiale care nu depășesc un număr pozitiv x. Primele rezultate în această direcție aparțin lui P.L. Cebyshev, care în 1850 a demonstrat că există două constante a și A astfel încât ═< p(x) < ═при любых x ³ 2 [т. е., что p(х) растет, как функция ]. Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения П. ч. (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключающийся в том, что предел отношения p(х) к ═равен

Ulterior, eforturi semnificative ale matematicienilor au fost îndreptate spre clarificarea legii asimptotice a distribuției factorului de frecvență.Întrebările privind distribuția factorului de frecvență sunt studiate atât prin metode elementare, cât și prin metode de analiză matematică. Deosebit de fructuoasă este metoda bazată pe utilizarea identității

(produsul se extinde la toate P. h. p = 2, 3,...), mai întâi indicat de L. Euler; această identitate este valabilă pentru toate complexele cu o parte reală mai mare decât unitatea. Pe baza acestei identități, întrebările de distribuție a numerelor P. sunt conduse la studiul unei funcții speciale ≈ funcție zeta x(s), determinată pentru Res > 1 de serie

Această funcție a fost folosită în chestiunile privind distribuția numerelor prime pentru s reale de către Cebyshev; B. Riemann a subliniat importanța studierii x(s) pentru valorile complexe ale lui s. Riemann a emis ipoteza că toate rădăcinile ecuației x(s) = 0 aflate în semiplanul drept au o parte reală egală cu 1/

Această ipoteză nu a fost dovedită până în prezent (1975); dovada sa ar ajuta foarte mult în rezolvarea problemei distribuției numerelor prime.Întrebările privind distribuția numerelor prime sunt strâns legate de problema lui Goldbach, problema încă nerezolvată a „gemenilor” și alte probleme ale teoriei analitice a numerelor. Problema „gemenilor” este de a afla dacă numărul de numere P. care diferă cu 2 (cum ar fi, de exemplu, 11 și 13) este finit sau infinit. Tabelele cu numerele P. aflate în primele 11 milioane de numere naturale arată prezența unor „gemeni” foarte mari (de exemplu, 10006427 și 10006429), dar aceasta nu este o dovadă a infinitității numărului lor. În afara tabelelor compilate, se cunosc numere parțiale individuale care admit o expresie aritmetică simplă [de exemplu, s-a stabilit (1965) că 211213 ≈1 este un număr regulat; are 3376 de cifre].

Lit.: Vinogradov I.M., Fundamentals of Number Theory, ed. a VIII-a, M., 1972; Hasse G., Prelegeri despre teoria numerelor, trad. din germană, M., 1953; Ingham A.E., Distribuția numerelor prime, trad. din engleză, M. ≈ L., 1936; Prahar K., Distribuția numerelor prime, trad. din germană, M., 1967; Trost E., Numerele prime, traducere, din germană, M., 1959.

Wikipedia

număr prim

număr prim- un număr natural care are exact doi divizori naturali diferiți - și el însuși. Cu alte cuvinte, numărul X este prim dacă este mai mare decât 1 și este divizibil fără rest doar cu 1 și X. De exemplu, 5 este un număr prim, iar 6 este un număr compus, deoarece, pe lângă 1 și 6, este și divizibil cu 2 și 3.

Numerele naturale care sunt mai mari decât unu și nu sunt numere prime se numesc numere compuse. Astfel, toate numerele naturale sunt împărțite în trei clase: una. Teoria numerelor studiază proprietățile numerelor prime. În teoria inelelor, numerelor prime corespund elementelor ireductibile.

Secvența numerelor prime începe astfel:

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 …

• Traducere

Proprietățile numerelor prime au fost studiate pentru prima dată de matematicienii din 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 numerele par perfecte pot fi scrise î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.

El a dezvoltat o nouă metodă de factorizare a 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 demonstrat că M 31 a fost ș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 de 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 primelor 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ă o progresie aritmetică a numerelor 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.

Etichete: Adăugați etichete

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 „x mod y” (mod este o abreviere a cuvântului latin „modulo”, adică „modul”) î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 „devin” 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 evaluează manual această funcție pentru numere mari.