S,tefea Ionela Roxana [629572]

UNIVERSITATEA ,,AUREL VLAICU DIN ARAD
FACULTATEA DE S TIINT  E EXACTE
DOMENIUL: MATEMATIC A
PROGRAM DE STUDII: MATEMATIC A-INFORMATIC A
FORMA DE ^INVAT AM^ANT: ZI
LUCRARE DE LICENT  A
^INDRUM ATOR S TIINT  IFIC:
Lector dr. SIDA LaviniaABSOLVENT:
S,TEFEA IONELA ROXANA
ARAD
Iulie 2017

UNIVERSITATEA ;;AUREL VLAICU00DIN ARAD
FACULTATEA DE S TIINT  E EXACTE
SPECIALIZAREA MATEMATIC A-INFORMATIC A
LUCRARE DE LICENT  A
NUMERE FERMAT
^INDRUM ATOR S TIINT  IFIC:
Lector dr. Sida LaviniaABSOLVENT:
S,tefea Ionela Roxana
ARAD
Iulie 2017

Universitate ,,Aurel
Vlaicu din Arad
Aprobat
Facultatea de S tiint e
Exacte
Domeniul:
Matematic a
Program de studiu:
Matematic a-
Informatic a
Nr.. . . din.. . .Decan
Vizat
^Indrum ator  stiint ic
Date personale ale candidat: [anonimizat]
1.Date privind identitatea persoanei
Numele: S ,tefea
Numele anterior:{
Prenumele: Ionela Roxana
2.Sexul: F
3.Data  si locul na sterii: Ziua/luna/anul: 23/10/1995
Locul (localitate, judet ): Ineu, Arad
4.Prenumele p arint ilor:
Tata: Ioan Cornel
Mama: Jenica Marinela
5.Domiciliul permanent:
Judet ul Arad, Calea Romanilor, nr. 16, bl. B2-3, sc. B, et. 3, ap. 14
Telefon: [anonimizat]
E-mail: [anonimizat]
1

6.Sunt student a promot ia: iulie/2017
7.Forma de ^ nv at  am^ ant pe care am absolvit-o este:
cu frecvent  a, f ar a tax a.
8.Locul de munc a: {
9.Solicit ^ nscrierea la examenul de licent  a:
sesiune iulie, anul 2017
10.Lucrarea de licent  a pe care o sust in are urm atorul titlu:
Numere Fermat
11.^Indrum ator  stiint ic:
Lector dr. Lavinia SIDA
12. Ment ionez c a sust in examenul de licent  a pentru prima oar a  si declar
pe propria-mi r aspundere c a am luat la cuno stint  a de prevederile art.
143 din Legea 1/2011. Declar c a prezenta lucrare nu este realizat a prin
mijloace frauduloase, ind con stient a de faptul c a, dac a se dovede ste
contrariul, diploma prin fraud a ^ mi poate  anulat a, conform art. 146
din Legea 1/2011.
SEMN ATURA
2

Capitolul 1
Istoric
Din cele mai str avechi timpuri numerele au fost foarte importante pentru
oameni nu doar ca mijloace de a studia cantit at ,ile, ci s ,i ca "entitti".
Originile matematicii sunt legate de conceptele de num ar, m arime  si
form a . Studii mai moderne asupra unor animale au ar atat c a aceste con-
cepte nu sunt doar pentru specia uman a. Concepte de acest fel f aceau parte
din viat a de zi cu zi a societ at ilor preistorice care se ocupau cu v^ anatul  si
pescuitul.
Arheologii au g asit vestigii vechi ale num aratului, vestigii dat^ and cu
40.000 de ani ^ .Hr. ^In acele vremuri cifrele erau necunoscute oamenilor, preis-
toricii num arau cu ajutorul oaselor, bet elor sau cu ajutorul pietricelelor.
Cercetarile arheologice au scos la iveal a desene pe peret ii pe sterilor, de-
sene inf at i s^ and linii drepte si cercuri, aceste desene ind f acute de triburile
preistorice. Arheologii au mai descoperit "oase numerice" preistorice, vechi
de 30.000 de ani, dar primele documente matematice dateaz a cu 3000 de
ani ^ .Hr  si provin din Mesopotamia ind vorba despre t ablit e de argil a pe
care apar semne corespunz atoare cifrelor. Aceste t ablit e erau inscrpt ionate
^ n timp ce argila era moale, iar ulterior erau arse la soare sau ^ n cuptor. Ele
cont ineau tabele de multiplicare, fract ii, probleme de divizibilitate, ecuat ii
p atratice  si cubice, exercit ii de geometrie, calculul unor numere remarcabile,
etc.
^In perioada babilonian a se folosea sistemul numeric sexazecimal (adic a ^ n
baza 60), de aici provenind ^ mp art irea unui minut ^ n 60 de secunde  si a unei
ore ^ n 60 de minute.
Numerele 1,2,3,4,5,… din  sirul numerelor naturale se numesc cardinale  si
arat a din c^ ate unit at i se compune ecare. Cu ajutorul celor zece caractere:
0,1,2,3,4,5,6,7,8,9
3

Figura 1.1: Pitagora
putem scrie orice num ar, aceste caractere numindu-se cifre.
Omenirii i-au trebuit milenii ca s a ajung a la cifrele utilizate de noi ast azi.
Primele tentative au fost f acute de celebrul matematician PITAGORA
^ n secolul al VI-lea, ^I.Hr, pitagorienii introduc^ and not iunile de num ar prim,
num ar compus, numere relativ prime, numere perfecte, numere prietene, etc.
[3]
^In anul 610 dup a Hr., savantul indian ARYABATA a inventat cele nou a
cifre utilizate de noi ^ n prezent: 1,2,3,4,5,6,7,8,9, iar pentru cifra ZERO
folosea un punct (.). [4]
Matematicienii egipteni au scris texte matematice ^ n egiptean a, iar odat a
cu perioada elenistic a au ^ nceput s a apar a texte ^ n greac a. Egiptenii au
continuat s a studieze matematica sub Imperiul Arab, ca parte a matematicii
islamice, limba utilizat a ^ n matematic a de egipteni ind araba.
Semnele + (plus)  si – (minus) , care pentru noi par at^ at de banale  si
familiare, sunt rodul unor lungi discut ii ^ ntre savant i. Aceste semne dateaz a
din secolul al XV-lea, iar semnul = (egal) din secolul al XVI-lea. Matematica
a evoluat odat a cu necesit at ile  si descoperirile matematicienilor.
Cu trecerea timpului omenirea a evoluat  si odat a cu ea au evoluat  si
numerele.
4

Capitolul 2
Divizibilitatea numerelor
O important , a deosebit a ^ n matematic a o are divizibilitatea numerelor,
at^ at a numerelor naturale c^ at s ,i a numerelor ^ ntregi.
2.1 Relat ,ia de divizibilitate pe N
Dac a consider am dou a numere naturale a s ,i b, spunem c a a divide b s ,i
scriemajbdac a exist a un num ar natural castfel ^ nc^ at b=a
c, iar a este
divizor al lui b ^ n acest caz.
Orice num ar n>1 are cel put ,in doi divizori:pe el ^ nsus ,i si pe 1. Prin
divizor propriu al lui n ^ nt ,elegem un divizor diferit de num arul n, iar prin
divizor netrivial al lui n, un divizor diferit de n s ,i 1. Relat ,iajdenit a pe
Nse numes ,te relat ,ie de divizibilitate pe N. Se arat a us ,or c a aceasta este o
relat ,ie de ordine pe N.
Un num ar prim, prin denit ,ie este un num ar mai mare dec^ at 1 care nu
are alt ,i divizori ^ n afar a de el ^ nsus ,i s,i 1. Un num ar se numes ,te compus dac a
are cel put ,in un divizor netrivial.
Lema 2.1.1. Orice num ar natural, mai mare dec ^t 1, are un divizor prim.
Demonstrat ,ie.Demonstr am prin reducerea la absurd. Presupunem c a
exist a un num ar n>1 care nu are divizori primi. Not am mult ,imea acestor
numere cu S, iar cum ea este nevid a s ,iNeste bine ordonat a, rezult a c a exist a
un cel mai mic element in S. Fie aceasta n0,n0este un num ar compus, deci
n0=a
b, cu 1< a;bn0. Pentru a nu contrazice alegerea lui n0,a =2S,
adic aaare un divizor prim care va  divizor s ,i pentrun0, ceea ce contrazice
faptul c an02S.
5

Teorema 2.1.1. Dac a n este un num ar compus, atunci el are cel put ,in un
divizor prim mai mic sau egal cupn.
Demonstrat ,ie. Cum n este compus, e n=ab, cu 1< abn. Dac a
a >pn, atuncin=ab > n , fals. Deci, apn. Observ am din lema
anterioar a c a a are un divizor prim. Deci, n are un divizor prim mai mic sau
egal cupn.
2.1.1 Propriet at ,i ale divizibilit at ,ii numerelor naturale
8a2N, atunciaja, undea6= 0;
8a2N, atunciaj0, undea6= 0 s ,i 1ja;
8a;b2N, atunciaja
bs,ibja
b(produsul a 2 numere nturale este
divizibil cu ecare factor al produsului), unde a;b6= 0;
8a;b;c2N, dac aajbs,ibjc, atunciajc, undea;b6= 0;
8a;b;c2N, dac aajbs,iajc, atunciaj(bc), undea6= 0;
8a;b;c2N, dac aajb, atunciajc
a, undea6= 0.
Teorema 2.1.2. (Teorema ^ mpart ,irii cu rest)
Dac am;n2N,n6= 0atunci9q;r2Nastfel ^ nc^ at m=n
q+rs,ir<n .
^In plus q s ,i r sunt unice.
Demonstrat ,ie. Consider am mult ,imea
A=fs2Nj9k2N;m=nk+sg.
Dinm=n
0 +m,m2A. Mult ,imea A nu este vid a, deoarece cum N
este bine ordonat a exista r, cel mai mic element din A. Rezult a m=nq+r,
pentruq2N. R am^ ane s a ar at am c a r < n . Presupunem c a rn, atunci
r=n+u, pentruu2Ns,im=nq+r=nq+n+u=n(q+1)+u,u2A,dar
ru. Obt ,inemr=u, de unden= 0, fals. Deci, r < n . S ,i asa avem
armat ,ia de existent ,a din enunt ,ul teoremei demonstrat a.
Pentru a ar ata c a numerele q s ,i r sunt unice, presupunem m=nq+r=
np+sunder;s < n . Dac aq < p atuncip=q+u;u6=o. Obt ,inem
nq+r=n(q+u) +s=nq+ (nu+s), s,i avemr=nu+s, cumn6=os,i
u1, rezult anun. Atuncir=nu+sn+sn, astfel contrazice
faptul c ar<n . Avemp=qde unde rezult a imediat r=s.
C^ atul s ,i restul ^ mp art ,irii lui m s ,i n in enunt ,ul teoremei sunt numerele q s ,i r.
6

2.2 Relat ,ia de divizibilitate pe Z
^In mod asem an ator cazului numerelor naturale s ,i pentru cazul numerelor
^ ntregi se introduce relat ,ia de divizibilitate, adic a relat ,ia de divizibilitate pe
Z.
Fie numerele ^ ntregi a s ,i b, dac a exist a un ^ ntreg c astfel ^ nc^ at b=a
c
spunem c aajb. La fel ca s ,i ^ n cazul relat ,iei de divizibilitate denite pe N, ea
este tranzitiv a s ,i re
exiv a dar nu este simetric a. Lu am ca s ,i exemplu, 2j2
s,i2j2.
Denim relat ,ia numit a asociere^ n divizibilitate pentru a obt ,ine o relat ,ie
de echivalent , a peZprin :
zy,x=y.
2.2.1 Propriet at ,i ale divizibilit at ,ii numerelor ^ ntregi
Re
exivitatea: aja,8a2Z;
Tranzitivitatea: ajbs,ibjc)ajc,8a;b2Z;c2Z;
1ja;1ja,8a2Z;
aj0,8a2Z;
Dac aajbs,ibja)a=b,8a;b2Z;
Dac aajbsaubjc)ajb
c,8a2Z,8b;c2Z;
Dac aajb;a2Z,b2Z) jaj=jbj, adic a (a)jbsauaj(b) sau
(a)j(b);
Dac aajbs,iajc)ajb
r+c
s,8a2Zs,i8b;c;r;s2Z.
Denit ia 2.2.1. Fie a,b numere ^ ntregi. Spunem c a un num ar ^ ntreg d
este cel mai mare divizor comun al numerelor a,b dac a :
1.djas,idjb
2. Pentru orice d0jas,id0jb,rezult ad0jd.
Cel mai mare divizor comun a lui a s ,i b este unic determinat cu except ,ia
unei asocieri in divizibilitate, putem presupune c a acesta este un num ar nat-
ural. Un astfel de cel mai mare divizor comun este unic determinat s ,i ^ l
not amd= (a;b). Spunem c a numerele a s ,i b sunt prime ^ ntre ele sau relativ
prime dac a ( a;b) = 1.
7

Propozit ia 2.2.1. Fie a,b numere ^ ntregi s ,id= (a;b).
Atuncia=a0d,b=b0d, undea0; b0sunt numere ^ ntregi prime ^ ntre ele.
Din denit ,ia celui mai mare divizor comun d a dou a numere a, b rezult a
dj(ab) . Acest rezultat a fost folosit de c atre Euclid pentru a determina
cel mai mare divizor comun a doua numere naturale prin metoda scderii
repetate a num arului mic din cel mare.
Algoritmul funct ,ioneaz a dup a cum urmeaz a:
Fie numerele naturale a > b ,a1=a;b 1=b. Pentru ecare pereche ( ai;bi)
form am perechea ( ai+1;bi+1) unde
ai+1=maxfbi;aibig; b i+1=minfbi;aibig.
Acest proces se va opri form^ and numere din ce ^ n ce mai mici s ,i vom
obt,ineak=bk, concluzion am c a c:m:m:d:c: (a:b) =ak=bk. Deoarece
c:m:m:d:c (a1;b1) =c:m:m:d:c (a2;b2) =:::=c:m:m:d:c (ak;bk), algoritmul
funct ,ioneaz a corect.
De exemplu, alegem a= 34,b= 19. Se realizeaz a urm atoarele perechi:
(a1;b1) = (34;19)
(a2;b2) = (19;3419) = (19;15)
(a3;b3) = (15;1915) = (15;4)
(a4;b4) = (154;4) = (11;4)
(a5;b5) = (114;4) = (7;4)
(a6;b6) = (4;74) = (4;3)
(a7;b7) = (3;43) = (3;1)
(a8;b8) = (31;1) = (2;1)
(a9;b9) = (21;1) = (1;1)
obt,inem c.m.m.m.c(34 ;19)=c.m.m.d.c(1 ;1)=1.
Acest algoritm pentru a  mai rapid este ^ mbun at at ,it de obicei prin
^ nlocuirea sc aderilor repetate cu ^ mpart ,iri, pentru aceasta remintim teorema
^ mp art ,irii cu rest pentru numerele ^ ntregi:
Teorema 2.2.1. (Teorema ^ mp art ,irii cu rest) Fie a;b2Zcub6= 0, exist a
q;r2Zastfel ^ nc^ at a=bq+runde 0<jbj. Numerele qs,irsunt unic
determinate.
8

Demonstrat ,ie.Pentrua= 0, avem a=b
0 + 0 s ,i 0<jbj. Lu am
astfel,q= 0; r = 0. Dac a a > 0; b > 0, putem aplica teorema 2.1.2.
Dac aa > 0; b < 0 aplic am teorema 2.1.2 pentru as,ib. Rezult aa=
(b)q0+r0; q0; r02N, 0r0<b=jbj. Lu amq=q0s,ir=r0s,i
rezult aa=bq+rcu 0r<b=jbj.
Aplic am teorema pentru as,ibdac aa < 0; b > 0 s,i obt ,inema=
bq0+r0;0r0<b. Dac ar0= 0, atunci a=bq0s,i alegemq=q0; r = 0.
^In cazul 0<r0, avema=bq0r0=b(q01)+(br0). Alegemq=q01,
r=br0, cum 0<r0<b, obt ,inem 0<r<b =jbj. Aplic am aceeas ,i teorem a
pentru numerele naturale as,ibdac aa < 0;b < 0. Dac ar0=aalegem
q=q0s,ir= 0 s ,i avema=bq0+r0;0r0< b. Dac ar0>0, avem
a=bq0r0=b(q0+ 1) + (br0). Lu amq=q0+ 1;r=br0. Cum
0<r0<brezult a 0<r<b=jbj.
Demonstr am unicitatea numerelor qs,irastfel determinate. Presupunem
c abq+r=bq0+r0cu 0r; r0<jbj. Rezult ab(qq0) =r0r, deci avem
jbj
jqq0j=jrr0j. Cum r s ,ir0sunt numere naturale cu 0 r;r0<jbj
avemjrr0j<jbj. Astfel,jbj
jqq0j<jbjs,i undejqq0j<1.
Atunciq=q0s,ir=r0.
Lema 2.2.1. Fiea;b;q;r2Zastfel c aa=bq+r. Atunci, cel mai mare
divizor comun al lui as,ibexist a dac a s ,i numai dac a cel mai mare divizor
comun al lui bs,irexist a. ^In plus, avem (a;b) = (b;r).
Demonstrat ,ie.Presupunem c a exist a d= (a;b). Avemdjrrezultat din
djas,idjb. Dac abs,irau ped0ca divizor comun rezult a d0jbq+r, adic ad0ja.
Atunci,d0jds,id= (b;r). Se demonstreaz a la fel s ,i armat ,ia reciproc a.
Teorema 2.2.2. (Algoritmul lui Euclid) Pentru orice dou a numere ^ ntregi
exist a un cel mai mare divizor comun.
Demonstrat ,ie.Fie dou a numere ^ ntregi as,ib. Dac ab= 0 atunci ( a;b) =
a. Aplic am teorema 2 :1:2 dac ab6= 0. Exist a r22Zs,iq22Zastfel ^ nc^ at:
a=bq2+r2;0r2<jbj. (E1)
Va  tratat mai t^ arziu cazul c^ and un rest va  zero.
Exist aq32Z,r32Ndac ar26= 0, astfel ^ nc^ at:
b=r2q3+r3;0r3<r 2. (E2)
Exist aq42Z,r42Ndac ar36= 0, astfel ^ nc^ at:
r2=r3q4+r4;0r4<r 3. (E3)
Exist aqk+12Z,rk+12Ndac ark6= 0, astfel ^ nc^ at:
9

rk1=rk
qk+1+rk+1, 0rk+1<r k…
Observ am astfel c a resturile veric a relat ,iile:
jbj>r 2>r 3>:::>r k>r k+10.
Exist a un rang nastfel^ nc^ at rn+1= 0 dac a t ,inem cont c a mult ,imea numerelor
naturale este bine ordonat a.
Din lant ,ul de ^ mpart ,iri cu rest ultimile doua relat ,ii sunt:
rn2=rn1qn+rn(En1)
rn1=rn
qn1(En)
Avemrn= (rn;rn1) obt ,inut din relat ,ia (En).
Aplic^ and lema anterioar a obt ,inem:
rn= (rn;rn1) =:::= (r2;r3) = (b;r 2) = (a;b)
din relat ,iile (En1);:::; (Ek);:::; (E2);(E1). Not am a=r0s,ib=r1pentru
a uniformiza relat ,iile (E1);(E2);:::; (En). Relat ,iile din algoritmul lui Euclid
pot  scrise astfel:
rk1=rk
qk+1+rk+1;1kn;r n+1= 0. (Ek)
Privind relat ,iile (Ek) ale algoritmului lui Euclid, obt ,inem:
rk1
rk=qk+1+rk+1
rk,
qk+12Zs,i 0rk+1
rk<1.
Putem concluziona c a qk+1=
rk+1
rk
.
Algoritmul lui Euclid realizat prin ^ mp art ,iri nu este doar o metod a mai
rapid a, ea are o aplicabilitate mult mai larga dec^ at varianta sc aderilor suc-
cesive, aceast a variant a poate  folosit a ^ n inele euclidiene.
Aplicarea algoritmului pentru numere ^ ntregi se reduce la aplicarea al-
goritmului pentru numere naturale. Se alege cel mai mic dintre cele dou a
numere ^ n rolul lui b.
^In anumite situat ,ii din algoritmul lui Euclid poate  necesar s a cunoas ,tem
num arul de ^ mp art ,iri. Trebuie s a denim mai ^ nt^ ai s ,irul lui Fiboncci pentru
a putea da un r aspuns referitor la aceast a problem a.
Fie (fn)n1, s,irul denit prin f1=f2= 1 s ,ifn+1=fn+fn1, pentru
n3.
Se demonstreaz a us ,or folosind induct ,ia matematic a c a pentru orice n3,
10

fn>
1+p
5
2n2
.
Putem demonstra cu ajutorul acestui rezultat urm atoarea teorem a:
Teorema 2.2.3. (Lam e)Num arul de ^ mp art ,iri din algoritmul lui Eulclid
pentrua;b2Ncua>b nu dep as ,es,te de 5 ori num aul cifrelor din scrierea
^ n baza 10 a lui b.
Demonstrat ,ie.Pentru numerele as,ibconsider am algoritmul lui Euclid:
a=r0; b =r1; r k1=rk
qk+1+rk+1;1kn; r n+1= 0
^In cazul acesta qi1;2ins,iqn+ 12, pentru c a rn1=rn.
Observ am c a rn1 =f2s,irn
qn+12f2=f3.
Se arat a c a rnifi+ 2;0inprin induct ,ie matematic a, iar ^ n
particularb=r1fn+1>n1, unde=1+p
5
2.
Presupunem c a b^ n scrierea sa ^ n baza 10 are scifre, atunci b <10sde
unde obt ,inem c an1<10s. Prin urmare, ( n1) lg < s .^In nal avem
n5sdac a t ,inem cont de relat ,ia1
5<lg.
Consider am problema invers a. S a vedem dac a prin algoritmul lui Euclid
se pot determina numerele naturale as,ib, algoritmul aplicat acestora s a se
realizeze prin n^ mp art ,iri.
Teorema 2.2.4. Dac a (fn)n1este s ,irul lui Fibonacci, aplicarea algoritmului
lui Euclid pentru fn+2s,ifn+1necesit a exact n^ mp art ,iri.
Demonstrat ,ie.Obt ,inemfn+1> f 2, pentrun2 t,in^ and cont de modul
de denire al acestui s ,ir.
^In acest caz algoritmul lui Euclid este dat de relat ,iile:
fn+2=fn+1+fn, 0<f n<f n+1
fn+1=fn
1 +fn1, 0<f n1<f n…
f4=f3
1 +f2;0<f 2<f 3
f3=f2
2.
Se observ a c a sunt exact n^ mp art ,iri. Oricare doi termeni consecutivi
ai s,irului (fn+2;fn+1) =f2= 1 sunt relativi primi, pentru orice n.
(Algoritmul lui Euclid )
INPUT: dou a numere naturale a;bcuab.
OUTPUT: cel mai mare divizor comun pentru as,ib.
1. C^ at timp b6= 0;execut a:
(a)r amodb;a b;b r:
11

2. Returneaz a a.
Lema 2.2.2. Fiea; b2Z, armat ,iile urm atore sunt echivalente:
1.ajbs,ibja;
2.a=b.
Demonstrat ,ie.Din (1) rezult a (2). Din b=ac0s,ia=bc0s,i avem
a(cc01) = 0. Dac a a= 0, dinajbrezult ab= 0, decia=b. Dac aa6= 0,
dincc0= 1 rezult a c0=1. Este evident a reciproca, din (2)rezult a(1).
Not am cuDamult ,imea divizorilor (^ ntregi) ai lui a, pentru orice num ar
^ ntrega.^In condit ,iile precedente, dac a ajbs,ibjarezult a c aDa=Db, adic aas,i
bau aceleas ,i mult ,imi de divizori. ^In acest caz spunem c a as,ibsunt asociate in
divizibilitate. Relat ,ia de divizibilitate este asimetric a pe mult ,imea numerelor
naturale : ajb, s,ibja)a=b. Spunem c a doua numere sunt asociate ^ n
divizibilitate dac a s ,i numai dac a sunt egale.
Not am cuZmult ,imea multiplilor lui a, pentru orice num ar ^ ntreg a:
aZ=fn2Zajng
Rezult a din denit ,ie c a :aZ=fn2Zj9c2Z;n=acg=facjc2Zg.
Urmt ,oarea proprietate important a este a mult ,imii multiplilor lui a: dac a
b;c2aZatuncibm+cn2Z, oricare ar  m;n2Z.
^In particular c a 0 2aZs,ib; c2aZrezult abc2aZ. Se spune ^ n
algebr a c a aZeste un ideal al mult ,imiiZs,i aceasta ajut a sa d am denit ,ia
not,iunii de ideal.
12

Capitolul 3
Numere prime
Denit ,ie: Num arul ^ ntreg pse numes ,te indecompozabil sau num prim,
dac ap6= 0,p6=1 s,ipnu are alt ,i divizori ^ n afr a de 1 s,i pep.
Not am cuPmult ,imea numerelor naturale prime.
p1;p2;:::;p n2P
Observat ia 3.0.1. Num arulpeste prim dac a s ,i numai dac a p2Znf1g
s,i8a;b2Z,pja
b)pjasaupjb. Un num ar care nu este prim se numes ,te
num ar compus.
Observat ia 3.0.2. Num arul p este indecompozabil dac a s ,i numai dac a s ,i
num arulpeste indecompozabil.
Observat ia 3.0.3. Un num ar ^ ntreg difer a de zero s ,i de1care nu este
indecompozabil se numes ,te decompozabil.
Observat ia 3.0.4. Singurul num ar prim par este 2, el ind totodat a s ,i cel
mai mic num ar prim.
Exemple de numere prime:
2, 3, 5, 7, 11, 13, 17, 19, 23, :::
Propozit ia 3.0.1. Orice num ^ ntreg p,p>1are cel put ,in un divizor inde-
compozibil.
Teorema 3.0.1. (Teorema fundamental a a Aritmeticii-Euclid) Orice num ar
^ ntreg,a6= 0 s,ia6=1este un produs nit de numere indeompozabile.
Demonstrat ,ie.Demonstr am pentru numerele naturale n;n> 1, acest lucru
ind sucent. De aici rezult a faptul c a orice num ar ^ ntreg a;a6= 0 s ,ia6=1
se scrie ca un produs nit
13

a=q1q2::: q t
,
qisunt numerele naturale indecompozabile. Armat ,ia este adev arat a
dac aneste indecompozbil. Presupunem c a avem numere naturale n > 1,
numerele naturale nu se descompun ^ ntr-un produs nit de numere indecom-
pozabile, la aceste numere consider am mult ,imea M. Aceasta mult ,ime are un
cel mai mic element n,neste un num ar decompozabil, avem n=n1n2s,i
1< n 1< n, 1< n 2< n. Prin urmare n1=2M;n 2=2M. Se descompun ^ n
produse nite de numere indecompozabile n1s,in2
n1=q11q12:::q 1r; n 2=q21q22:::q 2s
.
Se descompune ca un produs nit de numere indecompozabile
n1=q11q12:::q 1r; n 2=q21q22:::q 2s.
Observat ia 3.0.5. Dac an2N, presupunem c a neste decompozabil dac a s ,i
numai dac a admite cel put ,in un divizor, adic a 9djncu1<d<n .
Teorema 3.0.2. (Teorema fundamental a a Aritmeticii-Gauss) Descompunerea
unui num ar ^ ntreg n,n6= 0 s,in6=1, ca produs nit de numere indecom-
pozabile ^ nmult ,it cu1este unic a, mai put ,in ordinea factorilor.
La aceast a teorem a vom da doua demonstrat ,ii, pentru prima dat a teo-
rema a fost formulat a s ,i demonstrat a de Gauss ^ n celebrul s au tratat "Disqui-
sitiones Arithmeticae"(1801). Prima demonstrat ,ie:Putem s a ne limit am la
numere naturale mai mari ca 1. Presupunem c a numerele naturale n;n> 1
admit descompuneri distincte ca produs de numere indecompozabile. Fie
a, cel mai mic element al mult ,imii M, mult ,imea M ind mult ,imea acestor
numere. Avem
a=p1p2::: p r=q1q2::: q s;
undeqis,iqssunt indecompozabile. Remarc am c a oricare este i= 1; ::: r
s,i oricare este j= 1; ::: s; p 16=q1.^In cazul ^ n care exist a egalitate se
contrazice alegerea lui aprin ^ mp art ,irea cupi=qi. Presupunem c a avem
p1p2:::prs,iq1q2:::q s. Pentru c a p16=q1putem presupune
c api< q j. Lu am num arul b=p1q2:::q s, se poate observa c a b < a , deci
ab1 s,ip1jab1. Dinp1jab)ab >1. Deoarece avem c a
ab>1 s,ip1jab, aplic^ and teorema fundamental a a Aritmeticii (Euclid)
rezult a c aabare descompunerea
14

ab=p1l1:::l t:
Mai avem s ,i egalitatea ab= (q1p1)q2:::q s. Dac aq1p1>1, aplic^ and
teorema fundamental a a Aritmeticii (Euclid), obt ,inem descompunerea
q1p1=k1:::k v;
unde nici unul din k1; k2; :::k vnu estep1, c acip1nu divideq1p1. Avem
pentruabse obt ,ine descompunerea
ab=k1:::k vq2:::q s:
Descompunerile ab=p1l1:::l ts,iab=k1:::k vq2:::q ssunt diferite
c aci ^ nab=p1l1:::l taparep1, iar ^ nab=k1:::k vq2:::q snu apare
p1. Se contrazice alegerea lui adeoareceab<a s,i are dou a descompuneri
distincte.
A doua demonstrat ,ie a teoremei anterioare. Fie num arul ^ ntreg a>1
s,i e descompunerile sale
a=p1p2:::p r=q1q2:::q s
undepis,iqjsunt numere indecompozabile. Din faptul c a p1divide pe
q1q2:::q ss,ip1este prim rezult a c a exist a j12 f1;2;:::;sgastfel ^ nc^ at
p1=qj1. Pentru c a qj1este ireductibil rezult a c a p1=qj1. Simplic am cu
p1=qj1s,i rezult ap1:::p r=q1:::q j11qj1+1:::q s:
^In mod similar, avem j26=j1astfel ^ nc^ at p2=qj1s,i as ,a mai de-
parte. Nu putem avea r<s saur>s pentru c a dac a simplic am la ecare
pas c^ ate un num ar indecompozabil obt ,inem c a 1 este un produs de numere
indecompozabile. Cele dou a descompuneri au acelas ,i num ar de factori inde-
compozabili care coincid, fac^ and abstract ,ie de ordinea lor ^ n produs.
Se foloses ,te prin tradit ,ie termenul de num ar prim deoarece not ,iunile de
num ar indecompozabil s ,i num ar prim nenul coincid.
Lema 3.0.1. Orice num ar prim nenul este indecompozabil.
Demonstrat ,ie.Avem c ap > 0 s,i c ap=ab, undea < p; b < p . Din
proprietatea clar a pjabse obt ,ine c apdivide peasaupdivide pea. Pre-
supunem c a pdivide pea. Pentru c a avem s ,iajp, rezult a c a p=a. Am
obt,inut o contradict ,ie.^In demonstrat ,ia acestei leme nu am folosit teorema
fundamental a a Aritmeticii (Gauss).
Teorema 3.0.3. Orice num ar ^ ntreg indecompozabil este num ar prim.
Demonstrat ,ie.Fiea;b2Zs,ip > 1, un num ar indecompozabil astfel
^ nc^ atpjab. Fieab=pc, putem presupune c a a > 1 s,ib > 1. Lu am ^ n
15

considerare descompunerile ^ n produse nite de numere indecompozabile:
a=p1:::p r;b=q1:::q s;c=k1:::k l. Din egalitatea:
pk1:::k l=p1:::p rq1:::q s;
aplic^ and teorema fundamental a a Aritmeticii (Gauss), rezult a c a p=pi
saup=qj. Deci avem c a pjasaupjb.
Teorema 3.0.4. (Teorema ^ mp art ,irii cu rest) Oricare ar  numerele ^ ntregi
as,ib,b6= 0, exist a numerele unice qs,irastfel ^ nc^ at:
1.a=bq+r;
2.0r<jbj.
Demonstrat ,ie.La aceast a teorem a vom avea mai multe cazuri. Un caz
important este a0 s,ib>0. Vom xa pe bs,i vom demonstra prin induct ,ie
c a oricare ar  a2N, exist a numerele naturale qs,ircare veric a (1) s ,i (2).
Avem:
M=fa2Nj9q;rastfel ^ nc^ at a=bq+rs,i 0r<bg.
Este evident c a 0 2M, c aci 0 = 0
b+ 0. Spunem c a a2M, adic a
a=bq+r;0r<b . Avem:
a+ 1 =bq+r+ 1.
Dac a avem r+ 1< b, rezult a c a a+ 12M. Avema+ 12Ms,i dac a
r+ 1 =b, putem scrie a+ 1 =b(q+ 1) + 0.
Cazul al doilea :a < 0,b > 0. Aplic am cazul anterior lui as,ib,
obt,inema= (b)q+rcu 0r <jbj. Scriem egalitatea precedent a sub
formaa=b(q) +r, rezult a demonstrat ,ia.
Cazul al treilea :a >0; b < 0. Din primul caz avem a=bq+rcu
0r < b . Dac ar= 0, ^ nmult ,im egalitatea precedent a cu 1 s,i obt ,inem
a=b(q) + 0. Dac a 0 < r < b , ^ nmult ,im egalitatea precedent a cu 1 s,i o
scriem sub forma:
a=b(q1) + (b+r),
unde 0<br<b .
Cazul al patrulea :a <0; b < 0. Se procedeaz a ca la cazul precedent.
S a demonstr am unicitatea lui qs,ir; e scrierile a=bq+rs,ia=bq0+r0cu
0r <jbj;0r0<jbj. Presupunem c a r < r0; prin sc aderea celor dou a
egalit at ,i rezult ab(qq0) =r0r, unde 0< r0r <jbjrjbj. Dar din
egalitatea precedent a s ,iqq06= 0 rezult ajb(qq0)j=jbjjqq0jjbj. Am
obt,inut o contradict ,ie. Decir=r0s,i atunci avem imediat q=q0.
16

3.1 Teoreme privind innitatea numerelor prime
Teorema 3.1.1. (Euclid) Mult ,imea numerelor naturale prime este innit a.
Amintim aici dou a dintre demonstrat ,iile acestei cunoscute teoreme.
Prima demonstrat ,ie.demonstrt ,ie dat a de Euclid
Fiep1; p2; :::; p n. Consider am num arul N=p1; p2; :::; p n+ 1. N ad-
mite un divizor prim qconform propozit ,iei 3.0.1. Deoarece unul din numerele
picoincide cu q, dinpijNrezult apij1, am obt ,inut o contradict ,ie.
A doua demonstrat ,ie.Sucent este s a ar at am c a pentru orice num ar nat-
uralnexist a un num ar prim p; p>n . Alegem un divizor prim al num arului
N=n!1 pentru a demonstra.
Teorema 3.1.2. (Dirichlet) ^In progresia aritmetic a
a;a+q;a+ 2q;a+ 3q;:::;a +nq;:::;
cua;q> 0, numere naturale prime ^ ntre ele exist a o innitate de numere
prime.
Teorema 3.1.3. (Postulatul lui Bertrand) Oricare ar  num arul natural
n>1exist a un num ar prim pcuprins ^ ntre ns,i2n, adic a
n<p< 2n:
Observat ia 3.1.1. Cel mai mare num ar prim g asit p^ an a ^ n prezent are peste
22 de milioane de cifre s ,i estep= 2742072811. O problem a deschis a privind
numerele prime este" Conjectura lui Andrica" s ,i anume:
Diferent ,a radicalilor a dou a numere prime comsecutive este ^ ntotdeauna mai
mic a dec^ at 1.
Teorema 3.1.4. Orice num ar prim p5are forma 6k+ 1sau6k+ 5.
Demonstrat ,ie.Orice num natural are una din formele 6 k;6k+ 1;6k+
2;6k+ 3;6k+ 4 sau 6k+ 5. Putem observa c a 6 k, 6k+ 2, 6k+ 4 se divid cu
2, deci sunt numere prime. Deasemenea 6 k+ 3 se divide cu 3. Cum pentru
6k+ 1 s ,i 6k+ 5 nu putem preciza nici un divizor propriu r am^ ane c a aceastea
sunt formele posibile pentru numere prime.
Observat ia 3.1.2. Nu putem trage concluzia din teorema anterioar a c a un
num ar de forma 6k+ 1 sau6k+ 5 este num ar prim. Putem arma doar
faptul c a un num ar despre care s ,tiu deja c a este prim are una din formele
acestea.
17

Teorema 3.1.5. Dac a un num ar prim p divide un p atrat perfect N, atunci
p2^ l divide pe N.
Demonstrat ,ie.Dac a ^ l avem pe N p atrat perfect, atunci N=A2. Fie
A=p1
p2
:::
pkdescompunerea ^ n factori a lui A. Atunci avem N=
p2
1
p2
2
:::
p2
k.
Deci p este unul dintre factorii p1
p2
:::
pkdeoarece p divide N. Cum pi
apare la puterea a doua, rezult a c a p2divide pe N.
Teorema 3.1.6. Dac a un num ar prim p divide un cub perfect N, atunci p3
^ l divide pe N.
Demonstrat ,ie.Putem demonstra la fel ca la teorema anterioar a.
3.1.1 Cum putem obt ,ine numere prime?
Pentru c a mult ,imeaPa numerelor naturale prime este innit a observ am
c a ele formeaz a un s ,ir innit, dac a le scriem in ordine credc atoare obt ,inem
s,irul:
2;3;5;7; :::; p n; :::;
undepneste al n-lea num ar prim. Matematicienii au pus ^ n leg atur a cu pro-
priet at ,ile acestui s ,ir numeroase probleme extrem de interesante, de-a lungul
timpului. Unele dintre acestea sunt nerezolvate p^ an a ^ n prezent. Trecem ^ n
revist a c^ ateva probleme cu caracter elementar privind s ,irul (pn)n1.
Este dicil s a decidem dac a num arul natural neste prim sau nu pentru
c a este destul de mare. Din cele mai vechi timpuri matematicienii au ^ ncercat
s a construiasc a numere prime mari.
Pentru orice n0, Fermat a presupus c a numerele fn= 22n+ 1 sunt
prime.
3.2 Ciurul lui Eratostene
Acesta a ap arut^ n jurul anului 240^ .e.n s ,i este cel mai vechi test de primali-
tate cunoscut. Pentru orice numere prime Ciurul lui Eratostene funct ,ioneaz a
corect. Consider am un num ar n, pentru a testa dac a este prim ^ ntocmim o
list a cu toate numerele naturale pronind de la 2 p^ an a la n. Din ea se ^ nl atur a
toate numerele care sunt multimplii de numere prime mai mici sau egale cupn. Cele care r am^ an ^ n list a sunt toate numere prime.
Exemplu. Pentru a g asi numerele prime impare mai mici dec^ at 100,
scriem ^ nt^ ai numerele impare de la 3 la 100. Primul num ar din list a este 3,
18

astfel el este primul num ar impar prim. ^Inl atur am din s ,ir toti multiplii de 3
s,i primul num ar r amas este 5, care este prin urmare prim. Pentru el aplc am
acelas ,i procedeu. Cum 11 >p
100, mai r am^ ane s a aplic am procedeul doar
pentru 7. Toate numerele sunt prime care au r amas ^ n list a.
3.2.1 Algoritm pentru determinare numerelor prime
cu ajutorul ciurului lui Eratostene
1. Se scrie o list a a numerelor de la 2 la cel mai mare num ar ce urmeaz a
a  testat pentru primalitate. Numim aceast a list a lista A.
2. Se trece num arul 2, primul num ar prim g asit, ^ ntr-o alt a list a, cea a
numerelor prime g asite. Numim aceast a list a lista B.
3. Se marcheaz a 2 s ,i tot ,i multiplii lui 2 din lista A.
4. Primul num ar nemarcat din list a este un num ar prim. Se trece acest
num ar n lista B.
5. Se marcheaz a acest num ar s ,i tot ,i multiplii lui din lista A. Marcarea de
multipli poate s a ^ nceap a de la p astratul num arului, ^ ntruc^ at multiplii
mai mici au fost deja marcat ,i n pas ,ii anteriori.
6. Se repet a pas ,ii 4 s ,i 5 p^ an a c^ and se epuizeaz a toate numerele din lista
A.
^In urm atoarele imagini avem reprezentat Ciurul lui Eratostene: 3.1 s ,i 3.2.
Ciurul lui Eratostene este un algoritm clasic folosit s ,i ^ n limbajul de pro-
gramare Java (3.3).
19

Figura 3.1: Ciurul lui Eratostene
Figura 3.2: Ciurul lui Eratostene
20

Figura 3.3: Ciurul lui Eratostene ^ n Java
21

Capitolul 4
Numere Fermat
Matematicianul francez Pierre de Fermat (1601 1665) a fost probabil cel
mai mare matematician amator din istorie chiar dac a era de profesie avocat.
Numerele care-i poart a numele, numerele Fermat , au fost studiate pentru
prima dat a de c atre el. El a corespondat cu mai mult ,i matematicieni contem-
porani, ^ ns a nu a publicat nimic din descoperirile sale. Fiul s au a g asit toate
notit ,ele sale s ,i le-a publicat dupa moartea sa. Unul dintre matematicienii
contemporani cu care Pirre de Fermat a corespondat a fost matematicianul
francez Mersenne (1588 1648). Datorit a rezultatelor importante obt ,inute
de Fermat ^ n teoria numerelor se consider a c a el a pus de fapt bazele teoriei
moderne a numerelor.
Denit ia 4.0.1. Numerele Fermat sunt numere ^ ntregi pozitive care au urm atoarea
form a:
Fn= 22n+ 1,n>0.
Dac a un num ar Fermat este prim, atunci el se numes ,te num ar Fermat
prim.
P^ an a ^ n prezent se cunosc ca ind prime doar primele cinci dintre nu-
merele Fermat:
F0= 3,F1= 5,F2= 17,F3= 257,F4= 65537 f ar a a putea preciza dac a
exist a o innitate de numere prime Fermat.
De exemplu, primele c^ ateva numere Fermat sunt: 3,5,17,257,65537,
4294967297,18446744073709551617,. . . .
22

4.1 Propriet at ,i ale numerelor Fermat
Fermat a armat faptul c a toate numerele Fermat sunt prime (Conjectura
lui Fermat). ^Intr-adev ar primele cinci numere Fermat F0,F1,F2,F3s,iF4
sunt prime dar Leonard Euler a ar atat ^ n 1732 c a F5este compus, num arul
ind divizibil cu 641.
Demonstrat ,ia nu are foare multe calcule s ,i se bazeaz a pe relat ,ile:
641 = 5
27+ 1 = 24+ 54.
Astfel,
F5= 225+ 1 =
= 232+ 1 =
= 24
228+ 1 =
= (64154)228+ 1 =
= 641
228(5
27)4+ 1 =
= 641
6700417 =
= 4294967297.
^In 1770 tot Euler a ar atat c a orice divizor al lui Fntrebuie s a e de forma
2n+1
k+ 1 cuk0. Acest rezultat a fost inbun at at ,it de c atre matemati-
cianul francez Lucas (1842-1891) prin urm atoarea teorem a:
Teorema 4.1.1. Orice divizor prim al lui Fn, dac a exist a, este de forma:
2n+2
k+ 1.
Spre exemplu, pentru F3= 257 se caut a divizorii primi mai mici sau
egalip
257 = 16;:::de forma 25k+1 = 32k+1.F3este prim pentru c a astfel
de factori nu exist a. Pentru F6divizorii primi c autati ar  e forma
28k+ 1 = 265k+ 1pF6. Dup a mai multe calcule se obt ,inek= 1071, s ,i
astfel, 274177jF6.
Propozit ia 4.1.1. Dac a 2n+ 1 este num ar prim s ,i n este num ar natural,
nenegativ, atunci n este o putere a lui 2.
Demonstrat ,ie:Presupunem c a n= 2kmcuk2Ns,imnum ar par. Deci,
2n+ 1 = (22k)m+1= (22k+ 1)[(22k)m1(22k)m2+:::+ 1]:
Cum 2n+ 1 este prim, rezult a c a 22k+ 1 = 1, ceea ce este posibil, sau
22k+ 1 = 2n+ 1 de unde n= 2 .
Urm atoarea lem a st a la baza unei propiet at ,i importante a numerelor Fer-
mat.
23

Lema 4.1.1. Numerele Fermat veric a relat ,ile de recurent , a:
pentrun2:
F0F1F2:::F n1=Fn2,
Fn=F2
n12(Fn21)2,
Fn= (Fn11)2+ 1.
pentrun1:
Fn= (Fn11)2+ 1:
Fiecare dintre aceste relat ,ii pot  demonstrate prin induct ,ie.
Propozit ia 4.1.2. Pentrun;m2N, distincte, numerele Fermat Fms,iFn
sunt prime intre ele.
Demonstrat ,ie: Putem presupune n mai mare ca m.
Din lema anterioar a, F0F1:::F m:::F n1=Fn2.
Fied= (Fn;Fm). CumdnFns,idnF0F1:::F n1, obt ,iem c adn1. Toate
numere Fermat sunt impare de unde rezult a d= 1.
Fiecare numar Fermat va avea un factor prim pentru ca este >1. Fiepn
un divizor prim al lui Fn, cun2N. Dar, (Fn;Fm) = 1, pentru m6=n.
Observ am astfel c a divizorii pns,ipmsunt diferit ,i. Cum mult ,imea divizorilor
pneste innit a exist a o innitate de numere prime.
Propozit ia 4.1.3. Ultima cifr a a orc arui num ar Fermat cu except ,ia luiF0
s,iF1, este ^ ntotdeauna 7.
Teorema 4.1.2. Un num ar prim Fermat nu poate  un num ar prim Wieferich(un
num ar prim Wieferich e un num ar prim p astfel ^ nc^ at p2s a divid a num arul
2p11).
Propozit ia 4.1.4. Un num ar Fermat nu poate  num ar perfect(num ar egal
cu suma tuturor divizorilor s ai).
Propozit ia 4.1.5. Un num ar Fermat nu poate face parte dintr-o pereche de
numere amiabile (sau prietene)(numerele prietene sunt dac a exist a numere
diferite ^ n care ecare dintre ele este egal cu suma divizorilor celuilalt num ar).
Teorema 4.1.3. Dac a num arul nn+ 1 este prim, atunci exist a un num ar
^ ntreg m, astfel ^ nc^ at
24

n= 22m
^In acest caz are loc ecuat ,ia:
nn+ 1 =F2m+1
Teorema 4.1.4. Dac a not am cu P(Fn)cel mai mare factor prim al unui
num ar Fermat Fn, are loc
P(Fn)2n+2(4n+ 9) + 1:
4.1.1 Problema factoriz arii. Metoda Fermat
Descompunerea^ n factori primi a numerelor Fermat este foarte dicil a, t ,in^ and
cont de dimensiunea lor mare. De fapt s-au factorizat complet doar numerele
de laF5p^ an a laF11.
^In 1880, Landrry a factorizat F6, metoda folosit a neind publicat a. F6
a fost factorizat prin metoda fract ,iilor continue ^ n 1975 de c atre Morrison s ,i
Brillhart. ^In 1981 pentru F8Brent s ,i Pollard au folosit o versiune a testului
rho. Cu ajutorul metoei curbelor eliptice ^ n 1988, Brent a factorizat F11.F12
are 5 fctori primi cunoscut ,i, r am^ an^ and un factor compus necunoscut de 1187
cifre. Pentru F13situat ,ia este asem an atoare s ,tiinu-se 4 factori primi iar cel
compus r am^ ane de stuiat, are 2391 cifre. F14este un num ar compus chiar
dac a nu se cunoas ,te factorizarea lui.
Prin rezultatul dat de Galonis ^ n 1801 numerele Fermat ^ s ,i g asesc
important ,a^ n geometrie. Acesta a stabilit un poligon regulat cu nlaturi, este
construit cu rigla s ,i compasul dac a s ,i numai dac a n= 2kp1p2:::p r;unde k2
Ns,ip1;:::p rsunt numere prime Fermat distincte.
Aceste numere prezint a interes de asemenea s ,i ^ n teori corpurilor nite.
Astfel dac a consider am un corp K de orin 22n, grupul multiplicativ Keste o
sum a direct a de n ciclice ale c aror ordine sunt egale cu F0;F1;:::F n1. Folosim
acest rezultat pentru a determina ordinul unui element din Ks,i este este
necesar s a cunoas ,tem descompunerea ^ n factori primi a numerelor Fermat.
^In cazul ^ n care n are doi factori de marime similar a este recomandat a metoda
Fermat , de obicei. Se caut a ^ ntregii x, y astfel ^ nc^ at n=x2y2, pentru un
num ar natural n. Atunci n= (xy)(x+y) s,i se obt ,ine o prim a descom-
punere a lui n, ^ n care un factor este foarte mic. La baza acestui rezultat st a
urm atoarea propozit ,ie:
Propozit ia 4.1.6. Fie n num ar natural impar. Exist a o coresponent , a bijec-
tiv a ^ ntre descompunerile lui nde forman=abcuab>0s,i reprezent arile
lui n de forma n=x2y2unde x, y sunt numere naturale. Corespundent ,a
este dat a de relat ,iile:
25

x=a+b
2,y=ab
2,a=x+y; b =xy
Dac a avem n=ab, cu a s ,i b de valori apropiate, y va  un num ar mic iar x
put,in mai mare dec^ atpn.^In acest caz c aut am, p atratele perfecte de forma
x2n, pornind cu x1= [pn+ 1]. Test am dac a x2
1neste p atrat perfect.
Multe cazuri pot  eliminate cum exist a doar 22 de combinat ,ii pentru ultimile
dou a cifre ale unui num ar p atrat perfect.
Alegemx2=x1= 1 s ,i refacem rat ,onamentul dac a x2
1nnu este
p atrt perfect. Procesul se opres ,te pentru c a descompunerea trival a n=n
1
conduce la n= (n+1
2)2- (n+1
2)2.
S a apilc am metoda pentru n= 4429.
Din 66<p
4429<67, pornim cu x1= 67. Obt ,inem:
x1= 67, 672n= 60 – nu este p atrat perfect,
x2= 68, 682n= 195 – nu este p atrat perfect,
x3= 69, 692n= 332 – nu este p atrat perfect,
x4= 70, 702n= 471 – nu este p atrat perfect,
x5= 71, 712n= 612 – nu este p atrat perfect,
x6= 72, 722n= 755 – nu este p atrat perfect,
x7= 73, 732n= 900 – este p atrat perfect.
Deci avem, 4429 = (73 30)(73 + 30) = 43
103. Relu am procesul pentru
factorii g asit ,i, aces ,tia sunt primii la noi.
Dac a cei doi factori a s ,i b nu au valori apropiate aceast a factorizare poate
 inecent a. Pentru a testa dac a numerele generate sunt p atrate perfecte
este posibil s a e necesaren+1
2pnverc ari.
Se poate folosi o metod a Fermat generlizat a ^ n acest a situat ,ie care
act,ionez a mai bine in astfel de cazuri. Pentru aceasta, se alege un num ar mic
k s,i x va lua succesiv valorile [p
kn+1];[p
kn+2];::::C^ andx2kneste p atrat
perfect ne vom opri. Presupunem x2kn=y2. Num aruld= (x+y;n) este
un divizor propriu al lui n din:
(x+y)(xy) =kn
Folosind metoda Fermat generalizat a, alegem k= 3 ca s a factoriz am mai
us,orn= 68987:Atunci 454 <p
3n<455. Obt ,inem: 45523
68987 = 64,
adic a 3n= 455282. Calcul^ and (455 + 8 ;68987) = 463, rezult a 68987 =
463
149.
Algoritm (Metoda Fermat generalizat a)
INPUT: un num ar n, i,par compus s ,i k, factor de apropiere.
OUTPUT: doi factori a, b cu n=ab.
26

1.N [p
kn],i 1,t 0.
2. C^ at timp iNs,it= 0, efectueaz a:
(a)y p
(N+i)2kn.
(b) Dac ay= [y], atuncix N+i,t 1.
(c)i i+ 1.
3. Dac at= 1, atunci returneaz a a= (x+y;n);b=nnas,i se opres ,te.
4. Returneaz a mesaj de es ,ec.
Factorizarea primelor 12 numere Fermat, F0; F1; :::; F 11:
F0= 21+ 1 = 3{num ar prim
F1= 22+ 1 = 5{num ar prim
F2= 24+ 1 = 17{num ar prim
F3= 28+ 1 = 257{num ar prim
F4= 216+ 1 = 65;537{ cel mai mare num ar Fermat prim cunoscut
F5= 232+ 1 = 4;294;967;297
= 6416700417(factorizat ^ n 1732)
F6= 264+ 1 = 18;446;744;073;709;551;617 (20 de cifre)
= 274;17767;280;421;310;721 (14 cifre) (fctorizat ^ n 1855)
F7= 2128+1 = 340;282;366;920;938;463;463;374;607;431;768;211;457
(39 de cifre)
= 59;649;589;127;497;2175;704;689;200;685;129;054;721(factorizat
^ n 1970)
= 115;792;089;237;316;195;423;570;985;008;687;907;853;269;984;665;640;564;039;457;
584;007;913;12
F8= 2256+ 1 = 9;639;937 (78 de cifre)
= 1;238;926;361;552;89793;461;639;715;357;977;769;163;558;199;606;896;584;051;
237;541;638;188;580;280;321(factorizat ^ n 1980)
= 13;407;807;929;942;597;099;574;024;998;205;846;127;479;365;820;592;393;377;723;
561;443;721;764;0
27

F9= 2512+1 = 30;073;546;976;801;874;298;166;903;427;690;031;858;186;486;050;853;
753;882;811;946;569;946;433;649;006;084;097 (155 de cifre)
= 2;424;8337;455;602;825;647;884;208;337;395;736;200;454;918;783;366;342;
657741;640;062;627;530;801;524;787;141;901;937;474;059;940;781;097;519;023;905;
821;316;144;415;759;504;705;008;092;818;711;693;940;737(factorizat^ n 1990)
F10= 24102+1 = 179;769;313;486;231;590;772;930:::304;835;356;329;624;224;137;217
(309 de cifre)
= 45;592;5776;487;031;8094;659;775;785;220;018;543;264;560;743;076;778;192;
897130;439;874;405;488;189;727;484:::806;217;820;753;127;014;424;577(factorizat
1995)
F11= 28204+1 = 32;317;006;071;311;007;300;714;8:::193;555;853;611;059;596;230;657
(617 de cifre)
= 319;489974;849167;988;556;341;760;475;1373;560;841;906;445;833;920;
513173;462;447;179;147;555;430;258:::491;382;441;723;306;598;834;177
(factorizat ^ n 1988 LINK)????????
4.2 Congruent ,e speciale. Mica teorem a a lui
Fermat
Mica teorem a a lui Fermat constituie o parte fundamental a a teoriei nu-
merelor. Ea apare pentru prima datin anul 1640 intr-o scrisoare a lui Fermat
adresat a unui amic al s au. Prima demonstrat ,ie a acestei celebre teoreme a
fost dat a de c atre matematicianul Wilhelm Leibniz ^ n anul 1683.
Teorema 4.2.1. Fiep2, num ar prim. Atunci,
ap11(mod p),
pentru orice num ar ^ ntreg a prim cu p. Atfel spus ap11…p.
Demonstrat ,ie.Consider am numerele ^ ntregi a;2a;:::; (p1)a. Observ am
c ap-kapentru 1kp1. Pentruj6=k,ja6=ka(mod p). Deci,
a;2a;:::; (p1)areprezint a un sistem complet de resturi modulo p din care
a fost exclus 0. Astfel, a
2a
:::
(p1)a1
2
:::
(p1)(mod p). De
aici,ap1(p1)!(p1)!(mod p). Cum (( p1)!;p) = 1, rezult a ^ n nal
ap11(mod p).
O alt a variant a a acestei teoreme este urm atoarea:
Teorema 4.2.2. Pentrup2, num ar prim s ,i pentru orice a, num ar ^ ntreg,
(poate  chiar muliplu al lui p) are loc relat ,ia:
28

apa(mod p ).
Demonstrat ,ie.Dac ap-a, din mica teorem a a lui Fermat, rezult a c a
ap11(mod p), unde apa(mod p). Dac a pja, tunciapa0 (mod
p).
O prim a aplicat ,ie a micii teoreme a lui Fermat const a ^ n determinarea
unor resturi modulo p pentru puteri. De exemplu, folosind teorema putem
calcula restul lui 8110modulo 13 s ,i obt ,inem c a 8110= (812)9
8264
12(mod 13).
Reciproca micii teoreme a lui Fermat nu este adev arat a. Dac a ap1
1(mod p ) atunci nu rezult a c a p este num ar prim, putem aminti totus ,i aici
o teorem a similar a care este adev art a s ,i anume:
Teorema 4.2.3. Dac a a este un oarecare s ,i are loc
ap11(mod p )
,
pentru orice num ar q prim, cu qjp1s,iap1
21(mod p), atunci
num arul p este prim.
29

Bibliograe
[1] Cira, Octavian and Smarandache, Florentin, Various Arithmetic Func-
tions and their Applications, 2016
[2] http://ro.math.wikia.com/wiki/Pitagora
[3] http://www.icstm.ro/DOCS/josa/josa 2008 1/a.04 CESTIM DAR MAI ALES CENUSTIM DESPRE NUMERE.pdf
[4] http://www.infoarena.ro/ciurul-lui-eratostene
[5] http://www.matestn.ro/mate/PhotoMate/Divizibilitate
%20si%20nr%20prime/DivizibilitateSiNrPrime.pdf
[6] https://en.wikipedia.org/wiki/Fermat number
[7] http://recreatiimatematice.ro/arhiva/complementare/RM22002CRACIUN.pdf
[8] https://ro.wikipedia.org/wiki/Euclid
[9] http://math.ucv.ro/ dan/courses/carte Alg.pdf
[10] https://ro.wikibooks.org/wiki/Divizibilitatea numerelor naturale
[11] http://www.viitoriolimpici.ro/uploads/attach data/100/26/31//3e02c06.pdf
30