Articolul tratează conceptele de numere prime și compuse. Sunt date definiții ale unor astfel de numere cu exemple. Dăm o dovadă că numărul primelor este nelimitat și facem o intrare în tabelul primelor folosind metoda lui Eratostene. Se vor dovedi dacă un număr este prim sau compus.

Yandex.RTB R-A-339285-1

Numere prime și compuse - Definiții și exemple

Numerele prime și compuse sunt clasificate ca numere întregi pozitive. Ele trebuie să fie mai mari decât unul. Divizorii sunt, de asemenea, împărțiți în simpli și compuși. Pentru a înțelege conceptul de numere compuse, este necesar să studiem mai întâi conceptele de divizori și multipli.

Definiția 1

Numerele prime sunt numere întregi mai mari decât unu și au doi divizori pozitivi, adică ele însele și 1.

Definiția 2

Numerele compuse sunt numere întregi care sunt mai mari decât unu și au cel puțin trei divizori pozitivi.

Unul nu este nici prim, nici numar compus. Are un singur divizor pozitiv, deci este diferit de toate celelalte numere pozitive. Toate numerele întregi pozitive sunt numite naturale, adică folosite în numărare.

Definiția 3

numere prime sunt numere naturale care au doar doi divizori pozitivi.

Definiția 4

Numar compus este un număr natural care are mai mult de doi divizori pozitivi.

Orice număr mai mare decât 1 este prim sau compus. Din proprietatea divizibilității, avem că 1 și numărul a va fi întotdeauna divizori pentru orice număr a, adică va fi divizibil cu el însuși și cu 1. Oferim definiția numerelor întregi.

Definiția 5

Numerele naturale care nu sunt prime se numesc numere compuse.

Numerele prime: 2, 3, 11, 17, 131, 523. Ele sunt divizibile numai cu ei înșiși și cu 1. Numere compuse: 6, 63, 121, 6697. Adică, numărul 6 poate fi descompus în 2 și 3, iar 63 în 1, 3, 7, 9, 21, 63 și 121 în 11, 11, adică divizorii săi vor fi 1, 11, 121. Numărul 6697 se va descompune în 37 și 181. Rețineți că conceptele de numere prime și numere prime relativ sunt concepte diferite.

Pentru a ușura utilizarea numerelor prime, trebuie să utilizați un tabel:

Un tabel pentru toate numerele naturale existente este nerealist, deoarece există un număr infinit de ele. Când numerele ajung la dimensiuni de 10000 sau 1000000000, atunci ar trebui să te gândești să folosești sita lui Eratosthenes.

Luați în considerare o teoremă care explică ultima afirmație.

Teorema 1

Cel mai mic divizor pozitiv al unui număr natural mai mare decât 1, altul decât 1, este un număr prim.

Dovada 1

Să presupunem că a este un număr natural mai mare decât 1, b este cel mai mic divizor non-unic al lui a. Trebuie să demonstrăm că b este un număr prim folosind metoda contradicției.

Să presupunem că b este un număr compus. De aici avem că există un divizor pentru b, care este diferit de 1, precum și de b. Un astfel de divizor este notat cu b 1 . Este necesară această condiție 1< b 1 < b a fost completat.

Se poate observa din condiția că a este divizibil cu b, b este divizibil cu b 1, ceea ce înseamnă că conceptul de divizibilitate este exprimat astfel: a = b qși b = b 1 q 1 , de unde a = b 1 (q 1 q) , unde q și q 1 sunt numere întregi. Conform regulii înmulțirii numerelor întregi, avem că produsul numerelor întregi este un număr întreg cu o egalitate de forma a = b 1 · (q 1 · q) . Se poate observa că b 1 este divizorul lui a. Inegalitatea 1< b 1 < b nu potrivește, deoarece obținem că b este cel mai mic divizor pozitiv non-1 al lui a.

Teorema 2

Există infinit de numere prime.

Dovada 2

Să presupunem că luăm un număr finit de numere naturale n și notăm p 1 , p 2 , … , p n . Să luăm în considerare o variantă de găsire a unui număr prim diferit de cele indicate.

Se consideră numărul p, care este egal cu p 1 , p 2 , … , p n + 1 . Nu este egal cu fiecare dintre numerele corespunzătoare numerelor prime de forma p 1 , p 2 , … , p n . Numărul p este prim. Atunci teorema este considerată a fi demonstrată. Dacă este compus, atunci trebuie să luăm notația p n + 1 și arată nepotrivirea divizorului cu oricare dintre p 1 , p 2 , … , p n .

Dacă nu ar fi așa, atunci, pe baza proprietății de divizibilitate a produsului p 1 , p 2 , … , p n , obținem că ar fi divizibil cu p n + 1 . Rețineți că expresia p n + 1 numărul p este împărțit egal cu suma p 1 , p 2 , … , p n + 1 . Obținem că expresia p n + 1 al doilea termen al acestei sume, care este egal cu 1, trebuie împărțit, dar acest lucru este imposibil.

Se poate observa că orice număr prim poate fi găsit între orice număr de numere prime date. Rezultă că există infinit de numere prime.

Deoarece există o mulțime de numere prime, tabelele sunt limitate la numerele 100, 1000, 10000 și așa mai departe.

Atunci când compilați un tabel de numere prime, ar trebui să țineți cont de faptul că o astfel de sarcină necesită o verificare secvențială a numerelor, începând de la 2 la 100. Dacă nu există divizor, acesta este înregistrat în tabel; dacă este compus, atunci nu este introdus în tabel.

Să luăm în considerare pas cu pas.

Dacă începeți cu numărul 2, atunci acesta are doar 2 divizori: 2 și 1, ceea ce înseamnă că poate fi introdus în tabel. Tot cu cifra 3 . Numărul 4 este compus, ar trebui descompus în 2 și 2. Numărul 5 este prim, ceea ce înseamnă că poate fi fixat în tabel. Faceți asta până la numărul 100.

Această metodă este incomodă și necesită timp. Puteți face o masă, dar va trebui să petreceți mult timp. Este necesar să se utilizeze criterii de divizibilitate, care vor grăbi procesul de găsire a divizorilor.

Metoda care utilizează sita lui Eratosthenes este considerată cea mai convenabilă. Să aruncăm o privire la tabelele de mai jos. Pentru început, se scriu numerele 2, 3, 4, ..., 50.

Acum trebuie să tăiați toate numerele care sunt multipli de 2. Efectuați baraj secvențial. Obținem un tabel de forma:

Să trecem la tăierea numerelor care sunt multipli de 5. Primim:

Tăiem numerele care sunt multipli ai lui 7, 11. În sfârșit, tabelul arată ca

Să trecem la formularea teoremei.

Teorema 3

Cel mai mic divizor pozitiv și non-1 al numărului de bază a nu depășește a , unde a este rădăcina aritmetică a numărului dat.

Dovada 3

Este necesar să notăm b ca cel mai mic divizor al unui număr compus a. Există un întreg q , unde a = b · q , și avem că b ≤ q . O inegalitate a formei b > q deoarece condiția este încălcată. Ambele părți ale inegalității b ≤ q ar trebui înmulțite cu orice număr pozitiv b care nu este egal cu 1. Obținem că b b ≤ b q , unde b 2 ≤ a și b ≤ a .

Din teorema demonstrată se poate observa că ștergerea numerelor din tabel conduce la faptul că este necesar să se înceapă cu un număr egal cu b 2 și care satisface inegalitatea b 2 ≤ a . Adică, dacă tăiați numerele care sunt multipli de 2, atunci procesul începe de la 4, iar cele care sunt multipli de 3 încep de la 9 și așa mai departe până la 100.

Compilarea unui astfel de tabel folosind teorema lui Eratostene spune că atunci când toate numerele compuse sunt tăiate, vor rămâne primele care nu depășesc n. În exemplul în care n = 50 , avem că n = 50 . De aici obținem că sita lui Eratosthenes cerne toate numerele compuse care nu sunt mai mari ca valoare decât valoarea rădăcinii lui 50. Căutarea numerelor se face prin tăiere.

Înainte de a rezolva, este necesar să aflăm dacă numărul este prim sau compus. Criteriile de divizibilitate sunt adesea folosite. Să ne uităm la asta în exemplul de mai jos.

Exemplul 1

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

Decizie

Suma cifrelor numărului dat este 9 8 + 9 9 = 9 17 . Deci numărul 9 17 este divizibil cu 9, pe baza semnului divizibilității cu 9. Rezultă că este compus.

Astfel de semne nu sunt capabile să demonstreze primitatea unui număr. Dacă este necesară verificarea, ar trebui luate alți pași. Cel mai potrivit mod este de a enumera numerele. În timpul procesului, pot fi găsite numere prime și compuse. Adică, numerele în valoare nu trebuie să depășească un . Adică, numărul a trebuie descompus în factori primi. dacă acest lucru este adevărat, atunci numărul a poate fi considerat prim.

Exemplul 2

Determinați numărul compus sau prim 11723.

Decizie

Acum trebuie să găsiți toți divizorii numărului 11723. Trebuie evaluat 11723 .

De aici vedem că 11723< 200 , то 200 2 = 40 000 , și 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Pentru o estimare mai precisă a numărului 11723, este necesar să scrieți expresia 108 2 = 11 664 și 109 2 = 11 881 , apoi 108 2 < 11 723 < 109 2 . De aici rezultă că 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

La descompunere, obținem că 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 53 , 59 , 61 , 7, 7, 7, 7, 6 83 , 89 , 97 , 101 , 103 , 107 sunt toate numere prime. Întregul proces poate fi descris ca o împărțire pe o coloană. Adică, împărțiți 11723 la 19. Numărul 19 este unul dintre factorii săi, deoarece obținem împărțirea fără rest. Să descriem împărțirea după o coloană:

Rezultă că 11723 este un număr compus, deoarece în plus față de el și 1 are un divizor 19 .

Răspuns: 11723 este un număr compus.

Dacă observați o greșeală în text, vă rugăm să o evidențiați și să apăsați Ctrl+Enter

Lista divizorilor. Prin definiție, numărul n este prim numai dacă nu este divizibil egal cu 2 și cu orice numere întregi, altele decât 1 și el î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 mai mic sau egal cu x.

Aflați despre aritmetica modulară. Operația „x mod y” (mod este prescurtarea cuvântului latin „modulo”, care înseamnă „modul”) înseamnă „împarte 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 întorc” înapoi la zero. De exemplu, un ceas măsoară timpul în modulul 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.

Aflați despre capcanele Micii Teoreme a lui Fermat. Toate numerele pentru care nu sunt îndeplinite condițiile de testare sunt compuse, dar numerele rămase sunt doar probabil sunt considerate simple. Dacă doriți să evitați rezultatele incorecte, căutați nîn lista „numerelor Carmichael” (numerele compuse care îndeplinesc acest test) și „numerelor Fermat pseudo-prime” (aceste numere îndeplinesc condițiile testului doar pentru unele valori A).

Dacă este convenabil, utilizați testul Miller-Rabin. Deși această metodă este destul de greoaie pentru calculele manuale, este adesea folosită în programele de calculator. Oferă viteză acceptabilă și dă mai puține erori decât metoda Fermat. Un număr compus nu va fi luat ca număr prim dacă se fac calcule pentru mai mult de ¼ de valori A. Dacă selectați aleatoriu valori diferite A iar pentru toate testul va da un rezultat pozitiv, putem presupune cu un grad destul de ridicat de încredere că n este un număr prim.

Pentru numere mari, utilizați aritmetica modulară. Dacă nu aveți un calculator de mod la îndemână sau dacă calculatorul dvs. nu este conceput pentru a gestiona numere atât de mari, utilizați proprietățile puterii și aritmetica modulară pentru a vă ușura calculele. Mai jos este un exemplu pentru 3 50 (\displaystyle 3^(50)) mod 50:

• Rescrieți expresia într-o formă mai convenabilă: mod 50. Când se calculează manual, pot fi necesare simplificări suplimentare.
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Aici am luat în considerare proprietatea înmulțirii modulare.
• 3 25 (\displaystyle 3^(25)) mod 50 = 43.
• (3 25 (\displaystyle (3^(25))) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
• = 1849 (\displaystyle =1849) mod 50.
• = 49 (\displaystyle=49).

• Traducere

Proprietățile numerelor prime au fost studiate pentru prima dată de matematicienii Greciei antice. 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 proprii divizori egali 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.

Până la momentul apariției lucrării „Începuturilor” lui Euclid în anul 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. Apropo, acesta este unul dintre primele exemple de utilizare a dovezii prin contradicție. El demonstrează, de asemenea, Teorema de bază a aritmeticii - fiecare număr întreg poate fi reprezentat într-un mod unic ca produs de numere prime.

El a mai arătat că dacă numărul 2 n -1 este prim, atunci numărul 2 n-1 * (2 n -1) va fi perfect. Un alt matematician, Euler, în 1747 a fost capabil să arate 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 asociate 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 o sumă a două pătrate și, de asemenea, a formulat o teoremă conform căreia orice număr poate fi reprezentat ca o sumă a patru pătrate.

El a dezvoltat o nouă metodă de factorizare pentru numere 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, a p = a modulo p va fi adevărată. .

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

Mica Teoremă a lui Fermat a stat la baza multor alte rezultate în teoria numerelor și metode de testare dacă numerele sunt prime, multe dintre ele fiind încă utilizate astăzi.

Fermat a corespuns extins cu contemporanii săi, în special cu un călugăr pe nume Marin Mersenne. Într-una dintre scrisorile sale, el a presupus 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 sigur că atunci când n nu este o putere a doi, numărul nu era neapărat prim. Aceste numere se numesc numere Fermat și abia 100 de ani mai târziu Euler a arătat că următorul număr, 232 + 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ă el le-a studiat în mod activ.

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 dat matematicienilor cele mai mari numere prime cunoscute. Că numărul 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 este și prim. Acest record a ținut încă o sută de ani, iar 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, s-a dovedit primitatea 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 reușit să demonstreze) legea pătratică a reciprocității.

El a fost primul care a introdus metodele 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 +…

Obținut prin suma cantităților inverse numerelor prime, de asemenea, diverge. Suma celor n termeni ai seriei armonice crește aproximativ ca log(n), în timp ce 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 între numere întregi mai degrabă aleatoriu. 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 segmentele mari, numerele prime sunt distribuite destul de uniform. Legendre și Gauss s-au ocupat de distribuția 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, el numărase toate numerele prime până la 3 milioane. Legendre și Gauss au calculat în mod egal că pentru n mare densitatea primelor este 1/log(n). Legendre a estimat numărul de prime între 1 și n ca

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

Și Gauss - ca o integrală logaritmică

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

Cu un interval de integrare de la 2 la n.

Afirmația despre densitatea numerelor prime 1/log(n) este cunoscută sub numele de Teorema numerelor prime. Au încercat să demonstreze acest lucru de-a lungul secolului al XIX-lea, iar Cebyshev și Riemann au făcut progrese. Ei l-au conectat cu Ipoteza Riemann, o conjectie nedovedită până acum despre distribuția zerourilor funcției zeta Riemann. Densitatea numerelor prime a fost demonstrată simultan de Hadamard și de la Vallée-Poussin în 1896.

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

• ipoteza prime gemene - 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 de la 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)
• Există un număr infinit de numere prime Fermat? există numere prime Fermat după a 4-a?
• 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? - unu?
• dacă p este prim, 2 p -1 nu include întotdeauna printre factorii primelor pătrate
• 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 găsite în 2007.

Cel mai mare număr prim factorial (de forma 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.

• Traducere

Proprietățile numerelor prime au fost studiate pentru prima dată de matematicienii Greciei antice. 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 proprii divizori egali 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.

Până la momentul apariției lucrării „Începuturilor” lui Euclid în anul 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. Apropo, acesta este unul dintre primele exemple de utilizare a dovezii prin contradicție. El demonstrează, de asemenea, Teorema de bază a aritmeticii - fiecare număr întreg poate fi reprezentat într-un mod unic ca produs de numere prime.

El a mai arătat că dacă numărul 2 n -1 este prim, atunci numărul 2 n-1 * (2 n -1) va fi perfect. Un alt matematician, Euler, în 1747 a fost capabil să arate 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 asociate 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 o sumă a două pătrate și, de asemenea, a formulat o teoremă conform căreia orice număr poate fi reprezentat ca o sumă a patru pătrate.

El a dezvoltat o nouă metodă de factorizare pentru numere 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, a p = a modulo p va fi adevărată. .

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

Mica Teoremă a lui Fermat a stat la baza multor alte rezultate în teoria numerelor și metode de testare dacă numerele sunt prime, multe dintre ele fiind încă utilizate astăzi.

Fermat a corespuns extins cu contemporanii săi, în special cu un călugăr pe nume Marin Mersenne. Într-una dintre scrisorile sale, el a presupus 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 sigur că atunci când n nu este o putere a doi, numărul nu era neapărat prim. Aceste numere se numesc numere Fermat și abia 100 de ani mai târziu Euler a arătat că următorul număr, 232 + 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ă el le-a studiat în mod activ.

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 dat matematicienilor cele mai mari numere prime cunoscute. Că numărul 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 este și prim. Acest record a ținut încă o sută de ani, iar 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, s-a dovedit primitatea 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 reușit să demonstreze) legea pătratică a reciprocității.

El a fost primul care a introdus metodele 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 +…

Obținut prin suma cantităților inverse numerelor prime, de asemenea, diverge. Suma celor n termeni ai seriei armonice crește aproximativ ca log(n), în timp ce 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 între numere întregi mai degrabă aleatoriu. 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 segmentele mari, numerele prime sunt distribuite destul de uniform. Legendre și Gauss s-au ocupat de distribuția 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, el numărase toate numerele prime până la 3 milioane. Legendre și Gauss au calculat în mod egal că pentru n mare densitatea primelor este 1/log(n). Legendre a estimat numărul de prime între 1 și n ca

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

Și Gauss - ca o integrală logaritmică

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

Cu un interval de integrare de la 2 la n.

Afirmația despre densitatea numerelor prime 1/log(n) este cunoscută sub numele de Teorema numerelor prime. Au încercat să demonstreze acest lucru de-a lungul secolului al XIX-lea, iar Cebyshev și Riemann au făcut progrese. Ei l-au conectat cu Ipoteza Riemann, o conjectie nedovedită până acum despre distribuția zerourilor funcției zeta Riemann. Densitatea numerelor prime a fost demonstrată simultan de Hadamard și de la Vallée-Poussin în 1896.

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

• ipoteza prime gemene - 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 de la 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)
• Există un număr infinit de numere prime Fermat? există numere prime Fermat după a 4-a?
• 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? - unu?
• dacă p este prim, 2 p -1 nu include întotdeauna printre factorii primelor pătrate
• 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 găsite în 2007.

Cel mai mare număr prim factorial (de forma 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

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 se ocupă de o secțiune 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 care este mai mare decât unu poate fi reprezentat ca produs de numere prime. Totuși, aceasta este singura modalitate de a reprezenta numere naturale până la ordinea factorilor. Pe baza acestui fapt, putem spune că numerele prime sunt părțile elementare ale numerelor naturale.

O astfel de 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 mai eficiente modalități de a calcula numere prime este „siuta lui Erastothenes”.

Practica a arătat că după calcularea numerelor prime folosind sita Erastofen, este necesar să se verifice dacă numărul dat este prim. Pentru aceasta, au fost dezvoltate teste speciale, așa-numitele teste de simplitate. Algoritmul acestor teste este probabilistic. Cel mai adesea sunt folosite în criptografie.

Apropo, pentru unele clase de numere există teste de primalitate eficiente specializate. De exemplu, pentru a testa simplitatea numerelor Mersenne, se folosește testul Lucas-Lehmer, iar pentru a testa simplitatea 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 sunt atunci? Există, de asemenea, un număr infinit de numere prime. Cea mai veche dovadă a acestei judecăți este dovada lui Euclid, care este expusă în Elemente. Dovada lui Euclid este următoarea:

Imaginează-ți că numărul primelor 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 la 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).

De-a lungul a mii de ani de studiu a numerelor prime, s-a descoperit că cel mai mare număr prim cunoscut este 243112609 − 1. Acest număr are 12.978.189 de cifre zecimale și este un prim Mersenne (M43112609). Această descoperire a fost făcută pe 23 august 2008 la Departamentul de Matematică al Universității uCLA, ca parte a căutării distribuite GIMPS pentru numerele prime Mersenne.

Principala caracteristică distinctivă a numerelor Mersenne este prezența unui test de primalitate Luc-Lehmer extrem de eficient. Odată cu acesta, numerele prime de Mersenne sunt, pe o perioadă lungă de timp, cele mai mari numere prime cunoscute.

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

Problema Goldbach, sau prima problemă a lui Landau, este să dovedească sau să infirme că fiecare număr par mai mare de doi poate fi reprezentat ca suma a două numere prime, iar fiecare număr impar mai mare de 5 poate fi reprezentat ca suma a trei numere prime.
A doua problemă a lui Landau necesită găsirea unui răspuns la întrebarea: există un set infinit de „gemeni simpli” - numere prime, a căror diferență este egală cu 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 precum numărul Fibonacci, numărul Fermat etc.