Numere Prime Speciale

Informatica

Numere Prime Speciale

Byadmin ianuarie 1, 2024

Cuprins

INTRODUCERE

CAPITOLUL I: Numere prime

Numere naturale prime

Numere întregi prime

Metode de factorizare

Considerații privind distribuția numerelor prime in N

Criterii pentru numere prime

Cateva ipoteze asupra numerelor prime

CAPITOLUL II: Numere prime speciale și congruențe algebrice

Noțiuni introductive

Numere prime și progresii aritmetice

Noțiuni introductive pentru congruențe algebrice

Congruențe de gradul întâi

Sisteme de congruențe de gradul întâi

Congruențe față de un modul prim

Rădăcini primitive modulo m

Indici modulo m

Congruențe binome

CAPITOLUL III: Numerele prime ale lui Mersenne

Numere perfecte

Numerele prime ale lui Mersenne

Un criteriu pentru numerele prime ale lui Mersenne

CAPITOLUL IV:Numerele prime ale lui Fermat

Șirul lui Fermat

Numerele prime ale lui Fermat

CAPITOLUL V: Numerele lui Fibonacci

Șirul numerelor lui Fibonacci

Șiruri recurente liniar

Proprietați de divizibilitate. Numerele prime din șirul lui Fibonacci.

Introducere

In teoria numerelor, un rol fundamental îl are clasa numerelor prime, adică a numerelor naturale care nu pot fi puse sub forma unui produs de numere mai mici ca ele. Acest rol este pus în evident de așa teorema fundamental a aritmeticii care afirmă că orice număr natural, mai mare ca 1 , se reprezintă ca un produs de numere prime.

Această lucrare intitulată “Numere prime speciale” este structurată pe cinci capitole: Capitolul I “Numere prime”, Capitolul II “Numere prime speciale și congruențe algebrice”, Capitolul III “Numerele prime ale lui Mersenne”, Capitolul IV “Numerele prime ale lui Fermat”, Capitolul V “Numerele lui Fibonacci”.

Primul capitol “ Numere prime” cuprinde conceptele de număr ireductibil, număr prim, numere întregi prime apoi teorema lui Euclid și teorema lui Euler. In acest capitol sunt prezentate și metodele de factorizare cu exemplu lui Fermat, considerații privind distribuția numerelor prime în N, criterii pentru numere prime iar în finalul acestui capitol prezintă câteva ipoteze asupra numerelor prime.

Al doile capitol “Numere prime speciale și congruențe algebrice” prezintă mai întâi câteva noțiuni introductive despre numerele prime speciale și numere prime din progresii aritmetice. Apoi prezintă noțiuni algebrice despre congruențe algebrice, congruențe algebrice de grad I, sisteme de congruențe pentru gradul I, congruențe fața de un modul prim, rădăcini primitive modulo m, indici modulo m și congruențe binome.

Al treile capitol “Numerele prime ale lui Mersenne” cuprinde la început subcapitolul intitulat numere prime unde sunt prezentate conceptele de număr perfect, numere prietene sau amiabile, numere saturate și câteva teoreme demonstrate. Tot acest capitol cuprinde și numere prime ale lui Mersenne și un criteriu pentru numerele prime ale lui Mersenne.

Al patrulea capitol “Numere prime ale lui Fermat” prezintă șirul lui Fermat împreuna cu proprietațile numerelor lui Fermat și apoi sunt prezentate numerele prime ale lui Fermat.

Ultimul capitol intitulat “Numerele lui Fibonacci” cuprinde șirul numerelor lui Fibonacci ce cuprinde câteva propoziții demonstrate.Tot acest capitol prezinta șiruri recurente liniar, aplicații ale formulei lui Binet și proprietați de divizibilitate.

CAPITOLUL I: Numere prime

Numere naturale prime

In mulțimea numerelor naturale, 0 are ca divizor orice număr natural, iar 1 divide orice număr natural. Singurul divizor al lui 1 este 1. Orice număr natural b, mai mare ca 1, are ca divizori pe 1 si b, iar 1 și b se numesc divizori improprii ai lui b. Dacă b are si alți divizori, aceștia se vor numi divizori proprii ai lui b.

Definiția 1. Numărul ireductibil este un număr natural j, j≠1, care are numai divizori improprii. Daca numărul natural n are divizori proprii , n se numește număr compus.

Pentru termenul ireductibil se folosește și termenul nedecompozabil (indecompozabil).

Definiția 2.Un număr natural r, r≠o, r≠1, se numește număr prim dacă oricare p, s N, r/p·s implica r/p sau r/s.

Teorema 1. Fie r N, r>1. Următoarele două afirmații sunt echivalente:

r este prim;

r este ireductibil.

Demonstrație.

Fie r un număr prim . Vom arăta că prin reducere la absurd r este un număr ireductibil. Fie

r= p·s, 1<p<r, 1<s<r, r/r r/p·s și conform definiției 2 → r/p sau r/s. Dacă r/p rezultă rp si contrazicem pr, iar dacă r/s, rp și contrazicem pr.

Fie r un număr ireductibil si p, s două numere naturale arbitrare astfel încăt r/p·s. Notăm (r, p)= d. Cum d/r rezultă d= 1 sau d= r. Dacă d=r, din d/p rezultă r/p . Dacă d=1, din r/p·s și (p,m)= 1, rezultă r/s.

Deci, in N noțiunea de număr prim si număr ireductibil coincide.

Teorema 2. Orice număr natural mai mare ca 1 este prim sau este un produs de numere prime.

Orice număr natural diferit de 0 este un produs de numere prime.

Demonstrația 1. (reducere la absurd) Presupunem ca M={n N / n>1, n nu este produs de numere prime}≠ 0 . Fie a primul element din M. a nu poate fi prim, deci a= k·l, 1<k< a, 1<l<a. l si k fiind mai mici ca a se reprezintă ca produse de numere prime deci a=k·l se reprezintă ca un produs de numere prime. Contrazicem ipoteza. Deci M= Ø și teorema este demonstrată.

Demonstrație 2.(inducție) Pentru n=2, proprietatea din enunțul teoremei este adevarată. Presupunem că proprietatea este adevarată pentru toate numerele naturale a, 2a<n. Dacă n este număr prim proprietatea este adevărată. Dacă n nu este prim, n=k·l, l<kl<n, proprietatea fiind adevărată pentru k si l, este adevărată si pentru n=k·l.

Vom nota cu Ƥ mulțimea numerelor naturale prime. Fie pƤ si nN*. Mulțimea

M={sN /ps/n }. M≠Ø deoarece 0 M. Șirul p0,p1,p2,…….,ps,….. este strict crescator și deci exista un ß N astfel încât pß>n.

Avem s<ß, xM. In M există un ultim element α și este cea mai mare putere a lui p care divide n, se noteaza pα‖n și α se numește ordinul lui p relative la n. Se mai folosește notația: α=ordp(n).

Teorema3. Orice număr natural diferit de zero se reprezintă în mod unic, pană la ordinea factorilor, ca un produs de numere prime.

Teorema3’. Pentru orice număr natural n, n ≠0, există un singur șir de numere naturale α(p), pƤ, dintre care cel mult un număr finit diferit de zero astfel încât:

n=

Consecinta. Orice număr natural n>1 se scrie în mod unic sub forma

n= p1α1p2α2……..pkαk, (1)

unde p1, p2, ……..,pk sunt numere prime, p1< p2 <……< pk, αi N*, i= . Expresia din membru doi al egalitații (1) se numește descompunerea canonica a lui n in factori primi.

Teorema4. ( Teorema lui Euclid) In șirul numerelor naturale exista o infinitate de numere prime.

Prima demonstrație. (cartea IX din “Elemente” de Euclid). Folosim metoda reducerii la absurd. Presupunem că există un număr finit de numere prime Ƥ= {p1, p2,……,pk}. Fie numărul M= p1p2……pk+1. Cum M> 1, există un număr prim p, p/M. Orice număr prim este din Ƥ deci există i{1, 2,…….., k}, p=pi. Din p/M si p/ p1p2…….pi….pk rezultă că p divide diferența celor 2 numere adica p/1. Rezulta p=1, ceea ce contrazice definiția numărului prim.

A doua demonstrație. Pentru orice număr natural n exista un număr prim p>n. Intr-adevar , n!+1 are cel puțin un divizor prim p și trebuie să avem p> n (in caz contrar p/1). Rezultă că dupa orice număr prim exista un număr prim mai mare.

A treia demonstrație. Pentru orice număr natural n, n>2, exista cel puțin un număr prim p astfel încât n<p<n!. Intr-adevar, n!-1 are cel puțin un divizor prim p și acesta satisface condiția dată. Luăm un număr natural n>2 și contruim șirul n, n1, n2, …….,nk, nk+1, …. unde n1=n!, nk=nk-1!

Există un șir de numere prime diferite

p 1< p2<……<pk <…….,

unde n< p1< n1, n1< p2< n2, …….< nk-1< pk< nk,….

A patra demonstrație. (Euler). Presupunem că Ƥ este finit Ƥ= {p1, p2, ….pk}. Pentru orice pi Ƥ avem :

1+ + +…….+ +……..= .

Deci = = = (conform teoremei fundamentale a aritmeticii).

Am ajuns la o contradicție: seria armonica este convergentă!

Teorema care urmează ne arată că Ƥ este o submulțime destul de consistentă lui N. Totodată această teoremă are drept consecința imediată teorema lui Euclid.

Teorema5. (Euler). = +∞

Demonstrație. Fie p1, p2,……., pm toate numerele prime, diferite, care nu depășesc un număr natural dat N. Pentru orice număr real r, r> 1, avem:= , i= (2)

Inmulțind membru cu membru egalitațile (2) obținem:

1+ + + ……++ + + ……….= (3)

Unde N1≥ N1+1, N2≥ N1+ 1 s.a.m.d

Seria fiind convergentă pentru orice r> 1, putem alege N asa fel încât

++………<,

Oricare ar fi > 0. Rezultă că

+ +……..<,

pentru N suficient de mare. In (3) trecem la limita pentru N → ∞. Obținem:

= (4)

Această formula a fost stabilită de Euler pentru r real.

Riemann a considerat funcșia (suma seriei ) din membrul al doilea pentru r complex (funcția zeta a lui Riemann) și a observat legătura dintre comportarea acestei funcții și distribuția numerelor prime în șirul natural.

Observăm că formula (3) este adevarată și pentru r=1. In acest caz, cum = +∞, obținem:

= +∞ (5)

Am considerat numerele prime numerotate în ordine crescătoare: p1= 2, p2= 3, p3= 5, p4= 7, …..,pn,……Din (5) rezultă:

-= +∞. (6)

Pentru 0< η ≤ avem:

-ln(1- η)= η+ + +……….< η+ + +…………= < 2η.

Din (6) obținem

2= +∞.

Numere întregi prime

In inelul Z al numerelor întregi 0 se divide prin orice număr intreg. Unitațile din Z, 1 si -1, sunt singurele numere care se divid cu orice număr întreg.

Un număr intreg b, diferit de unitați, are cel puțin patru divizori: unitațile1, -1 și asociații lui b, b si –b. Acești divizori ai lui b se numesc divizori improprii. Daca b are și alți divizori aceștia se numesc divizori proprii ai lui b.

Definiția 3. Un număr întreg j diferit de 0 se numește ireductibil (nedecompozabil) daca nu are divizori proprii. Un număr întreg, diferit de unitați, care are divizori proprii, se numește număr compus.

Definiția 4. Un număr întreg p, diferi de zero și unitați se numește număr prim dacă oricare ar fi întregii a si b astfel că p/a·b, atunci p/a sau p/b.

Observație. Un număr întreg este prim in Z dacă și numai dacă |p| este prim in N. Deci numerele prime din Z sunt numere prime în N si opusele lor.

In mulțimea numerelor întregi noțiunile de număr prim și număr ireductibil coincid.

Fie n un număr întreg oarecare, diferit de zero și unități.

n =sign |n| si, in N, |n| are descompunere în factori unica, până la ordinea factorilor. Putem reformula teorema fundamental a aritmeticii în Z:

Teorema 6. Orice număr întreg diferit de zero și unități se reprezintă ca un produs de numere prime. Această reprezentare este unică, până la ordinea factorilor și factori asociați.

Vom considera că factorii din descompunerea unui număr sunt si factori asociați. Descompunerea canonică a unui număr natural c, diferit de zero și unități este:

c= sign np1α1 p2α2……ptαt αi N*, i= (7) unde p1 <p2 <…….<pt sunt numere prime si αt N*.

Formula(7) este adevarată și pentru c= ±1, cu condiția că un produs de zero factori este egal cu 1. Fiind date numerele întregi nenule a, b, ……., n, considerăm toate numerele prime p1, p2,….ps care divid cel puțin unul dintre numerele a, b, …..,n. Admițând că în descompunerea unui număr factorul pi poate apărea și cu puterea zero, putem considera că descompunerile sunt:

|a| = p2α2………,

|b| = ………,

……………………….. (8)

|n| = ………,

, …… N, i=

Teorema 7. Fie numărul întreZ:

Teorema 6. Orice număr întreg diferit de zero și unități se reprezintă ca un produs de numere prime. Această reprezentare este unică, până la ordinea factorilor și factori asociați.

Vom considera că factorii din descompunerea unui număr sunt si factori asociați. Descompunerea canonică a unui număr natural c, diferit de zero și unități este:

c= sign np1α1 p2α2……ptαt αi N*, i= (7) unde p1 <p2 <…….<pt sunt numere prime si αt N*.

Formula(7) este adevarată și pentru c= ±1, cu condiția că un produs de zero factori este egal cu 1. Fiind date numerele întregi nenule a, b, ……., n, considerăm toate numerele prime p1, p2,….ps care divid cel puțin unul dintre numerele a, b, …..,n. Admițând că în descompunerea unui număr factorul pi poate apărea și cu puterea zero, putem considera că descompunerile sunt:

|a| = p2α2………,

|b| = ………,

……………………….. (8)

|n| = ………,

, …… N, i=

Teorema 7. Fie numărul întreg n cu decompunerea canonica

|n| = …… (9)

Condiția necesară și suficientă ca un număr intreg d sa dividă pe n este că

|d| = ……, 0≤ ßi ≤ αi, i=

Demonstrație. Condiția este necesară dacă: d/n, exista un număr întreg a astfel încât

|n| = ……. |c| → α1≥ ß1, ≥ ß2,…………,αt ≥ pt.

Condiția este suficientă: |n| = …… = …….·……. = |d| |a|

Unde a = ±…….

Consecința. Dacă descompunerile în factori primi ale numerelor întregi a, b, ……, n sunt date prin (8), atunci:

(a, b,……, n) = ,

[a, b,……, n] = .

Definiția 5. Se spune că numerele a, b, ….n sunt prime între ele daca (a, b, …..n)=1. Se mai spune ca a, b, …..n sunt global prime între ele.

Consecința. Numerele a, b,……, n sunt prime între ele dacă și numai dacă nu există nici un număr prim care să divida pe fiecare dintre numerele a, b, ….., n. Se observă că dacă numerele a, b, ….., n sunt prime două cate două ele sunt global prime. Reciproca nu este adevarată.

Metode de factorizare

O metodă simplă care pune în evidență divizorii primi ai unui număr natural dat n, este metoda ciurului lui Eratostene. Metoda aceasta este un algoritm de determinare a tuturor numerelor naturale prime care nu-l depăsesc pe n.

Teorema 8. Dacă numărul natural n este compus, atunci el are un divizor d, 1< d≤

Demonstrație . Fie n= ca, 1< c< n, 1< a< n. Putem presupune că c≤ a. Din 1< ≤ ca= n rezultă că 1< c ≤ .

Consecința. Dacă numărul natural n, n>1, nu are nici un divizor prim p care satisface condiția p ≤ atunci n este un număr prim.

Demonstrație. Procedăm prin reducere la absurd. Fie n un număr natural, n > 1, care nu are nici un divizor prim p, satisfăcând condiția p ≤. Presupunem că n este compus și are divizor prim p, p ≤ si contrazicem ipoteza.

Ciurul lui Eratostene se bazează pe următorul algoritm:

P1 : Scriem numerele 1, 2,….., n.

P2 : Eliminăm 1.

P3 : Găsim cel mai mic număr neeliminat din sir, p.

P4: Dacă p> trecem la P6, in caz contrar trecem la P5.

P5: Eliminăm toti multiplii lui p, cu excepția lui p însuși și trecem la P3.

P6: Stop!

Observăm că după eliminarea lui 1 cel mai mic număr rămas în șir este 2, care este prim și apoi (P5) tăiem din șir toți multiplii lui 2. Cel mai mic termen rămas în șir este 3, și cel mai mic multiplu netăiat al lui 3 este 32. Tăiem toți multiplii lui 3, începând cu 32. Următorul număr prim este 5 și cel mai mic multiplu netăiat al său este 52 s.a.m.d.

Observăm că după parcurgerea de un număr finit de ori a ciclului P3 → P4 → P5→ P3 se ajunge obligatoriu la un p prim, p > (sirul 2 <3 < ……<p este un șir strict crescător).

Algoritmul pentru descompunerea în factori primi a unui număr natural n > 1 are următorii pași:

Determinăm numerele prime care nu depăsesc : p1< p2<………<pk ≤.

Dacă pi ≠n1, i=, numărul n este prim. Stop!

Dacă este cel mai mic dintre p1,……pk care divide n determinăm n1 astfel încât n=ph1n1.

Dacă pi≠ n1 , i=, n1 este prim. Stop!

Dacă ph2 este cel mai mic dintre p1,……..pk, ph2/n1 determinăm n2 astfel încât n1= ph2 n2.

s.a.m.d….Algoritmul se încheie după un număr finit de pași deoarece n> n1> n2……>nk și, în mod obligatoriu, ajungem la un nk număr prim.

Metoda este foarte simplă și sistematică dar are dezavantajul că odata cu creșterea lui n volumul calculelor crește enorm și după un anumit număr se depășește posibilitățile de calcul al unui calculator, oricât de performant ar fi acesta.

Pentru descompunere se folosesc și tabelele de numere prime. Cea mai cuprinzătoare tabelă de numere prime este cea a lui D.H.Lehmer, care ne dă cei mai mici divizori primi ai numerelor naturale pană la 10 000 000.

Un algoritm interesant de factorizare a fost propus de N.A.Draim. Algoritmul constă într-o succesiune de împărțiri successive.

Se alege un șir de împărțitori: i1=3, i2=5,……,in= 2n+1,….. Fie N numărul care trebuie descompus in factori. Considerăm:

N1= N, N1=3q1+r1, M2= N1-2q1 ;

N2= M2 +r1, N2=5q2 + r2, M3= M2-2q2;

N3= M3 + r2, N3= 7q3+r3, M4= M3-2q3;

………………………………….

Nk= Mk+rk-1, Nk=(2k+1)qk+rk, Mk+1 = Mk -2qk;

…………………………………..

Nn= Mn +rn-1, Nn= (2n +1)qn+rn, rn=0, Mn+1= Mn- 2qn.

Deoarece N1 > N2 > N3 >……….dupa un număr finit de pași trebuie să ajungem la un rest egal cu 0. Vom arăta că: Mk= N1- 2(q1 + q2 +………+qk-1). (10)

Pentru k=2 proprietatea este adevărată: M2 = N1 -2q1. Presupunem că (10) este verificată. Vom avea:

Mk-1= Mk – 2qk= N1- 2(q1 + q2 +………+qk).

Arătăm că:

Nk= kN1 – (2k-1) (q1 + q2 +………+qk-1). (11)

Pentru k=2 proprietatea este adevarată: N2= M2 +r1 =N1- 2q1 + r1 =N1- 2q1 +(N1 -3q1) = 2N1 -5q1.

Presupunem că (11) este verificată. Vom avea:

Nk+1 = Mk+1 + rk= N1- 2(q1 + q2 +………+qk) +Nk- (2k+1)qk=(k+1) N1 –(2k +3)( q1 + q2 +………+qk).

Din ultima egalitate a algoritmului rezultă că:

Nn= (2n+1) qn= nN1- (2n+1)( q1 + q2 +………+qn).

Din ultima egalitate si (n, 2n+1) =1 rezultă că 2n+1/N1. Avem :

Mn+1= Mn- 2qk= N1 -2(q1 + q2 +………+qn) (12) si făcând k=n in (11), obținem:

(2n+1)qn= n N1(2n +1) (+ q2 +………+qn-1) ↔ q1 + q2 +………+qn= N1 (13)

Din (12) si (13) rezultă : N=(2n-1)Mn-1.

Teorema 9. Condiția necesară și suficientă a numărului natural impar n să fie prim este că nici unu din numerele w2-n, (w+1)2-n, (w+2)2-n,…….,()2-n (14) , să nu fie pătrat perfect.

Teorema 9’. (A.S.Montfere, 1829) Numărul natural impar n este prim dacă și numai dacă nici unul din numerele n+k2, k=0,1,……, nu este pătrat perfect.

Pentru a găsi o decompunere în factori a numărului natural impar n construim șirul (14). Dacă nici un număr din șir nu este pătrat perfect, n este număr prim. Dacă (w+k)2-n=y2, n= (w+k-y)(z+k+y).

Pentru calculul numerelor din șirul (14) calculăm w, w2-n si apoi (w+1)2-n= w2-n +(2w+1), (w+2)2- n= (w+1)2 –n+ (2w+3), (w+3)2-n= (w+2)2 –n+ (2w+5) ș.a.m.d.

Dacă nu dispunem de o tabelă de pătrate, este util faptul că ultimile două cifre în care se termină un pătrat perfect nu poate fi decât: 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96. Din șirul (14) trebuie verificate pătratele perfecte care au una din terminațiile acestea.

Exemplu (Fermat). Să se descompuna în factori primi numărul 2027651281. Calculăm =45029,….. Deci w=45030.

Avem w2-n= 49619

Verificăm că nu este pătrat perfect

Se arată că 1040400= 10202 =y2

Deci: a=w +11 +y= 45030+11 +1020= 46061

b =w +11- y=45030+ 11-1020= 4402

și 2027651281= 46061· 4402

Considerații privind distribuția numerelor prime in N

Una din problemele centrale ale teoriei numerelor este problema distribuției numerelor prime in șirul numerelor prime. Această problemă este considerată ca fiind una din cele mai dificile și interesante probleme din matematică. Teoremele lui Euclid si Fermat, ne-au arătat că exista o infinitate de numere prime in N și mulțimea numerelor prime este o parte “consistentă” a mulțimii numerelor naturale.

Teorema 10. Oricare ar fi numărul natural n există interval de n numere naturale consecutive care sunt toate numere compuse.

Demonstrație. Se considera un șir (n+1)!+2, (n+1)!+3…….(n+!)! + (n+1). (15)

Numerele și șirul (15) sunt compuse deoarece primul se divide cu 2, al doilea cu 3…..

De la 1 la 100 există 25 de numere prime 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Intre 101-200 există 21 numere prime,

Intre 201-200 există 16 numere prime,

Intre 301- 400 există 16 numere prime,

Intre 401- 500 există 17 numere prme,

Intre 501- 600 există 14 numere prme,

Intre 601- 700 există 16 numere prme,

Intre 701- 800 există 14 numere prme,

Intre 801- 900 există 15 numere prme,

Intre 901- 1000 există 14 numere prme.

Apoi :

Intre 1-1000 există 168 de numere prime,

Intre 1001-2000 există 135 de numere prime,

Intre 2001-3000 există 127 de numere prime,

Intre 3001-4000 există 120 de numere prime,

Intre 4001-5000 există 119 de numere prime,

Intre 5001-6000 există 114 de numere prime,

Intre 6001-7000 există 117 de numere prime,

Intre 7001-8000 există 107 de numere prime,

Intre 8001-9000 există110 de numere prime,

Intre 9001-10000 există 112 de numere prime,

In total între 1 si 10000 există 1229 de numere prime

Gauss a arătat ca cea de-a 26379-a suta de numere naturale consecutive nu conțin nici un număr prim iar cea de a 27050-a suta conține 17 numere prime. Odată cu dezvoltarea tehnicii de calcul au fost găsite numere prime tot mai mari. Cel mai mare număr prim cunoscut in 1994 era 2848433-1.

Considerăm șirul numerelor prime Ƥ scrise in ordine crescătoare: p1=2, p2= 3, p3=5, p4=7….,pn, …….. Ne interesează găsirea unei funcții f(n) a.i. pn ≤ f(n).

Teorema 11. pn≤ . Egalitatea are loc numai pentru n=1

Demonstrație p1= 2= , p2= 3< =4. Presupunem că proprietatea este adevărată pentru p1, p2,…….pn. . Din prima demonstrație a teoremei 4 rezultă că: pn+1 ≤ p1 p2…..pn+1. Deci

Pn+1 ≤ · .

Există și o formulă dată de W.Sierpinki ,însă această formula prezintă mai mult un interes teoretic, fară o însemnare practică, care se bazează pe un număr ß care este definit cu ajutorul șirului numerelor prime Ƥ.

Teorema 12. Pentru orice număr natural, n>5, între n si 2n există cel puțin doua numere prime diferite.

Teorema 13. Pentru orice număr natural n, n>3, intre n si 2n-2 exista cel puțin un număr prim.

Demonstrație. Pentru n=4, între 4 și 6 există un număr prim 5. Pentru n=5, între 5 si 8 există un număr prim 7. Pentru n>5, conform teoremei precedente exista doua numere prime r și s astfel incât n< r< s <2n. Dacă s= 2n-1, cum 2n-2 este compus, rezultă n< r< 2n-2. Daca s< 2n-2 avem n<r <s <2n-2.

Teorema 14. Pentru orice q natural, q>1, avem: pq <2q.

Demonstrație. P2=3< 22. Dacă pq< 2q între 2q si 2q+1 există cel puțin un număr prim p. Cum pq+1 <p si p<2q+1 rezultă că pq+1 < 2q+1.

Teorema 15. Pentru orice q N, avem pq+2 <2pq.

Demonstrație. Pentru q>3, pq>p3 =5. Conform teoremei 12 există doua numere naturale r și s astfel încât pq <r <s <2pq. Cum pq+2 ≤ s, rezultă că pq+2 <2pq.

Criterii pentru numere prime

Prin criteriu pentru numerele prime se înțelege o proprietate care o au numai numerele prime și care poate fi constatată independent de verificarea în prealabil a faptului că numărul este prim. Criteriile se stabilesc prin teoreme care dau o condiție necesară pentru ca un număr să fie prim.

Teorema 16. Numărul natural n este prim dacă și numai dacă : = 2

Demonstrație. Un număr natural n este prim dacă și numai dacă are numai doi divizori: φ(n)= 2. Fie m/n. Dacă n=mq , = q, n-1=mq-1. Vom avea mq-m ≤ n-1< mq, deci q-1 ≤ <q

Adică =q-1, rezultă că – = 1.

Dacă m≠ n, avem n=mq+ s, 0 <s <m. Vom avea:

= q.

Din n-1= mq+s-1 , s-1≥ 0. Rezultă =q, deci = 0. Rezultă că și teorema s-a terminat și a fost demonstrată.

Teorema 17. Pentru ca un număr natural p, p>1 să fie prim este necesar și suficient ca pentru orice număr întreg q, 0 q≤ p-1 sa fie verificată relația q!(p-q-1)! +(-1)q ≡ 0 (mod p) (16). Este suficient să existe un singur q pentru care rel (16)este satisfacută, pentru ca numărul p sa fie prim.

Demonstrație. Condiția este necesară. Daca p este prim avem (p-1)! +1 ≡0 (mod p), iar această relație o putem scrie și sub forma:

(p-q-1)! (p-q)(p-q+1)……(p-1) +1≡ 0(mod p) (17)

Evident (p-q) (p-q-1)…(p-1) ≡(-1)q ·q! (mod p). (18)

Din (17) si (18) obținem:

(p-q-1)!q! (-1)q +1≡ 0(mod p). (19)

Dacă înmulțim ambii membri ai ultimei relații cu (-1)q obținem (16). Aceasta este suficientă. Dacă există un q pentru care avem relația (16), pentru q=0 avem (p-1)! ≡0 (mod p ), iar pentru q>0 din relațiile (18) dar și (19) avem că (p-1)!+1 ≡0 (mod p ) deci p este prim.

Teorema 18. (Leibniz). Numărul intreg p, p>1, este prim dacă și numai dacă :

(p-2)!≡ 1(modp)

Teorema 19. Un număr natural impar p, p≥3, este prim dacă și numai dacă :

(p-3)! ≡.

Demonstratie. Dacă în relația (18) luăm q=2 obținem:

(p-3)! ≡ -1(mod p)

echivalentă cu 2(p-3)! ≡ p-1(mod p).

p-1 este par și putem simplifica cu 2, pentru că (2,p)=1 deci (p-3)! ≡ (mod p).

Câteva ipoteze asupra numerelor prime

Una din cele mai faimoase probleme, înca nerezolvată, din teoria numerelor este asa numita ipoteza a lui Goldbach. Problema a fost pusă pentru prima dată în corespondența dintre Cristian Goldbach și Leonard Euler, la aceea vreme aceștia erau matematicieni la Academia din Sankt-Petersburg. Următoarea propoziție este cunoscută sub denumirea de ipoteza lui Goldbach

Propoziția 1. Orice număr natural par, mai mare ca 2, este suma a doua numere prime

Exemplu: 4= 2+2, 6=3+3.

O altă ipoteză mai tare este:

Propoziția 2. Orice număr natural par, mai mare ca 6, este suma a doua numere prime diferite. Această propoziție a fost verificată de Pipping pentru toate numerele pare până la 100000.

Propoziția 3. Orice număr natural impar, mai mare ca 7, este suma a trei numere prime impare.

Dacă ipoteza lui Goldbach este adevarată, propozitia 3 ar fi ca o teorema. Intr-adevar, dacă 2n+1 >7, 2n+1-3= 2(n-1) >4, deci, conform ipotezei lui Goldbach, 2n+1-3 = p+q, p si q numere impare, deci 2n+1 =3+ p+q.

Teorema 20. Dacă ipoteza lui Goldbach este adevarată, orice număr intreg n impar se poate reprezenta intr-o infinitate de moduri sub forma : n=p+q-r , unde p,q,r sunt numere prime.

Demonstrație Fie n un numar intreg impar.Am putea alege, o infinitate de moduri, un numar prim impar r astfel incat n+r> 4. Conform ipotezei lui Goldbach, exista doua numere prime impare p astfel incât n+r= p+q.

Teorema 21. Orice număr natural mai mare ca 11 este suma a doua numere compuse.

Demonstrație. Daca n este par, n-4 este compus si n= 4+(n-4). Dacă n este impar , n-7 este par ,deci n= 7+(n-7).

G.H.Hardy si J.E.Littlewood au formulat ipoteza ca orice număr natural, destul de mare, este suma unui număr prim si a unui pătrat: n=p+t2, p prim tN. Ipoteza nu a putut fi demonstrată deocamdată.

CAPITOLUL II: Numere prime speciale

Noțiuni introductive

In literatura de specialitate, prin numere prime speciale se ințelege numerele prime ale lui Mersenne și numerele prime ale lui Fermat.

Tot prin numere prime speciale vom înțelege numere prime care satisfac o anumită proprietate P(n) relative la numerele naturale. P(n) determină o submulțime a mulțimii numerele naturale formată din toate numerele naturale și pentru care P(n) este adevarată. Mulțimea respectivă este un șir de numere naturale. Deci, prin numere prime speciale ințelegem numerele prime dintr-un șir de numere naturale.

Teorema 1. Nici un polinom f(x) cu coeficienți întregi, de grad mai mare ca 0, nu poate genera numai numere prime.

Demonstrație Fie f(x) = amxm +am-1xm-1 + ….+a1x+ a0, m1, ai, i=, am . Presupunem că acest polinom genereaza numai numere prime. Fie a , p prim. Pentru orice q avem: f(a + qp) – f(a) = am[(a + qp)m – am] + am-1 [(a + qp)m-1 –am-1 ]+…..+a1(a +qp –a).

Din ultima relație rezultă că p/ f(a +qp) –f(a) și cum p/f (a), rezultă că p/ f(a + qp) și cum f(a +qp) este număr prim, f(a+ pq)= . Deci f2(a+ qp) =f2(a). Prin urmare , ecuația f2(x) –f2(a) are o infinitate de rădicini. Deci polinomul f2(x) –f2(a) este identic nul adică f2(x) este un polinom constant, ceea ce contrazice ipoteza m>0. Se adresează in mod natural întrebarea: fiind dat un polinom cu coeficienți întregi f(x), există o infinitate de numere naturale n astfel încât f(n) este număr prim?

Există astfel de polinoame dacă f(x)= ax+b, (a,b)=1 șirul un =f(n), este o progresie aritmetică care conține o infinitate de termini numere prime.

Dacă f(x) este prim pentru o infinitate de numere naturale n,f trebuie satisfăcute următoarele condiții:

f(x) este ireductibil;

nu există a , a>1 astfel încât a / f(x) pentru orice x . Condiția i) este necesară dar nu este suficientă. Exemplu f(x)= x2 +x +2 este ireductibil, f(o)=2 este prim, dar pentru x>0, f(x)= x( x+1) +2 este număr compus ( multiplu de doi).

V.I.Buniakowski a făcut ipoteza: dacă f(x) este un polinom cu coeficienți întregi, care satisface condițiile i) si ii), există o infinitate de numere naturale n pentru care f(x) este număr prim.

Teorema 2. Există o infinitate de numere prime de forma p= r2+1.

Teorema 3. Există o infinitate de numere prime de forma p=r2 +r +4

Este adevărat că polinoamele f(x) =x2 +1 si g(x) =x2 +x +41 satisfac condițiile i) și ii).

Schinzzel a emis următoarea ipoteză generala:

H: Fie s N*, f1(x), f2(x), …….,fs(x) polinoame cu coeficienți întregi ireductibile, având coeficientul termenului rang cel mai mare pozitiv și satisfacând condiția.

S: nu există nici un număr natural mai mare ca 1 care să divida produsul f1(x), f2(x)….,fs(x) pentru orice x întreg . atunci există o infinitate de numere naturale n pentru care fiecare din numerele f1(x), f2(x),…..fs(x0 este prim.

Teorema 4. Dacă ipoteza lui Schinzel este adevarată, atunci pentru orice număr natural par 2k există o infinitate de perechi de numere naturale prime (p, q), q= p+ 2k. în particular, există o infinitate de perechi de numere prime gemene.

Demonstrație. Luăm s=2, f1(x) =x, f2(x) = x+2k. Vom avea f1(1)f2(1) = 1+2k, f1(-1)f2(-1)= =1-2k și dacă d/f1(1)f2(1), d/ f1(-1)f2(-1) atunci d/2 și cum 1+2k este impar, d=1. Conform ipotezei lui Schinzel există o infinitate de numere naturale n astfel încât n și n+2k sunt prime. Pentru k=1, există o infinitate de numere prime gemene.

Teorema 5. Fie c1,c2…..cm cifre în baza 10, cm . Există o infinitate de numere prime care, scrise in baza 10, se termină cu cifrele c1, c2,…..,cm scrise în ordinea dată.

Demonstrație Dacă d= avem (a, 10m) =1.

In progresie aritmetică un= n 10m +a există o infinitate de numere prime și fiecare dintre aceste numere prime se termină cu c1c2…..cm.

Sierpinski a demonstrat un rezultat mai puternic:

Teorema 6. Fie a1, a2, …..am; d1, d2,………, dn două șiruri finite de cifre din baza 10, a1 dn {1, 3, 7, 9}. Este o infinitate de numere prime care, scrise in baza 10, încep cu grupul de cifre a1, a2……., am și se termină cu grupul de cifre b1, b2,……,bn.

Numere prime din progresii aritmetice

Teorema 7. Există o infinitate de numere prime de forma p=4k -1, k.

Demonstrație Procedăm prin reducere la absurd. Presupunem că exista doar un număr finit de numere prime de forma p= 4k- 1 și acestea sunt p1, p2,……,pn. Considerăm numărul ajutor N= 4p1p2……pn-1. Deoarece N>1, există numere prime p care divid N. Orice număr prim impar p este de forma p= 4k+1 sau p= 4k-1. Daca toți divizorii primi ai lui N ar fi de forma N(4/N-1 si 4/N+1 4/2, contradicție! ). Deci există un număr prim p, p/N și p de forma p=4k+1. Prin urmare, pp1, p2,…..pn}. Rezultă că p/ 4p1p2……pm și cum p/N ar rezulta p/1 ceea ce contrazice definiția numărului prim

Teorema 8. Oricare ar fi numărul natural n, n, există o infinitate de numere prime p de forma p= nk-1.

Demonstrație. Pentru n= 1, {nk -1 }= N{-1} și afirmația teoremei este adevarată (teorema lui Euclid). Pentru n=2 teorema este adevarată (există o infinitate de numere prime impare).

Lema.Oricare ar fi numărul natural n, n>1, numărul (n!)2 +1 are divizori primi și acesti divizori sunt de forma p= 4k+1.

Demonstrație. Pentru n>1, numărul (n!)2+1 este impar și mai mare ca 1. Există p prim, p, p/(n!)2 +1. p este de forma p=4k +1 sau p =4k +3. Arătam, prin reducere la absurd, ca p este de prima formă. Dacă p =4k+3, din p/(n!)2 +1 rezultă p/ (n!)2(2k+1)+1, adică p/(n!)p-1 +1 și deci p/(n!)p+n!. prin inducție dupa m se arată că dacă p este prim, oricare ar fi numărul natural m, p/mp-m (mica teorema a lui Fermat). Deci p/(n!)p +n! si p/(n!)p- n!. Rezultă că p/2n! deci pn și p/n!. Rezultă că p/1 și contrazicem definiția numărului prim.

Teorema 9. Există o infinitate de numere prime de forma p=4k+1

Demonstrație. Presupunem că există doar un număr finit de numere prime de forma 4k+1: p1= 5< p2 <……<ps. Considerăm numărul N=[ (p1,p2……,ps)!]2 +1. Conform lemei precedente, N are un divizor prim p de forma p= 4k+1 . cum p {p1, p2,……, ps} rezultă că p/1 și contrazicem definiția numărului prim.

Congruențe algebrice- noțiuni algebrice

Fie f[x] un polinom cu coeficienți întregi f(x)= an xn +an-1xn-1 +…..+a1x +a0. (1)

Definiție Polinomul (1) are gradul n modulo m dacă an≡ 0(mod m) (2). Vom considera congruențe de forma f(x) ≡ 0(mod m).

Definiție Vom spune că numărul întreg x0 verifică congruența (2) dacă funcția polinomială

f :Z→Z primește în x= x0 o valoare care este un număr întreg divizibil prin m f(x0) ≡ 0(mod m ).

Teorema 1. Dacă un număr întreg x0 verifică congruența (2), atunci orice număr din aceeași clasă modulo m verifică (2).

Demonstrație. Fie x1 , arbitrar , x1 ≡x0 (mod m0. Rezultă că (mod m) k{0, 1,…..,n} și apoi: ak , k {0, 1, ….,n]. sumând membru cu membru ultimele congruențe, obținem: f(x1) ≡f(xo) (mod m) și cum f(x0) ≡0 (mod m), rezultă: f(x1) ≡ 0(mod m).

Definiție Se numește soluție a congruenței (2) o clasă de resturi modulo m formată din numere care verifică congruența (2).

Teorema 2. Dacă un număr întreg x0 este reprezentantul unei soluții a congruenței f(x) (mod m) atunci x-x0 divide modulo m pe f(x) și reciproc, dacă x-x0 divide modulo m pe f(x), clasa lui xo este o soluție a congruenței.

Demonstrație Din f(x) =(x-x0) g(x) +f(x0) avem ca :

f(x0) f(x) ≡ (x-x0) g(x) (mod m).

Congruențe de gradul întâi

Dacă f(x) este de gradul întâi, congruența o putem scrie sub forma ax ≡ b(mod m), a,b, a nu este congruent cu 0(mod m).

Teorema 3. Dacă numărul întreg x0 verifică congruența ax ≡ b(mod m), perechea (x0, ) este o soluție a ecuației diofantice ax +my =b, și, reciproc, dacă (x0, y0) este o soluție a ecuației diofantice, x0 satisface congruența.

Demonstrație. Dacă x0 verifică ax0≡ b (mod m), există un întreg y0 astfel încât b- ax0 =my0 deci ax0 +my0 =b. Reciproc, dacă ax0 +my0 =b, rezultă ax0 ≡ b(mod m).

Pentru rezolvarea congruenței ax ≡ b(mod m) putem folosi următoarele metode:

Metoda verificărilor. Se consideră un sistem complet de resturi modulo m: r1, r2, …..,rm. Fiecare rest ri care verifică congruența ne dă o soluție x ≡ ri (mod m).

Metoda ecuației diofantice. Se rezolvă ecuația diofantică ax +my =b, găsim soluția generală x = x0 + t, y= y0 – t. Soluțiile congruenței sunt: x≡ x0 (mod m), x≡ x0+( mod m), x x0 +2 (mod m),……., x x0 +(d-1) (mod m).

Metoda lui Euler. Dacă există soluții ale congruenței, congruența se aduce la forma ax ≡ b(mod m), (a,m)=1 (in cazul (a,m)=d 1 se împart a, b, m prin d). Conform teoremei lui Euler avem de unde rezultă a( și am pus in evident soluția x .

Metoda transformării coeficienților. Presupunem că (a,m) =1. Se folosesc următoarele transformări:

Se adaugă lui a si b un multiplu de m astfel încât să putem simplifica ambii membri ai congruenței printr-un număr prim cu modulul;

Dacă (b, m)= d1 se face substituția x =d1y;

Se caută un întreg s astfel încât as ≡ 1(mod m) și înmulțind ambii membri ai congruenței cu s se obține x ≡ bs (mod m).

Sisteme de congruențe de gradul intai

Fie sistemul de congruențe:

), (3)

Ai , i= , mi N , mi , i= .

Dacă una dintre congruențe nu are soluții, întregul sistem nu are soluții. Dacă congruențele sistemului (3) are respectiv câte s1, s2,…….,st soluții, pentru rezolvarea sistemului (3) avem de rezolvat un număr de s = s1s2………st sisteme de forma:

(4)

După cum s-a văzut, o soluție a sistemului (3) sau (4) este o clasă de resturi modulo m, unde m este cel mai mic multiplu comun al numerelor m1, m2,……., mt: m=[m1, m2,……, mt].

Teorema 4. (teorema chineza a resturilor). Dacă numerele naturale m1,m2,…….., mt sunt prime doua câte doua, atunci sistemul (4) admite soluție unica modula m,

m = m1m2…….mt, x≡ x0 (mod m), unde x0= M1a1b1 + M2a2b2+ ……+ Mtatbt. (5)

Demonstrație. Este suficient să arătăm că numărul x0 dat prin (5) verifică toate congruențele sistemului. Numerele m1, m2,……, mt fiind prime doua cate doua avem :

m= [m1, m2,………, mt] = m1m2……..mt si

Mk =, k = deci mi / Mk daca i k, si i,k= .

Rezulta ca x0 ≡ Miaibi (mod mi) si Mibi ≡ 1( mod mi), i= . Deci x ≡ ai (mod mi), i= .

Aplicație. Să se rezolve sistemul de congruențe

Soluție. Fiecare din cele 3 congruențe are soluție unică. Sistemul dat este echivalent cu :

Demonstrația teoremei 4 este constructivă indicând și modul de construcție a soluției (dacă există). Din prima congruența obținem x = 2+ 11r, r . Înlocuind în cea de a doua congruența obținem 11r ≡ 3(mod 7) ↔ t≡ 6(mod 7) ↔ t= 6+7u, u. Deci x= 68 +77u. Înlocuind în a treia congruența, onbținem 77u ≡ -64 (mod 5), adică 2u ≡ 1(mod 5) ↔ u≡ 3 (mod 5) ↔ u = 3 + 5s, s. Înlocuind în ultima expresie a lui x obținem x= 299 + 385s. Soluția sistemului este x ≡ 299 (mod 385).

Putem găsi soluția și folosind teorema chineza a resturilor. Avem m1 = 11, m2= 7, m3 = 5, m= =11 ·7 · 5 = 385, M1 =7 · 5 = 35, M2 = 11· 5= 55, M3 = 11 ·7 =77, a1= 2, a2= 5, a3= 4. Congruența 35y1 + 55y2 + 77y3 =1 are soluția particulară (6, -1, -2). Deci x0= 35 · 2 · 6 +55 · ·5(-1) + 77 ·4 · (-2) = -471 ≡ 299 (mod 385) și soluția este x ≡ 299 (mod 385).

Congruențe față de un modul prim

Considerăm congruența: f(x) ≡ 0 (mod p) (6), unde p este un număr prim, iar f(x) este un polinom de gradul n modulo p.

Teorema 5. O congruența algebrica modulo p, de gradul n modulo p, esste echivalenta cu o congruența de grad modulo p cel mult egal cu p-1.

Demonstrație. Fiind dată congruența (6), aplicăm teorema împărțiri cu rest pentru polinoame cu coeficienți întregi perechii f(x), xp – x: f(x)= (xp –x)q(x) +r(x) (7). r(x) are gradul algebric cel mult p-1 deci cu atât mai mult gradul modulo p este cel mult p-1. Conform micii teoreme a lui Fermat, pentru orice număr întreg x, avem xp –x ≡ 0(mod p). Egalitatea (7) ne arată că numărul întreg x0 verifică (6) dacă și numai dacă r(xo) ≡ 0(mod p).

Teorema 6. (Lagrange) O congruența algebrica fată de un modul prim admite cel mult atâtea soluții cât este gradul său.

Demonstrație. Facem inducție după gradul n al polinomului f(x). pentru n= 1, congruența c1x + c0 ≡ o(mod p), de gradul întâi modul p, satisface (c1, p) =1 și are o singura soluție. Presupunem că pentru orice polinom de grad mai mic ca n, g(x), congruența g(x0 ≡ 0(mod p) nu poate avea mai multe soluții decât gradul său. Fie f(x) un polinom cu coeficienți întregi, de grad n modulo p. Arătăm, prin reducere la absurd, că f(x) ≡ 0 (mod p) nu poate avea mai multe soluții decat gradul său. Fie x1, x2,….., xr reprezentanți ai soluțiilor congruenței f(x) ≡ 0(mod p), r n. Polinomul f(x) se divide modulo p cu x- x1 deci se scrie sub forma f(x) ≡ (x- x1)g(x) unde gradul lui g este cel mult n-1. Congruența f(x) ≡ 0( mod p) se scrie (x-x1) g(x) ≡ 0(mod p). Din (xk- x1)g(xk) ≡0 (mod p) rezultă că g(xk) ≡ 0( mod p), k= (xk –x1 este prim cu p). Rezultă că g(x)≡0 (mod p) are r-1 n-1 soluții și contrazicem ipoteza.

Consecința. Dacă o congruența algebrica f(x) ≡ 0( mod p ), de grad algebric n, are mai mult de n soluții, atunci toți coeficienții lui f(x) sunt multipli de p.

Consecința. Dacă pentru congruențele:

xn + an-1xn-1 + an-2xn-2 + …….+ a1x + a0 ≡ 0(mod p),

cn + cn-1xn-1 + cn-2xn-2 + …….+ c1x + co ≡ 0(mod p),

avem aceleași n solutii modulo p, p prim, atunci ak ≡ ck (mod p) , k= .

Rădacini primitive modulo m

Fie m . Conform teoremei lui Euler, daca b , (b, m) = 1, avem ≡ 1(mod m). Deci M ={ n N* , bn ≡ 1(mod m)} ≠ . Rezultă că există un prim element al mulțimii m.

Definiție. Dacă b , (b, m) =1, vom numi exponentul căruia aparține b modulo m, sau ordinal clasei de resturi modulo m, cu reprezentantul b, un număr N* care satisface condițiile

Vom nota = Em(b) = ord Ca mod mz.

Exemplu. E17(2) =8, deoarece 21, 22, ………, 27 nu este congruent cu 1(mod 17), 28 ≡1 (mod 17).

Teorema 7 Dacă (G, ·), este un grup abelian finit de ordin n, b G, și ordinul lui b este , atunci ǀ n.

Demonstrație. Procedăm prin reducere la absurd. Dacă ⌿ n, avem n= 0 r . Știm că bn = e. Deci bnq+r =e ceea ce implică br =e, 0 r și contrazicem definiția ordinului. Considerăm că grupul (G, ·) este grupul multiplicativ al claselor de resturi modulo m, prime cu m, acest grup are ordinul φ(m) și cel mai mic pozitiv pentru care = C1 ↔ ≡1(mod m) este tocmai exponentul lui a modulo m. . Ordinul unei clase de resturi modulo m, prima cu m, trebuie cautat printre divizorii lui φ(m).

Definiție Un număr intreg g, (g, m) =1, se numește rădăcina primitivă modulo m, dacă ordinul clasei de resturi modulo m, cu reprezentantul g este egal cu

Observație Dacă g este rădăcina primitive modulo m si g1 ≡ g(mod m). g1 este rădăcina primitivă m.

Lema. Dacă b este număr întreg impar si n N*, atunci există tn N astfel încât: b2n= 1 + +2n+2tn.

Demonstrație. Se face prin inducție dupa n. Fie b = 1 + 2k, k Z. Avem b2= 1 + 4k (k + 1)= 1+ 23 · Proprietatea este adevărată pentru n=1 cu t1 = .

Presupunem proprietatea adevărată pentru n. Pentru n + 1 vom avea b2n+1 = ( ) 2 = (1 + +2n+2tn)2 = 1+ 2n+3 tn (1+ 2 n+1tn) deci tn+1 = tn( 1+ 2n+1tn).

Lema. Dacă b este număr întreg impar și N, , atunci ≡ 1(mod ).

Demonstrație. φ (2n) = 2n – 2n-1 = 2n-1 , )= 2 n-2 . Aplicăm lema precedentă pentru n = = și obținem = 1+ echivalent cu

≡ 1 (mod ).

Teorema 8. Numărul impar b, prim cu p, p numar prim impar, aparține aceluiași exponent atât modulo , cât și modulul 2.

Demonstrație. bn ≡ 1 (mod ) si bn ≡ 1(mod 2) implică an ≡ 1 (mod 2 ). Reciproc, bn ≡ ≡1(mod 2) implică bn ≡ 1 (mod ).

Teorema 9. Un număr întreg g, (g, m) =1, este rădăcina primitivă modulo m, dacă și numai dacă g nu satisface nici una din congruențele: ≡ 1(mod m), ≡ 1(mod m)….., 1(mod m), unde c = φ(m), iar p1, p2,……, pr sunt toți factorii primi diferiți ai lui c.

Demonstrație. Dacă g este rădăcina primitivă ,g nu poate satisface nici una din congruențele anterioare deoarece = φ (m), i= . Demonstrăm prin reducere la absurd, că dacă g nu satisface nici una din congruențe, atunci g este rădăcina primitivă modulo m, deci dacă = =ordCg, = c. Dacă c, cum , vom avea c = , d. Există un divizor prim pi al lui c, astfel încât pi ⁄b. Deci: b= pid, c= pid, = si = = (d ≡1 (mod m), ceea ce contrazice ipoteza. Această teorema ne dă o metoda mai simplă pentru a determina rădăcinile primitive.

Indici modulo m

Teorema 10. Dacă g este o rădăcina primitivă modulo m si parcurge un sistem complet de resturi modulo c = (m), atunci parcurge un sistem redus de resturi modulo m.

Demonstrație. Fie:,,,…….. un sistem complet de resturi modulo c.

Considerăm șirul: , …….., . Sistemul acesta de numere are proprietațile:

Conține c = φ(m) numere;

(, m) =1, i= , deoarece (g, m) = 1;

≢ , daca i ≠j, deoarece ≡ ( mod m) ↔ I ≡ j (mod c) și contrazicem modul în care au fost alese numerele i.

Definiție. Dacă g este o rădăcină primitivă modulo m și a un număr întreg, (a, m) =1, se

numește indice al lui a modulo m, in baza g, un număr întreg cu proprietatea ≡ a(mod m).

Proprietațile ale indicilor

a≡ d(mod m)↔ indga ≡ indgd (mod c).

Demonstrație. a≡ d(mod m) ↔ ≡ (mod m) )↔ indga ≡ indgd (mod c), deoarece ordinul clasei lui g este c.

Dacă (a, m) = 1, (d, m)=1, ind (ad) ≡ indga + indgd (mod c).

Demonstrație. (a, m) = 1, (d, m)=1 → (ad, m) =1. Din ad (mod m) și ad ≡ (mod m) rezultă indg(ad0 ≡ indga +indgd (mod c).

Dacă (a, m)= 1, indgan ≡ nindga (mod m).

Proprietatea este o consecința imediata a proprietați anterioare.

Dacă (a,m) =1 d⁄a, atunci indg ≡ indga – indgd (mod c).

Demonstrație. (a, m) =1 implică (d, m) =1. Dacă dk =a, avem indgd + indgk= =indga(mod c).

Dacă g1, g2 sunt două rădăcini primitive modulo m si (a, m)=1 atunci

indg2a ≡ (ind g1a) (indg2g1) (mod c).

Demonstratie. Dacă a ≡ (mod m), obținem:

Indg2a ≡ (indg1a) (indg2g1) (mod c).

Dacă (a, m) =1 și ordinul clasei lui a, modulo m este atunci (inda, c)= .

Demonstrație. Evident ⁄c. Din ≡ 1(mod m) si a ≡ (mod m0 rezultă ≡ (mod m), deci c ⁄inda care implică / inda.

Fie un intreg oarecare, / inda, /c. Din inda ≡ 0(mod , înmulțind ambii membri și modulul cu obținem: inda ≡ 0(mod c) ↔ ≡ 1(mod m), adică ≡ 1 (mod 1). Rezultă că / , ceea ce implică / . Deci satisface cele doua proprietați care caracterizează c.m.m.d.c.

Condiția necesară și suficientă ca un număr întreg a, (a,m) =1, să fie rădăcina primitivă modulo m, este ca (inda, c) =1.

Demonstrație. Dacă a este o rădăcină primitivă modulo m, conform proprietații 6 avem (inda, c) = =1. Reciproc, dacă (inda, c) =1, tot din proprietatea 6 rezultă =1 deci =c, adică a este rădăcină primitivă modulo m.

Oricare ar fi baza g, avem:

indg1 =0, indgg =1, indg(-1) = φ(m) (pentru m >2).

Demonstrație. Primele două egalități sunt evidente. Din teorema lui Euler ≡

≡1(mod m), rezultă (-1) (+1) ≡ 0(mod m). cum putem avea ≡ 1(mod m) (g este rădăcină primitivă), rezultă ≡ -1(mod m).

Congruențe binome

Se numește congruența binoma o congruența de forma Axn ≡ B (mod m) (7), A,B , m,n N*. Dacă d= (A,m) si d ⌿ B, congruența nu are soluții. Dacă d ⁄ B, putem simplifica ambii membri și modulul cu d. Putem considera că (A,m) =1. Atunci, există A’ Z astfel încât AA’ ≡ 1(mod m). Înmulțind ambii membri ai congruenței Axn ≡ B (mod m) cu A’, obținem următoarea congruența: xn ≡ a(mod m) (8) , echivalentă cu (7).

Definiție. Numărul întreg se numește rest de gradul n modulo m dacă există soluții ale congruenței (8). Dacă nu are soluții congruența spunem că a este nerest de gradul n modulo m. Resturile sau neresturile se numesc pătratice pentru n= 2, cubice pentru n= 3, bipătratice pentru n= 4.

Definiție. Se numește rădăcină a unității de grad n si modulo m, o clasa de resturi modulo m, Cx, care satisface ecuația = C1.

Se numește rădăcină de gradul n si modulo m, a clasei de resturi modulo m, Ca, o clasa de resturi modulo m, Cx, care satisface ecuația = Ca.

Teorema 11. Dacă m este un modul pentru care există rădăcini primitive, într-un sistem redus de resturi modulo m există c/ e resturi de gradul n modulo m, unde c = φ (m), e =(n.c).

Demonstrație. Numărul întreg a este rest de gradul n, modulo m, dacă și numai dacă e/ind a. Pentru inda considerăm valorile din sistemul complet de resturi modulo c :1, 2, ……, c. Dintre acestea sunt multipli de e numerele 1·e, 2·e,…….., ) d care sunt în număr de .

Teorema 12. Fie m un modul fară de care există rădăcini primitive. Un număr întreg a, (a, m) =1, este rest de gradul n, modulo m, dacă și numai dacă ≡ 1(mod m).

Demonstrație. A este rest de gradul n, modulo m ↔e /inda ↔ inda ≡ 0(mod e) ↔

(c/ e)inda ≡ 0(mod c) ↔ ≡ 1(mod m) ↔ ≡ 1(mod m).

Exemplu. Să se determine clasele de resturi de gradul 6 modulo 23. Avem c = φ(23) =22, n=6, (6,22) =2.

Există =11 clase de resturi de grad 6 modulo 23. Găsim aceste clase luând reprezentanții lor care sunt acele numere al căror indice sunt divizibile cu e=2. Acești reprezentanți sunt: 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18. Se poate verifica că fiecare din aceste numere verifică a11 ≡ 1(mod 23).

Teorema 13. Dacă m este un modul fată de care exista rădăcini primitive, e= (n, φ(m)), resturi de gradul n modulo m coincide cu resturile de gradul d, modulo m.

Observație. Rezolvarea congruențelor care au forma xn ≡ a(mod m), (a, m)= 1, se reduce la rezolvarea congruențelor de această forma pentru care n / φ (m). Dacă aceasta congruența are soluții, ea are n soluții.

Teorema 14. Dacă m este un modul față de care există rădăcini primitive, n N*, n/ /φ(m), a Z, (a, m) =1, soluțiile congruenței xn ≡ a(mod m) se obțin înmulțind una din soluțiile acestei congruențe cu toate soluțiile diferite modulo m ale congruenței xn ≡ 1(mod m).

Demonstrație. Deoarece ind1 =0, n /0, congruența xn ≡ 1(mod m) are n soluții distincte modulo m: p1, p2,…….., pn. Fie x0 soluție a congruenței xn ≡ a(mod m). Vom avea :

(x0pi)n = ≡ a·1 ≡ a(mod m) i=.

Nu putem avea, pentru i≠j, xopi ≡ xopj (mod m) deoarece (x0, m) =1 și ar rezulta ti ≡ tj (mod m).

CAPITOLUL III: Numerele prime ale lui Mersenne

Numere perfecte

Suma divizorilor pozitivi ai numărului natural n se notează cu σ. Exemplu :

σ(1) = 1,

σ(2) = 1+2 =3,

σ(6) = 1+2 +3 +6= 12,

σ(12) = 1+2+ 3 +4 +6 +12 =28.

Fie p un număr prim, avem σ (p) =p +1 și facem convenția σ (0)= 1.

Pentru n> 1, dacă n are descompunerea canonica n= ……… avem:

σ(p) = · ………=

σ este o funcție aritmetică definită pe N, cu valori în N, multiplicative. Deci, dacă a,b N, (a, b)=1, atunci σ(a · b)= σ(a) · σ(b).

Definiție. Doua numere naturale a,b se numesc numere prietene sau numere amiabile dacă suma divizorilor lui a, mai putin a însuși, este egala cu b și suma divizorilor lui b, mai puțin b însuși, este egală cu a.

Deci, numerele naturale a si b sunt numere prietene dacă σ (a)= σ(b) = a+b.

Un număr natural se numește perfect dacă este prieten cu el însuși: σ(a) –a= a.

Definiție. Numărul natural a se numește perfect dacă σ (a) = 2a.

Incă din școala lui Pitagora au fost studiate perechile de numere naturale prietene și numerele perfecte. Aici a fost pus în evidentă faptul că numerele 220 si 284 sunt prietene. Intr-adevar,

220= 22 · 5· 11, σ(220)= · · =504,

284 = 22 ·71, σ(248) = · =504, deci

σ(220)= σ(284) =220+ 284 =504.

Leonard Euler a găsit 65 de perechi de numere prietene, dintre care menționam perechea 18416 si 17296, 18416 = 24 · 1151, 17296 = 24 ·23 · 47.

Boethis ( 475-524) a introdus noțiunile de număr saturat și număr deficitar.

Definiție. Se numește numere saturate numerele naturale n care satisfac condiția:

σ (n)> 2n.

Se numesc numere deficitare numerele naturale n care satisfac condiția:

σ(n) < 2n.

Teorema 1. Numerele naturale, care sunt puteri naturale ale unor numere prime, sunt numere deficitare.

Demonstrație. Fie p prim și n= , N*. Deoarece σ (n) = , vom avea:

σ(n) < 2n↔ = < 2 ↔ > 21

și ultima egalitate este evidentă:

221.

Teorema 2. Numerele naturale impare, care au numai doi divizori primi diferiți, sunt numere dificitare.

Demonstrație. Fie n = ·, p1 si p2 numere prime diferite de 1, 2 N*. Vom avea p1 3, p2 5. Trebuie să arătăm că <2.

Avem:

σ(n) = · < · .

Rezultă că

< · < = <2

(funcția f: (1, +) →R. f(x) == 1+ este monoton descrescător).

Teorema 3. Dacă numărul natural n are forma n= 2z( 2z+1 -1), z * si p = 2z+1 -1 este număr prim, atunci n este număr pătrat.

Demonstrație. (2z, 2z+1 -1)= 1, deoarece 2z+1 -1 este impar. Prin urmare,

σ(n) = σ(2z( 2z+1 -1) )= σ()σ (2z+1 -1).

Cum σ( 2z)= 2z+1-1,

σ(2z+1-1) = 1+( 2z+1-1) = 2z+1.

Din aceste două relații rezultă σ(n) = 2z+1 (2z+1-1) =2n.

Numerele prime ale lui Mersenne

Definiție. Se numește numerele prime ale lui Mersenne, numerele prime de forma p= am-1, m.

Teorema 4. Fie a,m N, m>1. Dacă numărul am-1 este prim, atunci a=1 și p este număr prim.

Demonstrație. Din am-1 =(a-1) ( am-1+ am-2 +………..+1) si a-1 < am-1+ am-2 +………..+1 rezultă a-1 =1, deci a=2.

Pentru a arăta că dacă 2m-1 este numar prim, atunci m este prim, procedăm prin reducere la absurd. Presupunem că există u, s N, 1< u < m, 1< s < n, astfel încât m= us. Vom avea:

2m-1 = (2u)s -1s= (2u-1) (2u(s-1)+ 2u(s-2)+……..+1)

și cum 1< 2u-1 < 2m-1, rezultă că 2u-1 este un divizor propriu al lui 2m-1 și contrazicem ipoteza că acest ultim număr este prim.

Definiție. Se numește șirul lui Mersenne șirul (Mn), unde Mn =, pn fiind cel de al n-lea număr natural prim(adică termenul de rând n din șirul P = (2, 3, 5, 7, 11, 13,….., pn….). Numerele prime ale lui Mersenne sunt acei termini din șirul lui Mersenne care sunt numere prime.

Pentru primele șase numere prime avem:

Pentru numerele prime 2, 3, 5, 7, 13 am obținut numerele prime ale lui Mersenne 3, 7, 31, 127, 8191, cărora le corespund numerele perfecte 6= 2(22-1), 28= 22 (23-1), 496= 24( 25-1), 8128 = 26(27-1), 33550336 =212(213-1). Pentru numărul prim p=11, 211-1 =23 ·89 nu este prim. Acest exemplu ne arată că pentru propoziția ‘2p-1 este număr prim’, propoziția ‘p este prim’ este condiție necesară dar nu și suficientă.

Mersenne (1588-1648) a calculat primi 55 termeni din șirul (Mn) (pentru numerele prime de la 2 la 257), pe care le-a considerat ca fiind numere prime. Ulterior s-a arătat 2p-1 este prim pentru p {2, 3, 5, 7, 13, 19, 31, 61, 89, 107, 127} și este compus pentru toate celălalte numere prime p 257

Un criteriu pentru numerele prime ale lui Mersenne

Un criteriu (o condiție necesară și suficientă) pentru că Mn să fie numar prim a fost formulat de Lucat și demonstrate de D.H.Lehmer.

In acest scop a fost considerat șirul {sn} cu n N*, unde

s1=4, s2=14 si sn= -2 pentru n 3,

adică șirul 4, 14, 194, 37634, 141631794,…….. .

Fie numerele a = 1+, b= 1- . Avem a+b =2, a-b=2, ab= -2. Considerăm șirurile (un) și (sn) cu nN*, unde

un= , sn= an +bn, (1)

adică

u1=1, u2=2, u3=6, u4=16, u5=44, u6=120,…….

s1=2, s2=8, s3= 20, s4= 56, s5= 156,……

Teorema 5. Teremeni șirului (1) verifică urmatoarele egalități :

2ur+t= urst +srut, (2)

(-2)t+1 ur-t = utsr – urst, (3)

2sr+t= srst + 12urut;

u2r= ursr,

s2r = + (-2) r+1,

-12 = (-2) r+2.

Demonstrație. a) urst +srut = (at +bt) + (ar +bt) =2ur+t.

b)evident r> t si utsr- urst= [( at +bt)] (ar +br) – (ar-br) (at +bt)] = = (-2)t+1 ur-t

c)srst +12urut = (ar +br) (at+bt) +(ar – b2) (at – bt)= (ar + br) (at + bt) + (ar+ br) (at +bt)= 2(ar+t +br+t ) = 2sr+t.

d) ursr = (ar –br) (ar +br)= ( a2r-b2r) = u2r.

e)s2r= a2r +b2r = (ar +br) 2 -2arbr = +(-2)r+1.

f) -12 = (ar+br)2 – (ar-br )2= (ar+br)2 –( ar-br)2 = 4(ab)r = (-2)r+2.

Definiție. Fie p un număr prim, p>3. Se numește marca lui p, în raport cu șirul un, numărul natural care satisface condițiile:

(ur, p) = 1, pentru r<

(, p)= p.

Teorema 6. Dacă este marca numărului prim p, atunci p/ ur dacă și numai dacă / r.

Demonstrație. Fie M mulțimea indicilor r pentru care p/ ur. Egalitațile (2) si (3) ne arată că dacă r, t M, atunci r+t și r-t aparțin lui M. Conform definției anterioare este prim element în M ( cel mai mic dintre numerele naturale care aparțin lui M)

Fie r M, arbitrat. Deoarece 0, putem aplica teorema împărțiri cu rest perechii (r,). Există și este unic determinat o pereche de numere naturale (k, h) astfel încât r= wk +h, h<

Din M rezultă 2 = + , 32 +……., k,……..aparțin lui M, r M și k M implică h= r- M ceea ce implică h=0.

Teorema 7. Pentru orice număr prim p, p 3,avem:

up ≡ (mod p), sp ≡ 2(mod p).

Demonstrație. Avem up = [( 1+ )p – (1 – p]= ≡ , deoarece p/ pentru 1 h p-1. Apoi, sp = ( 1+ )p + (1 – p = 2 ≡ 2(mod p).

Teorema 7. Dacă este marca numărlui prim p, atunci p+1.

Demonstrație. Vom demonstra că p / up+1· up-1 ceea ce implică p/ up+1 sau p/ up-1 deci p+1.

In egalitațile (2) și (3) facem r =p si t=1 și ținem cont că u1=1, s1=2. Obținem:

2up+1 = 2up + sp

4up-1 = sp- 2up. (4)

Înmulțind membru cu membru egalitațile (4) obținem 8up+1 +kp-1 = – 4.

Conform teoremei precedente și ținând cont că 3p-1 ≡ 1(mod p)( mica teorema a lui Fermat, p>3) obținem: 8up+1up-1 ≡ 4 -4 · 3p-1 ≡ 4-4 =0 (mod p).

Din p / 8up+1 up-1 si (8, u)=1, rezultă p/ up+1up-1.

Reamintim că am notat cu pn termenul de rang n din șirul numerelor naturale prime.

CAPITOLUL IV: Numere prime ale lui Fermat

Sirul lui Fermat

Pierre Fermat (1601- 1665), contemporan cu Mersenne, și-a pus problema numerelor prime p de forma p =2m+1. El a arătat că, pentru ca numărul p =2m+1 să fie prim, este necesar ca m să fi o putere a lui 2, m= 2z, z N.

+1 =3, +1= 5, +1= 17, + 1= 257, +1= 65537,

a constat că toate sunt numere prime și a formulat ipoteza că toate numerele +1, z sunt numere prime.

Definiție. Se numește șirului lui Fermat sirul (Fn) nN, unde Fn= +1 :

3, 5, 17, 257, ……, +1,…………. (1)

Temenii șirului (1) se numesc numerele lui Fermat. Termenii șirului (1) care sunt numere prime se numesc numere prime ale lui Fermat.

Teorma 1. Dacă numărul p= 2k+1, k N un număr prim, atunci k este de forma k= 2z, z.

Demonstrație. Fie p= 2k+1, k N un număr prim. Orice număr natural k, k ≠0, se scrie sub forma k= 2zu, z,u , u număr impar. Presupunem că numărul k nu este de forma k= 2z ceea ce înseamna că u>1. Vom avea:

p =2k+1 = +1 = )u +1u =( +1)( + +……+1).

Rezultă că +1 este un divizor propriu al lui p deoarece 1< +1 < +1, ceea ce contrazice ipoteza că p este prim. Prin urmare u=1 si k= 2z.

Proprietăți ale numerelor lui Fermat

Teorema 2. Cu excepția lui F0 si F1, toate numerele lui Fermat, scrise în baza 10, se termină cu cifra 7.

Demonstrație. Este suficient să arătăm că, pentru n 2, Fn +3 se termină cu cifra 0, adică 10/ Fn+3. Din Fn+3 =4 +1) (1) rezultă că 4/Fn+3.(2)

Numărul +1= +1 se termină cu cifra 5 deoareca, pentru n>1, 2n-1-1 este un număr impar și orice putere impară a lui 4 se termină cu cifra 4. Rezultă că 5/Fn +3 (3).

Din (2) si (3) si (1,2) =1, rezultă 4 · 5/ Fn+3 ceea ce implică 10/ Fn+3.

Teorema 3. Pentru orice număr natural t,n, t>n, avem:

Fn/ Ft-2.

Demonstrație. Există un număr natural u, u≠ 0 astfel încât t= n+u. Rezultă că:

Ft – 2 = = ()2u – = ((-1) ( (+1)=

= ( ()-1) ((+1)( (+1) = …… =

= (( ) ((2 +1)………..((+1).

In ultimul produs primul factor este tocmai Fn. Rezultă că Fn/Ft-2.

Teorema 4. Oricare ar fi doua numere naturale t, n, t+n, avem (Ft, Fn) =1.

Demonstrație. Putem presupune t>n (astfel schimbăm ordinea celor doua numere). Notăm (Ft, Fn) =d.

Din d/ Fn, Fn/Ft-2 rezultă că d/Ft-2. Dar d/Ft și rezultă d/ 2 ( 2= Ft- (Ft-2)). Rezultă că d=1 sau d=2. Intrucât Fn si Ft sunt impare, avem d=1.

Teorema 5. (Euclid) În șirul numerelor naturale există o infinitate de numere prime.

Demonstrație. Pentru orice număr natural n, numărul Fn are un divizor prim pn (Fn>1). Șirului lui Fermat îi corespunde un șir de numere naturale prime (pn) nN. Pentru t ≠n, pn ≠pt (conform teoremei precedente). Deci (pn) este un șir de numere prime diferite două câte două.

Numere prime ale lui Fermat

Teorema 6. Numărul Fn= +1, n N, n>0, este prim dacă și numai dacă

≡ 1(mod Fn).

Demonstrație. Presupunem n=0, F0 = +1= 3 si ≡ 1(mod 3) ↔ 3 ≡ -1 (mod 3) este falsă. Pentru n> 0 presupunem că Fn este număr prim.Observăm că Fn= +1= ()2 +1= +1= +1. Prin inducție, se verifică imediat că pentru t>0, 4t ≡ 4(mod 120, deci Fn este de forma Fn = 12k +5. Conform criteriului lui Euler de la resturi pătratice, avem:

≡ (mod Fn) (4)

Unde este simbolul lui Legendre. In baza legii de reciprocitate a lui Gauss, avem:

= = = = =-1. (5)

Din (4) si (5) rezultă că :

≡ -1(mod Fn).

Considerăm adevarată congruența din enunțul teoremei, iar prin ridicare la pătrat a ambilor membri, obținem: ≡ 1(mod Fn). (6)

Dacă p este cel mai mic divizor propriu al lui Fn, p este prim (p>1). Din (6) rezultă

≡ 1(mod p).

Notăm cu ordinul clasei de resturi modulo p, cu reprezentantul 3. Din proprietățile ordinului rezultă / Fn-1, adică / . Rezultă că este de forma 2k, k n. Nu putem avea k< n deoarece ≡ 1(mod p), prin ridicări succesive la pătrat a ambilor termini ai congruenței, obținem ≡1(mod p) relație care contrazice congruența din enunțul teoremei (din congruența inițială rezultă ≡ -1(mod p). Deci = 2n. Din proprietațile ordinului avem

p-1 ≡ 0 (mod adică p= h· +1.

Din p/ Fn rezultă p Fn, adică h+1 +1. Deci h= 1 si p =Fn ceea ce demonstrează suficiența condiției din teoremă.

De exemplu, pentru n=1, F1 =5, ≡ -1(mod 5) deci, conform teoremei precedente 5 este prim. Pentru n=2, F2 = 17, ≡ -1(mod 17) ↔ 38 ≡ -1(mod 17) ↔ 812 ≡ -1(mod 17) ↔ (-4)2 ≡ ≡ -1(mod 17). Ultima congruență este evidentă și am verificat că 17 este număr prim. Pentru a arăta că F3 = 257 este prim trebuie să arăt că 3128 ≡ -1(mod 257).

Numerele Fn si cresc extrem de rapid și ne dăm seama că pentru n 3 este preferabil să verificăm dacă Fn are sau nu divizori primi, mai mici ca Fn.

Teorema 7. Pentru n>1, orice divizor prim al numărului Fn = +1 are forma p= =k·2n+2+1.

Demonstrație. Fie p un divizor prim al lui Fn. Din Fn≡ 0(mod p) rezultă ≡-1(mod p) și ridicând ambii membrii ai congruenței la pătrat, obținem ≡ 1(mod p).

Rezultă că ordinul clasei lui 2, modulo p, este 2n+1 și, cum ordinul divide p-1, vom avea p ≡ 1(mod 2n+1). Pentru n>1 avem p ≡1(mod8). Deci conform criteriului lui Euler, avem:

≡( ) (modp) si ( ) =1.

Rezultă 2n+1 / , adică 2n+2 / p-1 și prin urmare p este de forma p =k· 2n+2 +1.

Știm că un număr natural n este prim dacă și numai dacă nu are nici un divizor prim p, p. Pentru a arăta că Fn este prim trebuie să arătăm că nu are divizori primi p , de forma p = k· 2n+2 +1 și

k k· 2n+2 +1 = < +1.

Rezultă k< -n-2.

Teorema 8. Pentru orice k N* avem d/ – sk. (7)

Demonstratie. Folosim metoda inducției complete. Pentru k=1, proprietatea este adevarată: d/0 . Presupunem proprietatea (7) adevarată pentru numărul natural k. Vom avea:

– sk+1 =( )2 – ( )2 = () ().

Dar

– = () +(sk ).

Rezultă că d/ – .

Consecința. Numerele Fn si sn+1 dau același rest la împărțirea cu d.

CAPITOLULV: Numerele lui Fibonacci

Șirul numerelor lui Fibonacci

O carte remarcabila în istoria matematicii apare în Italia în anu 1021 și este intitulată Liber abacci. Autorul, matematicianul Leonardo din Pisa, cunoscut sub numerele de Fibonacci este cel mai important precursor al secolului de aur din istoria matematici. Ediția 1228 a cărții lui Fibonacci este tratată următoarea problema:să se determine numărul de perechi de iepuri care se vor naște într-un an dintr-o pereche de iepuri nou nascuți, știind ca o pereche de iepuri poate da naștere la o noua pereche (devine matura) dupa o luna.

Observăm că, dacă notăm cu tn numărul de perechi de iepuri din cea de-a n-a lună a anului, avem:

t1= 1, t2=1, t3=2, t4= 3, t5= 5, t6= 8, t7= 13, t8= 21, t9=34, t10=55, t11= 89, t12= 144……

Astfel a apărul unul dintre cele mai studiate șiruri de numere, cu proprietați și generalizări interesante și cu multe aplicații importante.

Definiție. Se numește șirul lui Fibonacci șirul (tn) t N* dat prin relația de recurență:

tn+2= tn+1 + tn (1)

și condițiile inițiale t1 = t2 =1.

Terminii șirului lui Fibonacci se numesc numerele lui Fibonacci.

Propoziție. Avem:

t1 + t2 + …….+ tn = tn+2 -1.

Demonstrație. Conform egalitații (1) putem scrie

t1= t3 –t2

t2= t4 – t3

tn= tn+2 – tn+1

Adunând membru cu membru aceste egalități, obținem:

t1 + t2+…… + tn= tn+2 – t2 = tn +2 -1.

Propoziție. Avem

t1 + t2+ t5 +…….+ t2n-1= t2n. (2)

Demonstrație. Conform definiției avem:

t1 = t2,

t3= t4- t2,

t5= t6 –t4,

…..

t2n-1 = t2n –t 2n-2.

Sumând membru cu membru aceste egalitați obținem (2).

Propozitie. Avem:

t2 + t4 + t6+ ……+ t2n = t2n+1-1. (3)

Demonstrație. Conform propoziției (1) avem

t1 +t2 + ……+t2n = t2n+1-1 (4).

Scazând membru cu membru egalitațile (4) si (2), obținem:

t2 +t4 +…….+ t2n = t2n+2t2n = t2n+1 -1.

Propoztie. Avem:

t1 –t2 +t3 –t4 +……..+ (-1)n+1tn= (-1) n+1tn-1+1.(5)

Adunând t2n+1 în ambii membri ai egalității (5) pe tn+1 obținem:

t1- t2+ t3+……..+ t2n-1-t2n +t2n+1 = t2n+1.

Propoziție. Avem:

+ + ……….+.= tntn+1. (6)

Demonstrație. Observăm că

tktk+1 – tk-1tk = tk (tk+1 –tk-1 ) = .(7)

Conform definiției și egalitații (7), avem:

= t1t2,

= t2t3 – t1t2,

= t3t4 – t2t3,

……..

= tntn+1 – tn-1tn.

Sumând membru cu membru aceste egalitați obținem (6).

Propoziție. =tn tn+2 +(-1)n. (8)

Demonstrație. Pentru n=1, proprietatea este adevarată:

= t1t3 -1 ↔ 12 = 1·2 -1.

Presupunem că (8) este adevarată. Adunând în ambii membri tn+1tn+2, obținem

+ tn+1tn+2 = tntn+2 + tn+1tn+2 + (-1)n,

deci

tn+1( tn+1 +tn+ 2) = tn+2 (tn + tn+1) +(-1)n,

adică

tn+1tn+3 = +(-1)n,

deci, proprietatea este adevarată pentru n+1.

Propoziție. t1t2 + t2t3+……..+ t2n-1 t2n = , (9)

t1t2 + t2t3+……..+t2n t2n+1= -1. (10)

Demonstrație. Identitatea (9) se demonstrează prin inducție. Pentru n=1 avem t1t2= .

Presupunem (9) adevarată. Vom avea:

t1t2 + t2t3+……..+ t2n-1 t2n+ t2n t2n+1 + t2n+1t2n+2 = + t2n t2n+1 + t2n+1t2n+2 = t2n ( t2n + t2n+1) + +t2n+1t2n+2 = t2n+2 ( t2n + t2n+1 ) = .

Identitatea (10) rezultă imediat din (9):

t1t2 + t2t3+……..+ t2n-1 t2n+ t2n t2n+1 = + t2n t2n+1 = t2nt2n+2 = -1 (conform propoziției anterioare).

Propoziție. tn = + + +…… (11) (suma din membru al doilea se termină când este încalcată regula indicilor de la combinări: pentru trebuie sa avem 0 ; in caz contrat =0 )

Demonstrație. Formula (11) a fost verificată pentru n = . Presupunem că formula este adevarată pentru n-1 si n-2.

tn-1 = + + + ….

tn-2 = + + +……

Vom avea:

tn= tn-1 + tn-2 = + ( + ) + ( + ) +….= + + +…….

Adaugăm șirului lui Fibonacci termenii t-1 =1 , t0 =0.

Șiruri recurente liniar

Definitie. Șirul de numere (tn) t N se numește șir recurent liniar de ordinul k, dacă există k numere fixate a1, a2, …….., ak, ak ≠ 0 astfel încât

tn+k = a1tn+k-1 + a2tn+k-2 +…….+ aktn, n N. (1)

Exemplu. Progresie geormetrică a, aq, aq2 , ………., tn= aqn,

este un șir recurent de ordinul întâi: k= 1, a1= q, an+1 = qtn.

Exemplu. Progresie aritmetica a, a+ p, a+ 2p,…… este un șir recurent de ordinul al doilea. Daca tn=a +np avem tn+2 = 2tn+1- tn.

Exemplu. Șirul lui Fibonacci este un șir recurent de ordinul al doilea.

Exemplu. Șirul pătratelor numerelor naturale:

t0 = 02, t1 = 12, t2= 22, ……tn = n2…… este recurent de ordinul al treilea deoarece:

tn+1 =(n+1) 2 = n2 +2n+1 =tn+2n +1 si tn+2 =tn+1 +2n +3.

Scăzând membru cu membru ultimile doua egalitați, obținem

tn+2 = 2tn+1 – tn +2 și mărind n cu o unitate

tn+3 = 2tn+2 – tn+1 +2.

Din ultimile două egalitați obținem

tn+3 = 3tn+2 – 3tn+1 +tn.

Exemplu. Șirul coeficientilor câtului împărțirii a doua polinoame ordonate dupa puterile crescătoare ale lui x,

P(x)= A0 + A1x +……+ Alxl,

S(x)= B0 + B1x+ ………+Bkxk , B0 ≠ 0,

este un șir recurent de ordinal k.

Fie șirul (En) unde :

= E0 + E1x + E2x2+ ………+ Enxn+ …….

Fie n un număr natural, n l-k +1, și presupunem că ne oprim cu câtul împărțirii lui xn+k:

P(x) = S(x) (E0 + E1x + ………+ En+kxn+k) + R(x).

Egalând coeficientul lui xn+k din membrul al doilea cu cel din membrul întâi, obținem

En+k B0 + En+k-1B1 + ….+ EnBk = 0

și, cum B0 ≠ 0, rezultă

En+k = – En+k-1 – En+k-2 -…….- Dn.

Teorema 1. Dacă șirul (tn ) n 0 satisface relația de recurență

tn+k = a1tn+k-1 + a2tn+k-2+ …… + antn.

atunci șirul (tn) coincide cu șirul coeficienților împărțirii unui polinom de grad n0+ k- 1, P(x), prin polinomul S(x) = 1 + a1x – a2x2 – …… – akxk iar P(x)= t0+ (t1 +a1t0 )x + (t2 –a1t1 – a2t0 )x2 +…..+ (tk-1- a1tk-2 -………- a1to )xk-1 în cazul n0=0 si p(x) = t0 +(t1 –a1t0 )x +…..+ (ak-1- a1tk-2 + …+ a1t0 )xk-1 + ( tk –a1tk-1 …..akt0) xk + …..+ ( tn0+k-1 – a1tn0+k-2 …….a0tn0-1) xn0+k-1 în cazul no>0.

Demonstrație. Observăm că:

P(x) = (1- a1x – a2x2 – ……. – akxk ) (t0 +t1x + t2x2 +…… +tnxn +….) = t0+ (t1 –- – a1t0)x +…… + (tn –a1tn-1- ……- aktn-k ) xn….

Datorită relației de recurență, coeficientul lui xn, pentru n n0+k, este egal cu 0. Deci P(x) este un produs de grad n0 +k -1 si

= to + t1x + ……..+ tn xn+ …….

Teorema 2. Orice combinație liniară de șiruri care satisfac relația de recurentă (1) este un șir care satisface relația (1).

Demonstrație. Dacă șirul (tn) n 0 satisface (1), atunci șirul (α tn) n 0, unde α este o constantă, satisface (1) deoarece:

αtn+k = a1 αtn+k-1 + …….+ ak αtn.

Dacă (tn ) n 0 si (vn) n 0 sunt două șiruri care satisfac (1) deci :

tn+k = a1tn+k-1 + ….+ aktn

vn+k = a1vn+k-1 + …+akvn

rezultă că șirul (tn +vn) n 0 satisface (1):

tn+k + vn+k = a1 ( tn+k-1 + vn+k-1 ) +…..+ ak(tn +vn).

din aceste două afirmații rezultă, prin inducție, că dacă ( ) n 0, i= satisfac (1), șirul (α1tn(-1) + α2tn(2) + ……+ αltn(l) ) n 0 satisface relația (1).

Teorema 3. Dacă , no, i= si (vn) sunt șiruri care satisfac relația de recurență (1), pentru orice n 0, si

vj = I + 2 +………….+ l , j= ,

atunci vn= I + 2 +………….+ l , oricare n N.

Demonstrație. Se face prin inducție. Pentru n = proprietatea este adevarată prin ipoteză. Presupunem că vj = I + 2 +………….+ l , j= .

Scriem că șirul (vn) cu n 0 satisface (1) și obținem vn+k= I + 2

Teorema 4. Pentru șirul lui Fibonacci, dat prin tn+2 = tn+1 + tn, t0= 0, t1 =1, avem:

tn = [( ) n – ( ) n ].

Demonstrație. Relației de recurență tn+2 = t n+1 +tn îi corespunde ecuația caracteristică x2-x -1 =0, care are ca rădăcini (distincte) numerele ω = , = . Deci termenul general din șirul lui Fibonacci are forma:

tn = c1 ωn + c2 n .

c1 și c2 sunt date de sistemul c1ω0 + c2 0 = 0, c1ω + c2 =1. Adică

rezultă că c1 = , c2 = și obținem

tn = [( ) n – ( ) n ].

Această formulă este cunoscută sub numele de formula lui Binet. Formula a fost stabilită de Moivre în 1718 folosind metoda funcției generatoare elaborate de Nicolas Bernouli.

Fiecărui șir numeric (tn) n 0 i se asociază funcției generatoare

G(z)= t0 + t1z + t2 z2 +…….+ tnzn +…. (2)

Avem și

zG(z) = t0z + t1z2 +……. + tn-1zn +……. (3)

z2G(z) = t0z2+………….+ tn-2zn +…….. (4)

Scăzând din (2) suma lui (3) cu (4) și ținând cont că în cazul șirului Fibonacci tn –tn-1-tn-2 =0, obținem

(1 –z –z2 )G(z) =z,

deci, pentru șirul lui Fibonacci funcția generatoare este

G(z) = .

Polinomul 1- z- z2 are rădăcinile –ω si – . Din

= +

rezultă A = – , B= , deci

G(z) = ( – ).

Pentru | ωz | ↔ |z | < | | avem

Rezultă că

G(z) = ,

Deci

tn =

Formula lui Binet poate fi stabilită și prin metoda inducție. Intr-adevar t0 =0 =, t1 =1 =( ).

Presupunem că:

tn = ,

tn+1 = ,

Vom avea:

tn+2 = tn+1 + tn = =

= [ ωn ( ω +1)- n ( = ( ωn+2 – n+2)

(ω si sunt rădăcinile ecuației x2 = x+1).

In cazul când relația de recurentă (1) are rădăcini multiple se poate construi o baza în mulțimea S a tuturor șirurilor care satisfac (1). Se poate proceda astfel: dacă x1 =α este o rădăcina de ordin de multiplicitate α, introducem în baza șirurile

,

care verifică relația de recurentă (1) și sunt liniar independente.

Aplicații ale formulei lui Binet

Teorema 5. t3 + t6 +……+ t3n = .

Demonstrație. Avem: t3 + t6 +…… + t3n = ( ω3 + ω6 + …… + ω3n – 3 – 6 -…..- 3n = ( ω3n+3 – ω3 / 2ω – 3n+3 – 3n / 2)

ω si sunt rădăcinile ecuației x2 = x+1 → x3 -1 =2x. Deci ω3 -1 =2ω si 3 -1 =2. Rezultă că:

t3 + t6 +….. + t3n = (ω3n+3 – ω3 / 2ω – 3n+3 – 3n / 2 )= ( – ) = (t3n+2 -1).

Teorema 6. + …………. + = .

Demonstrație. Avem = ( ) 3 = · = ( – 3ωk ) = ( t3k + (-1)k+1 3tk ).

+ …. + = ( t3+ t6 +…….t3n) +3 (t1- t3 +…..+(-1)n+1 tn) .

Folosind teorema anterioara, obținem

+ …. + = ( +3(-1)n+1 tn-1) = .

Teorema 7. Tn este cel mai apropiat număr întreg de .

Demonstrație. Scriem fomula lui Binet sub forma

Tn = + (-1)n+1 ( )n .

Trebuie să arătăm că ( )n . Și această inegalitate se verifică imediat prin inducție.

Teorema 8. Pentru orice n , t-n =(-1) n-1tn.

Demonstratie. Proprietatea este adevarată pentru n = 0, 1, 2, 3, 4.

Presupunem că t-n+2 = (-1)n+3 tn-2 ,

t-n+1 = (-1)n-2 tn-1.

Vom avea:
t-n = t-n+2 – t-n+1 = (-1)n+3 tn-2 – (-1)n-2 tn-1 = (-1) n-1 (tn-2 + tn-1 )= (-1)n-1tn.

Proprietați de divizibilitate. Numere prime din șirul lui Fibonacci

Teorema 9. Dacă d /n, atunci td / tn.

Redemonstrăm teorema folosind metoda inducției. Trebuie să arătăm că td / tdk, k N.

Pentru k= 0 si k=1, proprietatea este evident adevarată. Presupunem că td / tdk. Vom avea că

td(k+1) = tdk+d = tdk-1td + tdktd-1 și rezultă că td / td (k+1).

Consecința. Dacă n este număr compus, n≠ 4, atunci tn este număr compus.

Demonstrație. t4 =5 este prim. Dacă n= n1n2, 1< n1 n2 , cel puțin n2 >2, deci tn2>1, tn2 <tn si tn2 /tn,

Teorema 10. Doua numere consecutive din șirul lui Fibonacci sunt prime între ele.

Teorema rezultă din (t0, t1) = (t1, t2) =1 și conform algoritmului lui Euclid aplicat la sfarșitul paragrafului precedent, pentru n>2, (tn, tn+1) =1. Teorema poate fi demonstrată și prin inducție, observând că din tn+2= tn+1 +tn rezulta ca (tn, tn+1) = (tn+1, tn+2).

Teorema 11. (tm, tn) = t(m, n).

Demonstrație. Pentru m=n, proprietatea este adevarată.

Fie m >n. Aplicăm algoritmul lui Euclid perechii de numere naturale m si n:

m= nq0 +r1, 0< r1 < n,

n= r1q1 +r2, 0< r2 <r1,

……………

rv-1 = rv-1qv-1 +rv, 0< rv < rv-1,

rv-1= rvqv.

Vom avea:

(tm, tn) = (tnq0+r1, tn) =( tnq0-1tr1 + tnqotr1-1, tn) = ( tnq0-1tr1, tn) = ( tr1, tn)

( tnqo este multiplu de tn si tnqo-1, tnqo fiind prime între ele, tnq0-1 si tn sunt prime între ele). Rezultă că:

(tm, tn) = (tn, tr1) = (tr1, tr2) = … = (, ) = = t(m, n)

Teorema 12. m/n ↔ tm/ tn .

Demonstrație. Am demonstrat că m/ n implică tm /tn. Dacă tm /tn avem (tm, tn) =tm si conform teoremei precedente (m, n)= m, adică m/n.

Consecința. 2/ tn ↔ 3/n.

Consecința. 3/ tn ↔ 4/n.

Consecința. 4/tn ↔ 6/n.

Într-adevar, t6 =8. Din 8 /tn ↔ 6/n. Dar 8/ tn ↔ 4/ tn deoarece orice n este de forma n= 6k+r, r { 0, 1, 2, 3, 4, 5}

tn = t6k+r = t6k-1tr + t6ktr+1.

și dacă 4/ tn rezultă 4/ tr deci r = 0, n =6k si 8 /n.

Consecința. 5/ tn ↔ 5/n.

Consecința. 7/ tn ↔ 8/ n.

Intr-adevar, t8 =21, deci 8/n ↔ 21/n. Analog cu a treia consecința se arată că 21/ tn ↔7/ tn.

Consecința. 6/ tn ↔ 12/ n ↔ 12/ tn.

Consecința. 10/ tn ↔ 15/ n.

Consecința. 15/ tn ↔ 20/ n.

Consecința. Nu există numere impare ale lui Fibonacci care se divid cu 17.

Demonstrație. t9 =34. Deci 31/ tn ↔ 9/ tn. Fie n =9k +r, r {0, 1, ….., 8}. tn = t9k-1+ tr + t9k+1. Dacă 17/ tn rezultă 17/ t9k-1 deci 17/ tr si r=0. Deci n =9k si 31 /tn implică t3 par.

Consecința. Nu există numere ale lui Fibonacci care împărțite la 8 să dea restul 4.

Demonstrație. tn = 8q +4 implică 4/ tn si 8/ tn și am văzut că 4/ tn ↔ 8/ tn.

Consecința. Dacă (m, n) =1, atunci tmtn /tmn.

Demonstrație. tm/tmn si tn/ tmn. Din (m, n) =1 rezultă (tm, tn )=1. Rezulltă tmtn/ tmn.

Bibliografie

Vorobiev, N.N., Numerele lui Fibonacci, Editura Tehnică, București, 1953.

Minut, P., Teoria numerelor( capitole introductive), Editura “C. Gâldău”, Iași,1997.

Minut, P., Teoria numerelor (capitole de baza), Editura MATRIX ROM, București 2001.

Markusevici, A.I., Șiruri recurente, Editura Tehnică, București, 1954.

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

Vinogradov, I.M., Bazele teoriei numerelor, Editura Academiei, București 1953.

Minut Petru, Cristina Simirad, Numere prime. Numere prime speciale, Editura MATRIX ROM, 2005.

Năstasescu, C., Nița, C., Vraciu, C., Aritmetică și algebra, Editura didactică și pedagogică, București 1993.

Sierpinski, W., Ce știm și ce nu stim despre numere prime, Editura Știintifică, București 1996.