Multimea Numerelor Prime

1. Introducere

“Matematica este regina științelor și teoria numerelor este regina matematicii.”
Gauss

Numerele naturale au fascinat dintotdeauna omenirea, ce le-a considerat, pe bună dreptate, ca fiind mai mult decât mijloace de a studia cantitățile, le-a considerat entități având o personalitate proprie. Mistica tuturor popoarelor abundă de proprietăți supranaturale atribuite numerelor. Într-adevăr, pare că, pe măsură ce le cercetezi mai adânc, descoperi că au „consistență”, că, departe de a fi o creație conceptuală a omului, un simplu instrument la îndemâna sa, se conduc de fapt după legități proprii, pe care nu-ți permit să le influențezi, ci doar să le descoperi.

Printre primii oameni care au simțit acest lucru se numără Pitagora, ce a început prin a cerceta numerele și a sfârșit prin a întemeia o mișcare religioasă puternic fondată pe simbolistica numerelor. Pasiunea sa pentru numerele naturale era atât de mare (accepta, totuși, și existența numerelor raționale, ce sunt, în fond, tot un raport de numere naturale), încât circulă o legendă conform căreia și-ar fi înecat un discipol pentru „vina” de a-i fi relevant existența numerelor iraționale.

Numerele prime precum și proprietățile acestora au fost studiate intens de matematicienii încă din Grecia Antică. Matematicienii școlii pitagoreice erau fascinați de studiul numerelor datorită proprietăților mistice ale acestora. Aceștia au înțeles încă de pe atunci ideea de primalitate și erau interesați în studiul numerelor perfecte și al numerelor prietene. În vremea aceea „Elementele” lui Euclid apărută în jur de 300 i.Ch demonstra câteva rezultate importante despre numerele prime. Euclid a demonstrat că există o infinitate de numere prime, fiind una dintre primele demonstrații cunoscute care folosește metoda contradicției ca să stabilească un rezultat.

La o primă vedere, numerele prime par să fie distribuite printre numerele întregi într-un mod întâmplător. De exemplu din 100 de numere luate din fața lui 10 000 000 sunt 9 numere prime, în timp ce tot în 100 de numere, dar după 10 000 000 sunt doar 2 prime. În jur de 200 i.Ch matematicianul grec Eratostene propune un algoritm pentru calculul numerelor prime, numit Ciurul lui Eratostene. Un alt pas important a fost făcut de Fermat la începutul secolului al 17-lea. Până atunci Teoria Numerelor a suferit perioade destul de nefaste. Fermat a demonstrat speculațiile lui Albert Girard că fiecare număr prim de forma 4*n+1 poate fi scris în mod unic ca suma de 2 pătrate perfecte și a fost capabil să demonstreze cum orice număr poate fi scris ca suma de patru pătrate perfecte.

Fermat a propus o metoda de factorizare a numerelor mari pe care a demonstrat-o factorizând numărul 2027651281 = 44021*46061. A demonstrat ceea ce avea să devină cunoscută sub denumirea de Mica teorema a lui Fermat: dacă p este un număr prim atunci pentru orice număr întreg a avem: ap = a modulo p. Această formulă a demonstrat jumătate din ceea ce a fost denumită „ipoteza chinezească”, veche de peste 2000 de ani, conform căreia un număr întreg n este prim dacă și numai dacă numărul 2*n – 2 este divizibil la n. Cealaltă jumătate a acestei afirmații este falsă, contradicția constituind-o faptul că, de exemplu, 2341 – 2 este divizibil la 341, chiar dacă numărul 341=31*11 este un număr compus. Mica Teorema a lui Fermat constituie fundamentul pentru multe alte rezultate din Teoria Numerelor și reprezintă baza metodelor de verificare a primalității unui număr, metodă folosită pe scară largă în domeniul calculatoarelor.

Fermat a corespondat cu alți matematicieni ai vremurilor lui și în particular cu călugărul Marin Mersenne. Într-una din scrisorile sale către Mersenne, Fermat a lansat ipoteza că numerele 2*n + 1 ar fi întotdeauna prime dacă n este o putere a lui 2. El a verificat aceasta pentru n = 1, 2, 4, 8 și 16 și știa că dacă n nu era o putere a lui 2, rezultatul eșua. Numerele de această formă sunt numite numere Fermat și nu au trecut mai mult de 100 de ani până când Euler a arătat că 232 + 1 = 4294967297 este divizibil la 641, deci nu este prim. Euler prin descoperirile sale a avut un impact deosebit asupra Teoriei Numerelor în general și asupra numerelor prime în particular. El a extins Mica Teorema a lui Fermat și a introdus funcția a lui Euler. Cum am menționat anterior el a factorizat al 5-lea număr Fermat 232 + 1, a găsit 60 de perechi de numere prietene și a stabilit (dar nu a reușit să demonstreze ) ceea ce a devenit cunoscuta drept Legea Reciprocității Pătratice.

Euler a fost primul care a realizat că teoria numerelor poate fi studiată folosind unelte ale analizei matematice. El a arătat că nu numai așa-numita serie armonica (1/n) este divergentă, dar și seria

formată prin însumarea inverselor numerelor prime este tot divergentă.

S-ar putea pretinde că analiza matematică a început cu Euler. Euler a contribuit la cunoașterea a multor alte domenii, și în toate a implicat cunoștințele sale de matematică.

Lucrarea de față se intitulează ”Numere prime și pseudoprime” și își propune să trateze câteva aspecte legate despre aceste două noțiuni. Este structurată în trei capitole.

În capitolul, ”Noțiuni introductive”, sunt amintite noțiuni importante de aritmetică necesare în capitolele următoare.

Capitolul 3, ”Mulțimea numerelor prime”, conține noțiuni preliminare despre numerele prime, apoi prezintă câteva teoreme reprezentative pentru numerele prime, dar și aplicații cu astfel de numere.

Capitolul 4, „Numere pseudoprime”, realizează o introducere în mulțimea numerelor pseudoprime, precum și o prezentare pentru o parte dintre numerele pseudoprime cunoscute, printre care Carmichael, Euler, Fermat, Catalan.

2. Noțiuni introductive

În acest capitol sunt prezentate câteva noțiuni și proprietăți din aritmetică, utile în capitolele următoare. Demonstrațiile complete pentru teoremele prezentate pot fi găsite de cei interesați în lucrările Bușneag,D., Chirteș,F., Piciu, D.[5], Burton, D.M.[ 4 ], Rosen, K.H. [24].

Definiția 2.1: Dacă spunem că și scriem , dacă există astfel încât (nu definim divizibilitatea prin ). În acest caz spunem că este un divizor al lui (sau că este multiplu de ).

În loc de () putem folosi noțiunea ().

Relația de divizibilitate de pe fiind reflexivă, antisimetrică și tranzitivă, mulțimea (, |) este o mulțime ordonată (chiar mai mult, o latice) în care 1 este cel mai mic element (element inițial) iar 0 este cel mai mare element (element final).

Definiția 2.2: Un număr p este prim dacă singurii săi divizori sunt 1 și

. Cele mai mici numere prime sunt 2, 3, 5, etc.

Teorema 2.3 (Teorema împărțirii cu rest în : Dacă , atunci există și sunt unici astfel încât , iar . Numărul se numește câtul împărțirii lui la . Numărul reprezintă restul acestei împărțiri (evident dacă și numai dacă ).

Teorema 2.4: Fiind date două numere , există d (vom nata astfel încât , , iar dacă mai avem astfel încât și , atunci (adică în mulțimea parțial ordonată ( pentru orice două elemente există (.

Observații:

Numărul poartă numele de cel mai mare divizor comun al lui și .

Dacă pentru avem , vom spune despre și că sunt prime între ele.

Cel mai mic multiplu comun al două numere naturale și diferite de 0, notat (sau pur și simplu ), este numărul întreg pozitiv , care îndeplinește condițiile:

și

dacă și , atunci .

Inductiv se arată că pentru oricare numere naturale există astfel încât pentru orice atunci . Numărul se notează prin și poartă numele de cel mai mare divizor comun al numerelor (și analog se definește cel mai mic multiplu comun al acetor numere)

Dacă și atunci

Relația de divizibilitate pe ℕ se poate extinde la mulțimea ℤ a numerelor întregi:

Definiția 2.5: Dacă , , spunem că divide () dacă există astfel încât (nu definim divizibilitatea prin ). Dacă atunci

Numerele prime în se definesc ca fiind numerele întregi cu proprietatea că , iar singurii divizori ai lui p sunt .

Numerele prime din sunt numerele de forma , cu număr prim în .

Se verifică imediat că dacă , atunci:

(

Dacă și , atunci (deci în relația de divizibilitate nu mai este antisimetrică).

Dacă și , atunci .

Teorema 2.6 (Teorema împărțirii cu rest în : Dacă , , atunci există a. î. .

Observații:

Teorema împărțirii cu rest din poate fi formulată: Dacă , există astfel încât , iar .

Numerele se numesc câtul și restul împărțirii lui la . Numerele cu proprietatea enunțață mai sus sunt unice, deoarece dacă am mai avea și astfel încât , cu , atunci dacă și numai dacă , adică . Deoarece , , dacă presupunem că , atunci , iar condiția implică

. Deoarece .

Un întreg care nu este un prim este numit număr compus.

Definiție 2.7: Fie un număr întreg pozitiv fix. Două numere întregi și sunt congruente modulo , notat , dacă divide diferența (ceea ce înseamnă că pentru un număr întreg ).

Observații:

Fie și . Puterea lui modulo (in terminologia veche: exponentul căruia îi aparține modulo ) este cel mai mic număr întreg astfel incât . Notăm puterea lui modulo cu .

Funcția a lui Euler. Pentru , reprezintă cardinalul numerelor întregi pozitive care nu sunt mai mari decat și sunt prime cu , deci:

: ℕ*→ℂ , (m) = |{ x ∈ ℕ* | 1 ≤ x ≤ m, (x,m)=1 }|.

Dacă p este un număr prim, atunci evident (p)=p-1. Dacă este o putere a unui număr prim p, există numere pozitive mai mici decât , din care sunt multipli de , iar restul sunt prime cu. Prin urmare:

Dacă și este de exponentul modulo , atunci se numește rădăcină primitivă a lui .

Fie un număr prim impar și un număr întreg astfel încât . Dacă congruența are o soluție, atunci se numește rest pătratic modulo .

Fie un număr prim și , simbolul Legendre este definit astfel:

Atunci: (Gauss) și pentru p,q prime, impare, distincte(legea reciprocității pătratice).

Fie și , și numere întregi relativ prime, cu impar. Dacă este descompunerea lui în factori primi impari (nu neapărat distincți) atunci simbolul Jacobi este definit astfel:

.

Teorema 2.8: Dacă , , …, , unde sunt întregi cu , numere pozitive atunci .

Teorema 2.9 (Teorema lui Euler): Dacă este număr întreg pozitiv, cu , atunci .

Teorema 2.10: Dacă și sunt numere întregi relativ prime, cu , atunci numărul întreg pozitiv este o soluție a congruenței dacă și numai dacă .

Teorema 2.11(Criteriul lui Euler): Fie p un număr prim impar și a un numar întreg pozitiv care nu se divide la p atunci

Teorema 2.12: Fie n un număr natural impar, a și b prime între ele și cu n, atunci

dacă , atunci

Teorema 2.13 (Teorema chinezească a resturilor): Fie numere naturale, a.î. ( pentru orice , iar numere întregi, sistemul

are o soluție în și oricare două soluții diferă printr-un multiplu de .

Teorema 2.14 (Teorema fundamentală a aritmeticii): Orice număr întreg diferit de zero și de este un produs finit de numere prime.

Teorema 2.15: Fie numere întregi pozitive; dacă este prim și , atunci congruența are soluții dacă , unde și nici o soluție dacă .

3. Mulțimea numerelor prime

“Dumnezeu a inventat numerele întregi; restul este munca omului.”
Kronecker

3.1 Preliminarii

Înțelegem numerele prime studiind probleme simple care apar în legătură cu o operație aritmetică elementară ca de exemplu înmulțirea unor numere naturale, adică numere întregi pozitive. După cum se știe produsul a două numere naturale este întotdeauna un număr natural, deci există numere naturale care reprezintă produsul a două numere naturale mai mari decât unitatea. Există, de asemenea, numere naturale mai mari decât unitatea care nu sunt produsul a două numere naturale mai mari decât unitatea, de exemplu, numerele 2, 3, 5 sau 13. Tocmai aceste numere le numim prime.

Astfel, un număr prim este un număr natural, mai mare decât unitatea, care nu este produsul a două numere naturale mai mari decât unitatea.

Ne întrebăm dacă pentru orice număr natural n>1 avem posibilitatea să stabilim dacă este prim sau nu, definiția unui număr prim ne permite să dăm răspunsul la această întrebare. Într-adevăr, dacă numărul natural n>1 nu este prim, atunci el reprezintă produsul a două numere naturale a și b mai mari decât unitatea, adică , unde și , rezultă imediat că și n. Numărul nnefiind prim, este deci produsul a două numere natural mai mici decât n, astfel de numere le numim compuse. Dacă numărul n este compus, atunci, unde și , și . Câtul , este un număr natural, deci a este divizor al numărului n mai mare decât 1 și mai mic decât n.

Pentru a ne convinge că este prim este suficient să constatăm că nu are un divizor mai mare ca 1 și mai mic ca n. Pentru asta este suficient să efectuăm împărțiri consecutive ale numărului n la numerele, dacă nici una din împărțiri nu se face exact, atunci și numai atunci numărul n este prim.

Astfel, cel puțin teoretic, se poate constata oricând (folosind un număr finit de împărțiri) dacă n număr natural este prim sau nu. Folosind această metodă, în practică pot aparea dificultăți serioase de calcul dacă n este un număr mare.

Câte numere prime există? Euclid a demonstrat că mulțimea numerelor prime este infinită.

Cum putem găsi toate numerele prime mai mici decât un număr dat?

Metoda prezentată mai jos prin care putem găsi numerele prime mai mici decât un număr dat poartă numele de Ciurul lui Eratostene și este cunoscută încă din antichitate.

Să presupunem că vrem să aflăm toate numerele prime până la un număr natural oarecare n. Pentru aceasta vom scrie șirul numerelor naturale de la 1 la n și vom elimina din el toate numerele care nu sunt prime; mai întâi numărul 1, după aceea, pentru fiecare număr natural a>1, toate numerele mai mari decât a și care se divid la a. Observăm ușor că pe această cale toate numerele compuse sunt eliminate, rămânând numai numerele prime.

Astfel, din șirul am eliminat numărul 1, după aceea numerele mai mari decât 2 și care se divid la 2, apoi numerele mai mari decât 3 și care se divid la 3. Numerele care se divid la 4 au fost deja excluse ca numere mai mari decât 2 și care se divid la 2. Continuăm procedeul și vom elimina numerele mai mari decât 5 și care se divid la 5, etc.. Putem să nu eliminăm nici un număr Într-adevăr, dacă a este un număr compus și , atunci, conform teoremei: orice număr natural are cel puțin un divizor prim, numărul a are un divizor prim , prin urmare și numărul a este eliminat ca număr mai mare decât p și care se divide la p.

De exemplu dacă vrem să obținem toate numerele prime , eliminăm din șirul 1,2,3,…,100 numărul 1, apoi numerele și care se divid la 2, în continuare numerele care se divid la 3, după aceea numerele care se divid la 5 și, în sfârșit numerele care se divid la 7. Toate numerele care au rămas în șirul nostru vor fi prime, obținând șirul numerelor 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

În 1909 au fost editate tabelele cu numere prime , în care se dau cei mai mici divizori primi pentru fiecare număr natural care nu se divid la 2,3,5 sau 7, iar în 1951 au fost publicate tabele de numere prime până la 11.000.000, Jacob Philipp Kulik a întocmit tabele de numere prime până la 100.000.000 (manuscrisul se păstrează la Academia Austriacă de Științe din Viena).

În ultimele două decenii însă specialiștii s-au întrecut în a găsi numere prime cu valori din ce în ce mai mari. În 1996, cel mai mare număr prim cunoscut avea 420.921 cifre. În 1998, noul număr descoperit avea deja 909.526, iar în 2001 un număr nou avea 4.053.946 cifre. Progresul este galopant. La 25 ianuarie 2013, saltul a devenit și mai spectaculos: matematicianul Curtis Cooper, de la Universitatea din Missouri, a identificat cu ajutorul unor softuri speciale un număr prim format din 17.425.170 cifre. Valoarea exactă a acestui număr este: .

3.2 Mica teoremă a lui Fermat

Un rezultat important și foarte folosit în aritmetică este Mica teoremă a lui Fermat. Aceasta poate fi dedusă din Teorema lui Euler (Teorema 2.9), dar în continuare prezentăm alte două variante de demonstrație. Pentru acestea avem întâi următorul corolar (o generalizare a unei situații din capitolul anterior).

Corolar 3.2.1: Dacă este un șir finit de numere naturale al căror produs se divide printrun număr prim p, atunci cel puțin unul din numerele trebuie să se dividă la p.

Teoremă 3.2.2(Mica teoremă a lui Fermat): Dacă p este un număr prim și n un număr natural nenul astfel încât (n,p)=1, atunci avem

(1)

Demonstrația 1. Considerăm primii multiplii ai numărului : . Resturile împărțirii acestora la p sunt respectiv: . Așadar avem relațiile:

(2)

Observăm că pentru orice ; în caz contrar, ar urma că , deci , ceea ce contravine ipotezei (n,p)=1. Mai observăm că resturile sunt diferite între ele; dacă am avea , atunci ar rezulta , unde , din nou în contradicție cu ipoteza.

Aceste afirmații permit să concluzionăm că sunt numerele aranjate într-o anumită ordine.

Înmulțind egalitățile (2), vom obține

sau

, ,

deci

,

adică

, ,

de unde

, q.e.d.

Observație: Relația se mai poate scrie sau

Demonstrația 2. (prin metoda inducției folosind binomul lui Newton)

Fie p un număr prim dat. Teorema este evident adevărată pentru n=1. Să presupunem că ea este adevărată pentru un număr oarecare n. Conform binomului lui Newton, avem

, (3)

unde pentru , avem , și, după cum se știe, numerele sunt întregi. De aici deducem că numărul se divide la p, prin urmare conform Corolarului 3.2.1, cel puțin unul dintre numere trebuie să se dividă la p. Dar, întrucât , nici unul dintre numerele nu se divide la p, deci numărul trebuie să se dividă la p.

Ținând cont de (3), deducem de aici că numărul . Adăugându-i acestui număr care se divide la p (deoarece am presupus teorema adevărată pentru n), constatăm că numărul .

Am demonstrat astfel prin inducție că teorema este adevărată pentru orice număr natural n. Pentru numărul zero ea este evident adevărată.

Dacă n este un număr întreg negativ, atunci pentru p=2 avem și deoarece din două numere întregi consecutive și unul este întotdeauna par, avem întotdeauna . Mai departe, pentru p prim impar, avem și, deci, . Prin urmare, teorema este adevărată și pentru numere întregi negative n.

3.3 Teorema lui Euclid

Acest paragraf este dedicat teoremei lui Euclid relative la infinitatea numerelor prime.

Lema 3.3.1: Orice număr natural, mai mare decât 1, are un divizor prim.

Demonstrație: Folosim metoda reducerii la absurd, presupunem că există un număr n>1 care nu are divizori primi. Notăm cu mulțimea acestor numere, cum este nevidă și este bine ordonată, există un cel mai mic element în S. Fie acesta , este atunci un număr compus, , cu . Pentru a nu contrazice alegerea lui , adică are un divizor prim care va fi divizor și pentru , ceea ce contrazice faptul că .

Teorema 3.3.3(Euclid): Mulțimea numerelor naturale prime este infinită.

Pentru această teoremă, oferim mai jos mai multe demonstrații:

Demonstratia 1(Euclid): Presupunem, prin absurd, că există doar n numere prime p1, p2, ….,pn. Numărul N = p1p2…pn + 1 este mai mare decât 1, deci are un divizor prim. Cum fiecare , acesta va fi prim, adică N = pk pentru un k ∈ {1,….,n}, ceea ce este absurd.

Demonstrația 2: Fie Pn = n! + 1, pentru ≥ 1. Din Lema 3.3.1, pentru fiecare Pn găsim câte un divizor prim pn. Daca un pn ≤ n, atunci pn | n! și cum pn | Pn, rezultă pn = 1, fals. Deci, pn > n, pentru orice n. Am obținut astfel că, pentru orice n ≥ 1, exista pn > n număr prim, ceea ce arată că mulțimea numerelor prime este infinită (Pentru n = 1 găsim p1, apoi alegem n = p1 și obținem un număr prim > p1, etc.)

Demonstrația 3: Dacă , atunci între există cel puțin un număr prim.

Deoarece atunci numărul întreg și are un divizor prim p(conform Lemei 3.3.1), evident , deci . Dar nu putem avea , deoarece p ar fi atunci unul dintre factorii produsului și, prin urmare, p ar fi un divizor al numărului ; întrucât el este și un divizor al lui numărului , rezultă că p ar fi un divizor al diferenței acestor numere, adică ) =1, ceea ce este imposibil. Rezultă că , și deoarece știm că , avem . Așadar, pentru orice număr natural există un număr prim mai mare decât el. De aici rezultă că există o infinitate de numere prime.

Demonstrația 4 (Euler): Presupunem prin absurd că există numai un număr finit de numere prime.

Pentru orice i, , avem seria geometrică infinită .

Dar făcând produsul acestor serii se obține:

,

Ultima egalitate fiind o consecință a Teoremei 2.14. Rezultă că , adică seria armonică este convergentă. S-a obținut o contradicție.

Demonstrație 5(G. Polya): Pentru orice număr natural n se formează numărul lui Fermat .

Numerele lui Fermat sunt numere prime.

Vom demonstra acum afirmația: dacă , atunci și nu au nici un divizor prim în comun. Într-adevăr, dacă presupunem că , are loc identitatea:

== .

În consecință dacă și p| rezultă p|2. Aceasta nu se poate deoarece numerele sunt impare.

Pentru a încheia demonstrația este suficient să observăm că mulțimea numerelor prime conține mulțimea divizorilor primi ai numerelor Fermat și că aceasta este infinită ca o reuniune infinită de mulțimi (finite) disjuncte.

Demonstrație 6(Marcel Țena): Presupunem prin absurd că mulțimea numerelor prime este finită; fie acestea . Pentru orice , , considerăm mulțimile

Conform Teoremei 2.14, are loc incluziunea de mulțimi , deoarece orice număr întreg este un produs de numere prime și elementele lui An nu depășesc p1np2n…pkn . Trecând la cardinalele celor două mulțimi se obține egalitatea : 2n ≤ (n+1)k. Rezultă că Trecând la limita n → ∞ , se obține o contradicție.

3.4 Teorema lui Cebâșev și inegalitățile lui Cebâșev

Teorema lui Cebâșev este un alt rezultat fundamental din aritmetică, legat de numere prime. Demonstrarea acesteia este laborioasă, se parcurg mai multe leme intermediare până la rezultatul final (vezi lucrarea Bușneag,D., Chirteș,F., Piciu, D.[5]). Nu prezentăm aici decât lema finală din care se deduce teorema, dar și câteva consecințe interesante ale acesteia. De asemenea sunt prezentate o serie de inegalități cu privire la funcția ce numără numerele prime mai mici decât un număr dat (real).

Lema 3.4.1: Dacă , atunci între și se află cel puțin două numere prime distincte.

Teorema 3.4.2 (Cebâșev): Dacă , atunci între și avem cel puțin un număr prim.

Demonstratie:

Pentru și teorema este adevărată in mod evident deoarece între 4 și 6 se află 5 iar între 5 și 8 se află 7.

Pentru , conform Lemei 3.4.1 între n și 2n se află cel puțin două numere prime distincte și cu . Dacă cel mai mare dintre acestea este , celălalt trebuie să fie căci este par și compus pentru . Deci . Dacă , cum , din deduce că și astfel Teorema lui Cebîșev este complet demonstrată.

Corolar 3.4.3: Dacă , atunci între n și 2n se află cel puțin un număr prim.

Demonstrație: Dacă n ≥ 4 totul rezultă din teorema lui Cebîșev. Dacă între 2 și 4 se află 3 iar dacă atunci între 3 și 6 se află 5. Astfel corolarul este demonstrat pentru orice .

Printre funcțiile aritmetice importante se numără și funcția definită după cum urmează:

: ℕ*→ℂ , (n) = |{ x ∈ ℕ* | 1 ≤ x ≤ n, x număr prim }|.

Astfel, π(1)=0, π(2)=1, π(3)=π(4)=2, π(5)=π(6)=3, π(100)=25, π(1000)=168, etc.

În anul 1958, D. H. Lehmer a calculat π(108) și π(109) arătând că π(108)=5761455 și π(109)=50847534.

Evident, π(pn)=n pentru orice n≥1, unde pn este al n-lea număr prim.

Nu s-a găsit o formulă generală de calcul al acestei funcții, dar în continuare prezentăm, fără demonstrație, câteva aspecte legate de aceasta, printre care așa zisele inegalități ale lui Cebâșev (pentru mai multe detalii vezi lucrarea [ ]).

Propoziția 3.4.4: Pentru orice număr natural n> 1, avem inegalitatea:

Propoziția 3.4.5: Dacă n> 1, π(n)< 4 ∙.

Din aceste două propoziții deducem:

Propoziția 3.4.6: Pentru orice număr natural n> 1, avem dubla inegalitate

π(n)< 4 ∙.

Observații:

1. Dacă trecem la logaritmi naturali, Propozitia 3.4.6 devine 0,92π(n) < 1,11∙ astfel ca variația funcției π(n) este redată cu o exactitate mai mare de funcția (factorii numerici 0,92 și 1,11 diferă puțin de 1).

2. Cebîșev a demonstrat de asemenea că dacă raportul π(n) : tinde (pentru n→∞) la o limită l, atunci l = 1. Faptul că limita raportului π(n) : exista pentru n→∞ (și este egală cu 1) a fost demonstrată pentru prima data de J. Hadamard, la aproximativ 50 de ani de la lucrările remarcabile ale lui P. L. Cebîșev.

Deci, obținem că π(n)≈ pentru n> 1.

Teorema 3.4.7: (Cebâșev) Pentru x∈ℝ, x≥ 2 avem dubla inegalitate:

Observație: Daca pentru două funcții reale f și g scriem f ~g dacă = 1, atunci menționăm următoarele rezultate:

1. π(x) ~ . Cunoscut și sub numele de Teorema elementului prim sau Legea de repartițiea numerelor prime, acest rezultat a fost intuit de Legendre și Gauss în secolul al XVIII-lea și deminstrat în 1896, independent de J. Hadamard și G. J. de la Vallée-Poussin cu metode specific analizei complexe.

2. La 15 ani Gauss a conjecturat că π(x) ~Li(x) = dt.

Deoarece dt = − + dt și 0 <dt = dt + dt< + < + , deduce că 0 << + , de unde acum se deduce ușor că ~Li(x).

J. Rosser și L. Schoenfeld demonstrează inegalitățile:

(RS)

Inegalitatea din stânga având loc pentru , iar cea din dreapta pentru .

G. Mincu și L. Panaitopol demonstrază inegaliatea:

(MP)

pentru orice și .

C. Karanikolov demonstrează inegalitatea:

< (K)

pentru orice și .

L. Panaitopol stabilește o inegalitate mai tare de același tip și anume <(P)

pentru a>1 și x>.

Teorema 3.4.8: Dacă și , atunci.

Demonstrație:

Se arată mai întâi că pentru și are loc inegalitatea:

. (1)

Diferența dintre membrul stâng și cel drept este :

.

Folosind inegalitățile (RS) și (1), se poate scrie:

>>.

Teorema 3.4.9: Dacă și > sunt astfel încât raportul depășește un anumit prag, atunci:<<,inegalitatea din stânga având loc pentru iar cea din dreapta pentru .

Demonstrație: Se arată ca pentru orice există inegalitatea:

(2) iar pentru există inegalitatea: .(3)

Inegalitatea (2) este echivalentă cu cu presupunerea iar inegalitatea (3) este echivalentă cu cu presupunerea .

Pentru și folosind inegalitățile (RS) și (2), avem:

>>.

De asemenea pentru și folosind inegalitățile (RS) și (3), avem:

>>.

Corolar 3.4.10 : Pentru , există inegalitatea:

>.

Demonstrație: Demonstrația se face prin inducție matematică după n, iar pentru n=2 obținem relația din Teorema 3.4.8.

Corolar 3.4.11 : Pentru există inegalitatea:>.

Demonstrație: Se aplică Corolarul 3.4.10 în care .

Corolar 3.4.12 : Pentru există inegalitatea:.

Demonstrație: În Corolarul 3.4.11 inlocuim pe a cu și vom obține , de unde .

Corolar 3.4.12 : Dacă și , există inegalitatea:.

Demonstrație : Din Teorema 3.4.9 rezultă , care prin împărțire cu devine .

Observație : În ipoteza restrictivă și Teorema 3.4.8 este o consecința a

Teoremei 3.4.9. Întrucât , și folosind inegalitatea din stânga Teoremei 3.4.9, putem

scrie>.

3.5 Teorema lui Dirichlet

Teorema lui Dirichlet (prezentată fără demonstrație) ne conduce la o serie de mulțimi particulare de numere prime, care sunt la rândul lor infinite. Prezentăm câteva dintre acestea.

Teorema 3.5.1: Dacă , iar , atunci mulțimea conține o infinitate de numere prime.

Demonstrația completă a acestei teoreme poate fi găsită în lucrarea Popovici, C.P [21], mai jos vom prezenta câteva cazuri particulare ale acesteia.

Cazuri particulare ale teoremei lui Drichlet

Propoziția 3.5.2: Există o infinitate de numere prime de forma cu .

Demonstrație: Să presupunem prin reducere la absurd că mulțimea conține numai un număr finit de numere prime, fie acestea și să considerăm numărul . Numărul trebuie să aibă un factor prim de forma (căci dacă toți factorii primi ai lui ar fi de forma atunci și ar trebui să fie de forma . Deci ar trebui ca să dividă pe, ceea ce este absurd), de unde concluzia din enunț.

Propoziția 3.5.3: Există o infinitate de numere prime de forma cu .

Demonstrație: Să presupunem prin absurd că există doar un număr finit de numere prime de forma și anume și să considerăm numărul .

Cum un număr prim este de forma sau , deducem că trebuie să conțină un factor prim de forma (în caz contrar ar trebui ca să fie de forma ). Deci ar trebui ca un să dividă pe , ceea ce este absurd, de unde concluzia din enunț.

După cum am văzut, pentru orice număr prim (vezi Capitolul 2). De aici deducem că 2 este rest pătratic modulo pentru de forma , și non-rest pătratic pentru de forma (cu )

Propoziția 3.5.4: Există o infinitate de numere prime de forma .

Demonstrație: Fie; atunci numărul are cel puțin un divizor prim impar care nu e de forma (căci este de forma iar dacă toți divizorii primi impari ai lui ar fi de forma, atunci ar trebui să fie de fie de aceeași formă). Atunci de unde deducem că

Dar deci adică trebuie să fie de forma . Cum este de forma , rămâne doar prim trebuie să fie .

Cum deducem că Am probat deci că orice există un prim de forma .

Să presupunem acum că avem un număr finit de numere prime de forma și anume .

Considerăm numărul , conform celor de mai sus există un număr prim de forma (adică un ), astfel încât ceea ce este absurd.

Propoziția 3.5.5: Există o infinitate de numere prime de forma .

Demonstrație: Fie și (unde este al n-lea număr prim).

Cum este impar, va fi de forma iar va fi de forma . Dacă orice divizor prim al lui este de forma , iar însuși este de această formă –absurd!

Deci are cel puțin un divizor prim impar ce nu este de forma sau

Cum deducem că și deci

Dar .

Dacă , atunci absurd, de unde concluzia că este de forma Însă din deducem că , și astfel avem o infinitate de numere prime de forma .

Propoziția 3.5.6: Există o infinitate de numere prime de forma cu.

Demonstrație: Fie natural și . Cum este impar, este de forma

Dacă toți divizorii naturali ai lui ar fi de forma , atunci ar fi de aceeași formă ceea ce este imposibil.

Atunci ar trebui să aibă un divizor prim de forma sau .

Dacă atunci din deci și astfel și cum ,contradicție!

Deci este de forma și astfel din și deducem că de unde rezultă imediatcă avem o infinitate de numere prime de forma .

Corolar 3.5.7: Există o infinitate de numere prime de forma , cu.

Demonstrație: Fie , , iar . Cum și este impar, atunci , cum nu este de forma , va avea cel puțin un divizor prim ce este de forma . Evident .

Cum , adică . Atunci și

Avem că poate să fie de forma sau

Dacă atunci și cum deducem că , contradicție!

Cum am văzut că nu poate fi de forma deducem că trebuie să fie de forma . De aici corolarul rezultă imediat.

3.6 Aplicații

1 Să se demonstreze că:

a. Oricare două numere naturale consecutive sunt prime între ele.

b. Oricare două numere impare consecutive sunt prime între ele.

Soluție:

Fie n și n+1 două numere consecutive și d a.î. și => => și sunt numere consecutive prime între ele.

Fie și două numere impare consective și d a.î. și => => => , dar și sunt numere impare => => și sunt numere impare consecutive prime între ele.

2 Arătați că numerele și , unde sunt prime între ele.

Soluție:

Fie d divizor comun și , înmulțim prima relație cu 2 => și a doua relație cu => scădem relațiile =>

=> d|1 => numerele și sunt prime între ele, q.e.d

3. Aflați numerele naturale pentru care , și sunt simultan numere prime.

Soluție:

Dacă n=2=> numerele , și adică 2, 8 și 10 nu sunt simultan numere prime.

Dacă n=3 => numerele , și adică 3,13 și 15 nu sunt simultan numere prime.

Dacă n=5 => numerele , și adică 5, 29 și 31 sunt simultan numere prime.

Dacă n=7 => numerele , și adică 7, 53 și 55 nu sunt simultan numere prime.

Pentru toate celelalte valori ale lui , , n poate fi prim dacă ultima cifră este 1,3,7 sau 9 => . Dacă nu poate fi număr prim. Dacă nu poate fi număr prim => este soluție unică.

4. Determinați toate tripletele de numere prime care verifică relația: .

(etapa județeană, Botoșani, 1999)

Soluție:

Cel mai mic număr prim este 2.

Dacă , mulțimea numerelor prime mai mici sau egale cu 11.

Dacă

Dacă

Alegem și verificăm pentru toate valorile:

Dacă => .

Dacă => , nu este număr prim.

Dacă => , este număr prim => avem tripletul .

Dacă => , nu este număr prim.

Dacă => , este număr prim => avem tripletul .

Dacă => , este număr prim => avem tripletul soluție.

Dacă => , cum numerele și sunt numere pare, atunci este număr par, poate fi prim doar dacă . Dacă => , nu este număr prim.

Dacă => , cum numerele și sunt numere pare, atunci este număr par, poate fi prim doar dacă . Dacă =>, nu este număr prim.

5. Demonstrați că oricare ar fi , numerele: nu pot fi în același timp numere prime.

(etapa județeană, Botoșani, 1998)

Soluție: Analizăm cazurile:

Dacă , atunci nu este număr prim.

Dacă , atunci => nu este număr prim.

Dacă , atunci =>

nu este număr prim.

Conform cazurilor analizate mai sus rezultă că numerele nu pot fi simultan numere prime, q.e.d.

6. Determinați numerele prime care verifică relația.

Soluție: Numerele a, b, c nu pot fi toate impare deoarece membrul stâng al egalității ar fi un număr impar, ce nu poate fi egal cu 6622. Deci putem avea un singur număr par sau toate pare. Dacă toate trei ar fi pare am avea care nu verifică. Deci un singur număr este par. Cum . Obținem .Cun și trebuie ca b să fie multiplu de 17. Dar b este număr prim, de unde b=17 Înlocuind obținem c=19.

7. Determinați numerele prime p și q știind că există astfel încât

.

Soluție: Din , deci q este un număr prim impar.

Astfel că x, y sunt simultan pare sau impare, ceea ce face ca p să fie număr par, adică . Ecuația nu are decât soluția , astfel că .

8. Să se determine cifrele știind că împărțind la se obține câtul și restul , unde este număr prim.

Soluție:Din teorema împărțirii cu rest se obține și din ipoteză . Dacă atunci ceea ce conduce la cu soluțiile și , respectiv dar în acest caz nu avem soluții. Dacă atunci ceea ce conduce la respectiv și nu există soluții. Prin urmare soluția problemei:

9. Determinați toate numerele naturale care au proprietatea că și sunt simultan numere prime.

(etapa județeană, Brașov 1996)

Soluție:

Dacă este număr par și este număr prim => sau este număr impar.

Dacă => m=1 și n=0 sau m=0 și n=1.

Dacă m=1 și n=0 => m+n=1, nu e număr prim.

Dacă m=0 și n=1 => m+n=1, nu e număr prim.

Dacă este număr impar => n este număr impar (1).

Dacă este număr par și este număr prim => sau este număr impar.

Dacă => m=1 și n=0 sau m=0 și n=1.

Dacă m=1 și n=0 => m+n=1, nu e număr prim.

Dacă m=0 și n=1 => m+n=1, nu e număr prim.

Dacă este număr impar => m este număr impar (2).

Din și => număr par=> , unde => sau sau .

Dacă => , , => și sunt simultan numere prime => , soluție.

Dacă => , , => și sunt simultan numere prime => , nu este o soluție.

Dacă => , , => și sunt simultan numere prime => , nu este o soluție.

10. Pentru orice număr întreg , , există n numere naturale consecutive, nici unul dintre ele nefiind o putere a unui număr prim.

Soluție:

Soluția 1: Fie , vom arăta că satisfac condiția. Presupunem prin absurd că există un număr astfel încât . Deoarece avem , deci . Prin urmare . Din => , deci . Deoarece avem și , deci => , contradicție => q.e.d

Soluția 2: Fie numere prime. Sistemul de congruențe:

are o soluție naturală , conform teoremei chinezești a resturilor. Atunci au fiecare cel puțin doi divizori primi distincți. Din această soluție se observă că se poate obține o infinitate de asemenea șiruri de numere consecutive.

11. Nu există nici un număr natural astfel încât: .

Soluție: Presupunem prin absurd că există , astfel încât . Fie cel mai mic divizor prim al lui . Conform teoremei lui Fermat, , deoarece este impar, deci este impar. Fie ordinal lui , și este cel mai mic întreg pozitiv cu această proprietate. Atunci și . Deoarece a fost ales ca cel mai mic divizor prim al lui și sau . Cazul contrazice și cazul implică , ceea ce contrazice alegerea lui .

12. Dacă , atunci (unde este al k-lea număr prim).

Soluție: Facem inducție dupa . Pentru avem . Dacă , conform Corolarului 3.4.3 există cel puțin un număr prim astfel încât și astfel corolarul este demonstrat.

13. Dacă , atunci în descompunerea lui în factori primi găsim cel puțin un număr prim cu exponentul egal cu 1.

Soluție: Pentru și afirmația este adevărată.

Fie acum . Dacă n este par, , atunci și conform Corolarului

3.4.3 între și găsim cel puțin un număr prim p astfel încât .

Vrem să demonstrăm că p apare cu exponentul 1 în descompunerea în factori primi a lui n!. Într-adevăr, următorul număr din n! ce ar fi multiplu de p este 2p însă din .

Dacă n este impar, și din nou conform Corolarului 3.4.3 între și găsim cel puțin un număr prim . Deci avem și și din nou ajungem la concluzia că apare în descompunerea lui cu exponentul 1.

Observație. De aice se deduce imediat:

Dacă , atunci nu poate fi puterea unui număr natural cu exponentul mai mare decât.

14. Pentru orice , avem inegalitatea .

Soluție: Pentru avem și atunci conform Lemei 3.4.1 între și există cel puțin două numere prime distincte. Cum cele mai mici dintre aceste numere vor fi și avem .

15. Pentru orice avem .

Soluție: Pentru se verifică imediat prin calcul, iar pentru totul rezultă din problema precedentă.

16. Dacă , atunci .

Soluție: Dacă , atunci și cum , cu necesitate și deci .

Fie p cel mai mare număr prim . Atunci . Conform Corolarului 3.4.3, între și găsim cel puțin un număr prim , iar dacă am avea , atunci , în contradicție cu alegerea lui . Deci .

Cum , atunci și din nou conform Corolarului 3.4.3, între și există un număr prim. Cum , ținând cont de felul în care l-am ales pe deduce că . De asemenea, deoarece , avem .

Deducem de aici ca printre termenii sumei există numai unul al cărui numitor să fie divizibil prin . Punând pe sub formă de fracție (cu numitorul ) se observă că printre termenii ce dau număratorul lui există unul ce nu se divide prin . Atunci, dacă scriem (cu ), și , de unde concluzia că .

17. Să se demonstreze că pentru un număr natural n≥ 2, < dacă și numai dacă n este prim.

Soluție: Dacă n este prim, atunci π(n) = π(n − 1) + 1, deci:

− = ∙ (1 −).

Cum π(k) <k pentru k≥ 1 deducem imediat că >.

Presupunem acum că >. Dacă n nu este prim, atunci el este compus și

π(n) = π(n − 1) astfel că am obține că <, absurd!

Dacă p este un număr prim, r∈ℕ* a.î. pr|, atunci pr≤2n și

Soluție: Din pr|, deducem că exponentul lui p în descompunerea lui în factori primi (care este ) verifică inegalitatea α ≥r. Dacă am avea pr >2n, pentru k ≥r am avea =0 și atunci . Cum pentru orice x∈ℝ avem 1 ar trebui să avem α ≤r-1 ceea ce contrazice faptul că α ≥ r. Deci pr ≤2n . Ținând cont și de lucrul acesta, pentru a demonstra partea a doua, ținem cont de faptul că în descompunerea în factori primi a lui nu pot să apară decât numere prime q≤2n, de unde deducem că .

Dacă n∈ℕ, n≥14, atunci π(n) ≤.

Soluție: Pentru n=14 avem π(14)=6=.Pentru , în șirul 1, 2, …,n numerele 4, 6, …, (în număr de ) sunt compuse. Pe de altă parte, pentru n≥15, șirul 1, 2, …,n conține și numerele impare compuse 1, 9 și 15, de unde deducem că π(n) ≤ (căci ).

Numerele prime de forma 2m + 1 ( cu m ≥ 1 ) au exponentul o putere a lui 2 (este

valabilă și reciproca).

Soluție: Se demonstrează prin reducere la absurd:

Presupunem că exponentul ar avea divizor impar i și este de forma m = i, k . Deoarece 2m + 1 = (2k)i+ 1 = ( 2k + 1) (1 – 2k + (2k)2 – … – (2k)i-2 + (2k)i-1 ) , obținem că

2m + 1 este compus, ceea ce contrazice ipoteza!

Observație. Numerele de forma n = + 1,n poartă numele de numere Fermat.

Povestea numerelor Fermat a izvorât din povestea numerelor prime, Fermat având falsa impresie că întreaga clasă este formată din astfel de numere. Euler a arătat că, începând cu cel de-al șaselea număr din această clasă, se pot realiza descompuneri, astfel 𝓕5 = + 1 = 4294967297 este un număr compus, numărul 641 divizându-l, descompunerea acestuia fiind de forma 𝓕5 = + 1 =228(54+24) – (527 )4 = 228641-(6404 – 1) = 228641-(640-1)(640 + 1)(6402 +1) = 641 6700417.Nu se știe încă dacă există o infinitate de numere prime Fermat. Până în prezent nu au fost puse în evidență decât primele cinci numere prime care coincid cu primii cinci termeni ai șirului Fermat: 𝓕0 = 3 ; 𝓕1 = 5 ; 𝓕2 = 17; 𝓕3 =257; 𝓕4 = 65537.

Problema existenței numerelor prime Fermat a devenit o problemă de interes major atunci când Gauss a stabilit că orice poligon regulat poate fi construit cu rigla și compasul dacă și numai dacă numărul laturilor, n, verifică relația de forma = 2k p1p2…pr unde k, r , iar p1p2…pr sunt numere prime de tip Fermat, de aici și interesul pentru stabilirea acestora. Teorema prin care este stabilit dacă un număr Fermat este prim sau compus a fost formulată în 1891 de către Lucas și constituie fundamentul testului Pepin.

4. Numere pseudoprime

4.1 Noțiuni introductive

Mai jos vor fi prezentate noțiuni introductive legate de numerele pseudoprime, o parte din leme și teoreme sunt prezentate fără demonstrație, cei interesați le pot găsi demonstrate integral în lucrarea Rahman Mizanur M [22].

Conform Micii Teoreme a lui Fermat, dacă este prim, atunci pentru orice număr natural

Se crede că acum aproximativ 25 de secole matematicienii chinezi au descoperit această teoremă în cazul și au afirmat că dacă un număr întreg satisface congruența , atunci este număr prim. Recent, Mann-Keung Siu, un matematician chinez, profund interesat în istoria chinezească a matematicii, crede că există un mit creat, el consideră că este imposibil pentru chinezii matematicieni să fi formulat această afirmație din moment ce ei nu au formulat niciodată conceptul de numere prime.

Un exemplu care contrazice afirmația (dacă n satisface congruența , atunci este prim) a fost descoperit in , când Sarrus a arătat ca , dar este un număr compus. Nu este greu de realizat pe ce se bazează congruența de mai sus. Din Mica Teoremă a lui Fermat vedem că și prin urmare . De asemenea . Așadar . Așadar rezultă că , și multiplicând ambele părți ale acestei congruențe cu 2, obținem . De fapt este cel mai mic număr natural compus care satisface relația .

Definiție 4.1.1: Un număr natural n se numește pseudoprim dacă n este compus și .

Dacă n este un număr natural compus atunci n este pseudoprim dacă și numai dacă . Numerele pseudoprime sunt uneori numite „numere aproape prime” sau „numere Poulet”. P. Poulet [20], a determinat toate numerele pseudoprime mai mici decât .

Lema 4.1.2: Dacă și sunt numere naturale astfel încât , atunci pentru orice număr întreg , se verifică relația .

Exemplu: este număr pseudoprim

Pentru a arăta că este pseudoprim, avem ,

Din si , din lema anterioară avem.

Din , concluzionăm este divizibil cu 73 si 1103. Așadar numărul se divide la 73 și 1103, este un număr par, deci . Astfel , deci n este pseudoprim.

Lema 4.1.3: Dacă n este un pseudoprim, atunci este de asemenea un pseudoprim care este mai mare decât n.

Teorema 4.1.4: Fie n un număr întreg pozitiv compus:

este pseudoprim în bază , unde dacă și numai dacă (unde este puterea lui modulo )

Dacă este pseudoprim în bazele și , unde atunci este pseudoprim in baza

Dacă este pseudoprim în baza , atunci este pseudoprim în baza , unde este un număr întreg, invesul numarului ().

Dacă este un pseudoprim impar în baza , unde , atunci este pseudoprim în baza .

Câte numere pseudoprime sunt?

Există un număr infinit de pseudoprime. Demonstrația a fost bazată pe descoperirea uni șir infinit de numere impare pseudoprime. Prima demostrație a existenței unui număr infinit de pseudoprime a fost realizată în 1903 de Malo [15].

Teoremă 4.1.5: Există un număr infinit de numere pseudoprime.

Demonstrație: Această teoremă derivă imediat din Lema 4.1.3. Dacă n este un număr pseudoprim impar, atunci este de asemenea un număr pseudoprim impar mai mare decât n. În plus, odată ce există cel puțin un număr pseudoprim impar, e.g. , putem construi un număr infinit de numere pseudoprime impare luând și pentru .În mod clar aceste numere impare întregi sunt toate diferite și … . Astfel demonstrația este completă.

O altă demonstrație a acestei teoreme, bazată pe numerele Fermat, a fost dată de Cipolla [7] în 1904.

Numere pseudoprime și testul de primalitate.

O preocupare foarte importantă în teoria numerelor este de a stabili dacă un anumit număr întreg n pozitiv este număr prim sau compus. Cele mai multe dintre testele eficiente de testare a primalității cunoscute sunt bazate pe Mica Teoremă a lui Fermat, care prevede dacă p este un număr prim, atunci pentru orice număr întreg pozitiv, astfel încât , se aplică relația de congruență .

Astfel, dacă pentru un anumit număr întreg pozitiv , există cu și astfel încât , atunci n este compus .

De exemplu, din moment ce , n=91 e un număr compus. Pe de altă parte rezultă astfel că inversa Micii Teoreme a lui Fermat eșuează în a oferi un test de primalitate.

În ciuda faptului că inversa Micii Teoreme a lui Fermat nu oferă un test de primalitate, “majoritatea covârșitoare” de numere întregi pozitive poate fi demonstrată că e compusă datorită faptului că eșuează în a demonstra Teorema lui Fermat pentru un întreg .

Teorema 4.1.6: Fie număr întreg impar compus. Dacă pentru o bază relativ primă față de n, , atunci pentru cel puțin jumătate din posibilele baze b, unde .

Demonstrație: Fie mulțimea tuturor bazelor posibile pentru care n este un pseudoprim, unde , și are loc relația de congruență bin-1 . Fie b o bază fixă pentru care nu e pseudoprim. Dacă era pseudoprim în oricare dintre bazele , atunci conform Teoremei 4.1.4, ar fi un pseudoprim pentru baza ceea ce nu este adevărat (deja am presupus ca n nu e pseudoprim în baza b). Astfel, pentru s reziduri distincte {, , … , } numărul întreg eșuează să satisfacă relația de congruență

De aici rezultă că sunt cel puțin atâtea baze pentru care n eșuează să fie pseudoprim câte îndeplinesc relația de congruență . Asta completează demonstrația.

Să presupunem că vrem să știm dacă un număr întreg impar e prim. Am putea alege orice număr a care îndeplinește condiția . Folosind algoritmul lui Euclid, . Dacă știm că este compus și de fapt am găsit un factor netrivial .

Dacă , atunci testăm dacă . Dacă , atunci știm că n este compus. Pe de altă parte, dacă , atunci avem dovada unei posibilități ca n să fie prim. Alegem apoi alt a și repetăm procesul. Dacă pentru acest nou a obținem rezultă că n este compus și ne oprim. Astfel, raportându-ne la teorema anterioară, cu excepția cazului în care n satisface relația de congruență pentru toate bazele pozitive a cu cmmdc , avem cel puțin o sansă de 50% ca n să eșueze să satisfacă condiția pentru oricare a.

Presupunem că încercăm ka posibilități și găsim că pentru toate bazele k. În fiecare încercare, probabilitatea ca n să fie un compus întreg în ciuda faptului că a îndeplinit condiția pentru k este aproximativ cel mult , cu excepția cazului în care se întâmplă sa fie pseudoprim pentru toate bazele , cu . Mai sus am presupus că încercările cu baze diferite sunt mutual independente una față de cealaltă. Astfel, dacă k este un număr mare putem fi siguri că n este prim (în afara cazului când n este pseudoprim pentru toate bazele).

Fie n un număr întreg compus. Folosind acest test al primalității, dacă alegem 100 numere întregi diferite la întâmplare cuprinse între 1 și n și le testăm pentru fiecare dintre aceste 100 baze, probabilitatea ca n să treacă toate testele este mai mică de , un număr extrem de mic. Testul de primalitate nu demonstrează într-un mod absolut că un număr întreg n, care trece toate cele 100 de teste, este prim, dar prezice acest lucru cu o probabilitate covârșitoare și greu de ignorat.

Această metodă de a testa dacă un număr întreg pozitiv este prim este un exemplu de metodă “probabilistică”. Diferă de o metodă deterministă prin faptul ca astfel de metode arată că un număr întreg n este compus sau stabilește, cu o certitudine de 100%, că un număr este prim. Metoda probabilistică dezvoltată anterior nu funcționează pentru un număr întreg compus n cu relația de congruență valabilă pentru toate bazele , cu . Acum, întrebarea este dacă se poate întâmpla și pentru un număr întreg compus , pentru orice număr întreg , cu ? Din păcate, răspunsul este da, aceste numere există și sunt numite numere prime absolute sau numere Carmichael.

Exemplu: . Pentru a determina dacă n este compus sau prim, alegem orice bază . Din moment ce , aplicând Mica Teoremă a lui Fermat observăm că . În acest moment, nu știm dacă n este număr prim sau compus. Acum încercăm cu o altă baza ; din nou, din moment ce , aplicăm Mica Teoremă a lui Fermat și observăm că deci, 341 este un număr compus.

Am văzut diferite exemple unde un număr întreg n este pseudoprim în diferite baze. De exemplu, este pseudoprim in bazele 2, 5 și 7. O întrebare bună pe care cineva ar putea să o pună ar putea fi: având un număr întreg pozitiv , câte baze există astfel încât numărul să fie pesudoprim în baza ? Răspunsul la această întrebare a fost dat de Monier în 1980 [17].

Lema 4.1.7: Pentru ecuațiile de mai jos:

… (1)

…(2)

unde p este număr prim și k număr întreg pozitiv, numărul de soluții este egal.

Teorema 4.1.8: Dacă n este un număr compus, atunci numărul bazelor cu , pentru care este un pseudoprim în baza a, este dat de:

Demonstrație:

Numărul acestor baze a este numărul soluțiilor ecuației

(1)

Fie factorul prim al lui n.

Pentru fiecare considerăm ecuațiile

… (2)

și (3)

apoi, prin Teorema 2.16, ecuația (3) are soluții distincte . Din Lema 4.1.7., ecuația (2) are soluții distincte .

Din Teorema Chinezească a resturilor, ecuația (1) are soluții distincte ( incluzând 2 soluții triviale și . Astfel numărul soluțiilor ale ecuației (1), unde este .

Așadar Asfel demonstrația este completă.

4.2. Pseudoprime absolute/Numere Carmichael

Definiție 4.2.1: Un număr întreg n care satisface relația pentru toate numere naturale cu cmmdc (a, n) = 1 se numește pseudoprim absolut sau număr Carmichael.

Exemplu: Numărul n=561 este număr Carmichael: să alegem un număr întreg b astfel încât atunci Astfel, conform Micii Teoreme a lui Fermat avem , și . Prin urmare , și . Prin urmare, , pentru toate numerele b cu (561 este cel mai mic număr Carmichael).

Teorema 4.2.2: Fie n un număr întreg impar compus. Dacă n este divizibil cu un pătrat perfect mai mare decât 1, atunci n nu este un număr Carmichael.

Demonstrație: Să presupunem că . Fie g un generator modulo a.î g este un număr întreg al cărui ordin () este Considerăm produsul tuturor celorlalte numere prime p care divid n. Din Teorema Chinezească a Resturilor, există un întreg b care satisface relațiile: și . Apoi b ca generator a lui g este un generator modulo . Numărul întreg b satisface și relația , deoarece nu este divizibil cu p sau cu orice număr prim care divide . Am susținut că n nu este pseudoprim în baza b. Acest lucru este ușor de văzut deoarece dacă și , automat . Dar în acest caz deoarece este de ordinul modulo . Cu toate acestea, , deoarece. Acest lucru înseamnă că nu este divizibil cu . Această contradicție demonstrează că există o bază pentru care nu reușește să fie o pseudoprim în baza 2.

Teoremă 4.2.3: Dacă unde sunt numere prime distincte care satisfac relația pentru toate valorile atunci număr Carmichael.

Demonstrație: Fie b un număr întreg pozitiv cu . pentru orice , și din Mica Teoremă a lui Fermat pentru toate valorile . Deoarece , atunci pentru fiecare există numere întregi cu . Prin urmare, pentru fiecare j, știm că . Prin urmare din Teorema de 2.8, vedem că concluzionăm că n este un număr Carmichael. Astfel demonstrația este completă.

Definiție 4.2.4: Un exponent universal a unui întreg pozitiv este un întreg pozitiv , astfel încât pentru toți întregii relativ primi cu .

Cel mai puțin exponent universal a unui întreg pozitiv n se numește exponentul minim universal de n, și se notează .

Teorema 4.2.5 : Fie n un număr întreg pozitiv descompus în puteri de numere prime . Atunci , exponentul minimal universal al lui , este dat de . Mai mult, există un număr întreg astfel încât , este cea mai mare putere a unui număr întreg de modul .(Demonstrația completă a acestei teoreme se regăsește în lucrarea Mizanur Rahman, M [16 ])

Teoremă 4.2.6: Dacă este un număr Carmichael, atunci , unde sunt numere prime distincte care satisfac relația pentru .

Demonstrație: Dacă n este număr Carmichael atunci pentru toate numerele întregi cu . Din Teorema 4.2.5 spune că există un număr întreg cu ordin unde este un exponent universal minim și . Teorema 2.10 spune că , n trebuie să fie impar pentru că dacă este par atunci n-1 ar fi impar. Dar este par (contrazicând faptul că . Acum trebuie să arătăm că n trebuie să fie produs de numere distinct prime. Presupune că are un factor prim cu , atunci , asta implică ceea ce este imposibil deoarece . Prin urmare, trebuie să fie produs de numere prime impare distinct . Demonstrația este completă, și concluzionăm .

Teoremă 4.2.7: Un număr Carmichael trebuie să aibă cel puțin trei factori primi impari diferiți.

Demonstrație: Fie un număr Carmicheal, nu poate avea doar un factor prim, deoarece este compus și este produsul a cel puțin două numere prime distincte. Deci presupunem că , unde și sunt numere prime impare cu . Apoi , ceea ce arată că . Prin urmare, prin Teorema 4.2.5, nu poate fi un număr Carmichael dacă are doar doi factori primi. Astfel demonstrația este completă.

Observație. Există multe întrebări fără răspuns cu privire la numerele de Carmichael. De exemplu, nu se știe dacă există o infinitate de numere Carmichael.

4.3 Pseudoprime Euler

Conform criteriului lui Euler, dacă este un număr impar prim și este un număr întreg nedivizibil cu , atunci , unde este simbolul lui Legendre(vezi Capitolul 2).

Deci, dacă vrem să verificăm dacă numărul întreg pozitiv n este prim, putem să luam un număr întreg cu și să determinăm dacă , unde simbolul de pe partea dreaptă a congruenței este simbolul lui Jacobi(vezi Capitolul 2). Dacă congruența nu este adevărată, atunci este compus.

Exemplu. Fie și . Calculăm . Cum , utilizând teorema 2.12, vedem că , la fel, .

Astfel se demonstrază că nu este un număr prim.

Prin urmare, putem defini un tip de pseudoprim pe baza criteriului lui Euler.

Definiție 4.3.1: Un număr natural impar n care satisface relația unde b este un număr întreg pozitiv se numește pseudoprim Euler în baza b.

Exemplu: și , calculăm . Întrucât , vedem că , prin urmare . Deoarece este compus, este pseudoprim Euler în baza 2.

Teoremă 4.3.2: Dacă n este pseudoprim Euler în baza b, atunci n este un pseudoprim în această bază.

Demonstrație: Dacă este pseudoprim Euler în baza , atunci așadar prin ridcarea la putere a ambelor părți ale relației avem: . Din , vedem că , asta înseamnă că este pseudoprim în baza . Astfel demonstrația este completă.

Nu orice număr pseudoprim este pseudoprim Euler în baza 2. De exemplu, nu este pseudoprim Euler în baza 2, așa cum am arătat, dar este pseudoprim în această bază.

O întrebare firească este: Poate un număr compus să fie pseudoprim Euler pentru fiecare bază cu , unde ? În 1976 Lehmer [13] a arătat că răspunsul la această întrebare este negativ.

Teoremă 4.3.3: Nici un număr întreg impar compus nu este pseudoprim Euler pentru pentru fiecare bază relativ primă la .

Demonstrație: Presupunem contrariul, fie un număr impar compus, pseudoprim Euler pentru orice bază , unde și . Din Teorema 4.3.1, este număr Carmichael. Teorema 4.2.6 ne spune că orice număr Carmichael este un produs de cel puțin trei numere prime distincte. Prin urmare putem scrie: , unde , de asemenea pentru fiecare avem valabile relațiile . În particular, dacă pentru orice rădăcină primitivă a tuturor numerelor atunci astfel , acum numerele prime pot fi împărțite în două tipuri:

Valorile p pentru care , sau

Valorile p pentru care .

Astfel avem dacă p este de tipul (1) și dacă p este de tipul (2). Alegem a să fie pătratic nerest pentru și rezidu pentru toate celelelate valori . Presupunem că există un număr prim de tip (1) cesta fiind , deoarece N este pseudoprim Euler în baza a, atunci . Această contradicție ne arată că toate valorile lui p trebuie să fie de tip (2), de aceea trebuie să avem . Dar, n este pseudoprim Euler, ceea ce implică , înseamnă că , această contradicție completează demonstrația.

Teoremă 4.3.4: Există un număr infinit de numere pseudoprime Euler în baza b, care sunt produs de k factori primi distincți.

Monier a arătat în [19] că pentru un n număr întreg impar compus numărul de baze , unde și , pentru care n este pseudoprim Euler este dat de formula:

, unde

unde în formula , reprezintă exponentul lui p în factorizarea primă a lui n și este exponentul lui 2 în factorizarea primă a lui .

Exemplu: Să aplicăm formula de mai sus pentru a afla numărul de baze pentru care n = 2407 = 29 83 este un pseudoprim Euler. Vom calcula :

Calculăm

Prin urmare , astfel . Deci este pseudoprim Euler numai în baza .

4.4. Pseudoprime Fermat

Conform Micii Teoreme a lui Fermat, dacă este număr prim și , atunci . Această teoremă oferă un „test” de primalitate care de cele mai multe ori este corect: fiind dat un număr întreg impar p suficient de mare, alegem un număr a care satisface relația și calculăm . Dacă , atunci p este cu siguranță compus, dacă , atunci p este probabil prim.

Definiția 4.4.1: Un număr întreg impar compus , pentru care se numește pseudoprim în baza a (și îl notăm psp(a)).

Definiția 4.4.2: Un număr întreg impar compus se numește pseudoprim Fermat în baza , dacă și

Mica Teoremă a lui Fermat ne spune că orice număr prim care nu se divide cu a trece testul și este număr pseudoprim Fermat, reciproca nefiind adevărată. Există numere pseudoprime Fermat care nu sunt prime( astfel de numere sunt se numesc numere Carmichael)

Exemplu:

Numărul este un număr pseudoprim Fermat în baza , , observăm că putem scrie conform Micii Teoreme a lui Fermat , apoi calculăm , prin urmare din și Teorema Chinezească a Resturilor avem și , deci 91 este pseudoprim în baza . Pe de altă parte folosind în mod repetat rădăcina pătrată vom găsi că , asta înseamnă că 91 nu este pseudoprim în baza 2, prin urmare nu este nici număr prim.

Numărul este cel mai mic număr pseudoprim Fermat în baza . Putem scrie , din Mica Teoremă a lui Fermat avem , prin urmare , observăm că prin urmare . Teorema Chinezească a Resturilor implică , rezultă că este pseudoprim Fermat în baza 2.

Teoremă 4.4.3: Dacă n este un pseudoprim Fermat impar în baza 2 care nu este prim, atunci nici nu este număr prim.

Demonstrație: Deoarece n nu este număr prim îl putem scrie , știm că , înmulțim cu 2 și obținem , astfel aven și putem scrie , deci

deci nu este număr prim.

Teoremă 4.4.4: Dacă numărul nu este pseudoprim Fermat, atunci testul de număr pseudoprim Fermat de baza eșuează pentru cel puțin jumătate din elementele

Demonstrație: Presupunem că nu este pseudoprim Fermat și avem:

Apoi este subgrup al lui , altfel Deoarece nu este pseudoprim Fermat există elemente dar , astfel Rezultă că , în cele din urmă ori de câte ori și , atunci a nu trece testul, există cel puțin astfel de elemente, q.e.d.

4.5 Pseudoprime Catalan

Originile numerelor Catalan au fost dezvăluite pentru prima dată într-o scrisoare a lui Euler pentru Goldbach în 1751 când numără triunghiurile unui poligon convex (pentru detalii vedeți [3]). Astăzi în mod general ele se definesc prin formula și pot fi caracterizate recursiv de formula sau cu , numerele Catalan apar într-o uimitoare varietate de setări combixnatoriale unde sunt folosite pentru a enumera tot felul de obiecte geometrice si algebrice.

Teorema 4.5.1 (Wilson): Un număr natural este prim dacă și numai dacă .(Demonstrația completă a teoremei se găsește în Bușneag, D., Chirteș, F., Piciu, D. [5])

Teorema 4.5.2: Dacă este numar prim, atunci .

Demonstrație: Dacă x=2 este evident iar dacă totul rezultă din Mica teoremă a lui Fermat.

Cu toate că Teorema 4.5.2 este un prim test de bază util, inversa acesteia este falsă; de exemplu: , dar 341 nu este prim; astfel de numere sunt numite numere pseudoprime

Teorema 4.5.3: Dacă este un număr prim impar atunci

Demonstrație: Presupunem că este un număr prim impar. Modulul lui x, are , oricare ar fi i. De aici și astfel:

Lema 4.5.4: Dacă este numar prim și , atunci avem:

(a),

(b)

(c), unde inversul multiplicat al lui i modulo p.

Demonstrație: (a) este o relație cunoscută.

(b) Teorema binomului ne ofera , rezultă că:

, folosind (a).

Partea (c) rezulta din (b) cand .

La fel ca Teorema 4.5.2 și Teorema 4.5.3 oferă o condiție necesară, aceea ca p să fie număr prim, iar inversa ei este de asemenea falsă; de exemplu (mod 5907), dar 5907 nu este număr prim (fiind egal cu 3), numim aceste numere, numere pseudoprime Catalan.

Comparând Teorema 4.5.2 si 4.5.3, observăm că în ciuda faptului că acest calcul al numerelor Catalan este destul de complicat (vezi lucrarea [9]), este considerabil mai mic decât . Mai mult decât atât, pseudoprimele Catalan par să fie mai puțin comune decât pseudoprimele standard. O abordare mai teoretică constă în încercarea de a identifica pseudoprimele Catalan într-o formă dată, cea mai simplă dintre toate fiind unde este număr prim. În acest caz, apare o întrebare naturală și anume dacă acestea nu ar putea să fie și pseudoprime standard.

Propoziția 4.5.5: Dacă p este număr prim impar, atunci următoarele numere sunt egale modulo :

,

,

,

,

, unde determină inversul lui i modulo p.

Demonstrație: Dacă și i nu este multiplu de p, atunci i are invers modulo , și . Astfel:

Deci (a)=(b). Afirmația (b)=(e) poate fi dedusă direct din lucrarea [11], Teorema 133 sau avem:

Deci, desfăcând în puteri ale lui p, .

Modulo p, fiecare invers egalează un număr unic j cu , astfel Cauchy [8, capitolul III] a observat: (mod p), de aici astfel (b)=(e).

Ecuația (e)=(c) a fost demonstrată aparent de către Sylvester [18, capitolul 8A]; aceasta rezultă din [11, Teorema 132], sau folosind Lema 4.5.4 (c) si (1), avem modulo ,

(mod ), de aici avem (e)=(c).

În final, cu Teorema 4.5.2, ( mod p), așa că modulo , avem , pentru . Astfel (mod ), de aici obținem (c)=(d).

Reconsiderând dacă p este număr prim și modulo , atunci p este un număr prim Wieferich; 1093 și 3511 sunt singurele numere prime Wieferich știute; nu mai există alte numere prime Wieferich mai mici decât [14], dar în prezent nu se știe dacă există un număr finit de numere prime Wieferich. Wieferich a arătat în 1909 că dacă ecuația lui Fermat are o soluție pentru un număr impar p fără să dividă , iar apoi cel mai mic p este obligatoriu un număr prim Wieferich [23]. Propoziția de mai sus are următorul corolar:

Corolar 4.5.6: Dacă este număr prim, atunci următoarele sunt echivalente:

este un număr prim Wieferich,

este un pseudoprim,

este un pseudoprim Catalan.

(Demonstrația completă se găsește în Aebi., C. [1])

Deci 1194649= și 12327121= sunt exemple de pseudoprime Catalan. Mult mai rare decât pseudoprimele standard, 5907, și sunt singurele pseudoprime Catalan pe care le cunoaștem momentan.

Observația 1: Conform Teoremei 4.5.2 și 4.5.3, când p este număr prim: (mod p). Propoziția 4.5.5 ne oferă o versiune mai puternică a acesteia. Într-adevăr, din Propoziția 4.5.5 obținem:

(mod ).

Observația 2: Cum am vazut mai sus, Teorema 4.5.3 este o consecință banală a Lemei 4.5.4. Chiar dacă inversa Teoremei 4.5.3 este falsă, inversa Lemei 4.5.4 este adevărată, după cum a fost observat de către Leibniz [8, p. 91]: un număr natural p este prim dacă și numai dacă este divizibil cu p pentru orice . Într-adevăr, dacă n este număr compus, iar p este un divizor prim al acestuia, atunci nu este divizibil cu n, iar asta putem vedea scriind .

În cele ce urmează pentru ușurința înțelegerii vom introduce următoarea notație:

pentru n număr impar.

Folosind notația anterioară putem rescrie Teorema 4.5.3 astfel:

Dacă p este număr impar prim, atunci și definim lema de mai jos:

Lema 4.5.7:

Dacă p este număr prim impar atunci pentru toate numerele

impare m, unde ;

Dacă p, q sunt numere impare prime distincte, atunci:

;

c. Dacă p este număr impar prim, atunci pentru toate numerele impare și

(Demonstrația completă se găsește în Aebi., C. [1])

Propoziția 4.5.8: Dacă p și q sunt două numere prime impare distincte atunci produsul este pseudoprim Catalan dacă și numai dacă , .

Demonstrație: Dacă este pseudoprim Catalan atunci . În particular, . Din Lema 4.5.7 (a), , dar p este număr prim, . Prin urmare , la fel și . Invers, dacă și , p și q sunt numere prime distincte, .

Analog și conform lemei 4.5.7 (b) avem .

Considerațiile de mai sus ne permit să afirmăm că dacă p și q sunt numere prime, unde și fie p sau q-p destul de mici, atunci pq nu este pseudoprim Catalan. Pentru a da un banal exemplu în acest sens demonstrăm:

Corolar 4.5.9: Nu există numere pseudoprime Catalan de forma , în cazul în care și sunt numere prime gemene.

Demonstrație: Dacă p și p+2 sunt prime, din Lema 4.7.2 (c) avem . Întrucât și din Mica Teorema a lui Fermat avem . Deci p + 2). Dacă p(p+2) este pseudoprim Catalan, atunci conform Propoziției 4.7.3 ar trebui să avem și astfel p + 2), adică p+2=9, contrazice ipoteza că p+2 este număr prim.

Bibliografie

[1] Aebi, C., Cairns, G., Catalan numbers, primes and twin primes, College Calvin, Geneva, Switzerland, La Trobe University, Melbourne, Australia

[2] Bălăucă, A., 111 de probleme semnificative, olimpiade, concursuri și centre de excelență, clasa a VI-a, editura Taida, 2011

[3] Bezhanishvili, G., Leung,H., Lodder, J., Pengelley, D., and Ranjan, D., Counting triangulations of a polygon, Teaching Discrete Mathematics via Primary Historical Sources Website, http://www.math.nmsu.edu/hist projects/, New Mexico State University, downloaded 12.12.2007.

[4] Burton, D.M., Elementary Number Theory. 2nd ed. Dubuque: Wm. C. Brown publishers, 1989.

[5] Bușneag, D., Chirteș, F., Piciu, D., Complemente de aritmetică și teoria elemenetară a numerelor, editura Gil, Zalău, 2007

[6] Calafeteanu, G., Ermil, B., Lugoj, T., Lupu, A., Megan, J., Moclea, A., Pupăză, E., Stretcu, D., Probleme de matematică, clasa a VI-a, semestrul I, editura Valeriu, Craiova, 2012

[7] Cipolla, M., Sui Numeri composti P, che verificano la congruenza di Fermat (mod P), Ann.Mat. Pura Appl. 9 (1904) 139-160.

[8] Dickson, L. E., History of the theory of numbers. Vol. I: Divisibility and primality., Chelsea Publishing Co., New York, 1966.

[9] Douglas M. C., The computation of Catalan numbers, Math. Mag. 57 (1984), no. 4, 195-208.

[10] Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, and Desh Ranjan, Counting triangulations of a polygon, Teaching Discrete Mathematics via Primary Historical Sources

[11] Hardy, G. H. and Wright E. M., An introduction to the theory of numbers, The Clarendon Press Oxford University Press, New York, 1979.

[12] Iaglom, A.M., Iaglom, I.M., Probleme neelementare tratate elementar, Ed. Tehnică, 1983

[13] Lehmer, D.H., Strong Carmichael numbers, J. Austral. Math. Soc., A, 21 (1976) 508-510.

[14 ] Knauer, J., and Richstein, J., The continuing search for Wieferich primes, Math. Comp. 74 (2005), no. 251, 1559/1563 (electronic).

[15]Malo, E., Nombre qui, sans etre premieres, verifient exceptionnellement une congruence de Fermat, Intermediare des Math. 10 (1903) p.86.

[16] Mizanur Rahman, M., Teză, Numere pseudoprime, July 1992

[17] Monier, L., Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci.,12, (1980) 1003-1026. http://www.math.nmsu.edu/hist projects/, New Mexico State University, downloaded 12.12.2007.

[18]_______, My numbers, my friends, Springer-Verlag, New York, 2000.

[19] Monier, L., Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci.,12, (1980) 1003-1026.

[20] Poulet, P., Table de nombres composes verifieny le theoreme de Fermat pour le module 2 jusgu'a 100000000, Sphinx 8, (1938) 42-52.

[21] Popovici, C.P., Teoria numerelor, Editura Didactică și Pedagogică, București, 1973.

[22] Rahman Mizanur M., Pseudoprime Numbers, July 1992, Emporia State University

[23] Ribenboim, P., 13 lectures on Fermat's last theorem, Springer-Verlag, New York, 1979.

[24] Rosen, K.H., Elementary Number Theory. 2nd ed. Reading: Addison -Wesley, 1988.

[25] Sierpinski, W. ,Ce știm știm și ce nu știm despre numerele prime, Editura Științifică, București, 1966