teoreme_celebre_de_teoria_numerelor.pdf

7/26/2019 teoreme_celebre_de_teoria_numerelor.pdf

1/90

Autor Prof. Voinea Axinte Costica

- BOTOSANI 2006 -


2/90

Autor Prof. Voinea-Axinte Costica 2

Introducere

Evocarea nceputurilor aritmetice este impresionant i educativ pentru oricine,deoarece arat ct de lung a fost calea care a condus de la rboj la teoria analitic anumerelor.

coala lui Pitagora a elaborat teoria numerelor pare i impare, a rapoartelor, pebaze geometrice. Euclid, cunoscut ndeobte ca geometru, consacr ns crile VII, VIIIi IX din Elemente teoriei numerelor ntregi. Manualele colare cuprind i astziteorema mpririi cu rest, algoritmul lui Euclid care conduce la cel mai mare divizorcomun a dou numere naturale, teorema fundamental a aritmeticii privind existena iunicitatea descompunerii n factori primi a unui numr natural i teorema de existen aunui numr infinit de numere prime.

Euclid este cel care fundamenteaz aritmetica i teoria numerelor reale, dar ilipsete axioma lui Arhimede, aa nct coninutul aritmetic ateapt secolul al XIX-lea i

pe Dedekind pentru al desvri.Astfel, n dezvoltarea teoriei numerelor putem distinge trei etape de dezvoltare:

1. etapa antichitii, cnd problemele de teoria numerelor erau cuprinse n aritmetic,nefiind separate total de celelalte ramuri ale matematicii elementare2. etapa desprinderii teoriei numerelor din aritmetic ca ramur aparte, ajungnd la oaritmetic superioar, ncepnd din Renatere pn n secolul al XIX-lea3. etapa modern a teoriei numerelor, din secolele al XIX-lea i al XX-lea, cnd n teorianumerelor i fac loc metode moderne de cercetare din teoria numerelor bazate pe teoriafunciilor de variabil complex i analiz matematic. Din acest punct de vedere ianatere o subramur a teoriei numerelor i anume teoria analitic a numerelor, rmnndca problemele care nu folosesc teoria funciilor i analiza matematic s constituie teoriaelementar a numerelor.

Se poate cosidera c teoria numerelor are mai multe ramuri, care interfereazntre ele, teoria numerelor avnd un caracter unitar, putnd ns vorbi despre:

Teoria elementar a numerelor ale crei probleme sunt legate de teoriadivizibilitii i reprezentarea numerelor sub o form dat. Capitolele importanteale teoriei elementare fiind: teoria congruenelor, ecuaiile diofantice(nedeterminate), teoria formelor. Se numete teorie elementar deoarece folosetemetode specifice aritmeticii i algebrei elementare.

Teoria algebric a numerelor, care se ocup de studiul diverselor clase denumere algebrice folosind procedee ale algebrei moderne.

Teoria analitic a numerelor se ocup de probleme ale teoriei numerelorpentru studiul crora sunt necesare metodele analizei matematice reale saucomplexe (cum ar fi, de exemplu, problemele privind distribuia numerelor primen irul numerelor naturale).

Teoria geometric a numerelor n care pentru diverse enunuri se dau


3/90


interpretri geometrice i pentru demonstraii, se folosesc procedee geometrice. Aproximrile diofantice, care se ocup, n principal, de problema

aproximrii numerelor reale prin numere raionale, problem strns legat denatura aritmetic a diverselor clase de numere.

Teoria probabilistic a numerelor , care folosete metode probabilisticepentru rezolvarea unor probleme ale teoriei numerelor. Ideea folosirii metodelorprobabilistice apare nc de la Gauss, dar teoria probabilistic a numerelor s-aconstituit n a doua jumtate a secolului XX, dup axiomatizarea teoriei

probabilitilor, n 1933, de ctre A. N. Kolmogorov, axiomatizare care a permisaplicarea teorei p robabilitilo r n domenii dintre cele mai neateptate.

Se mai face distincie ntre teoria multiplicativ a numerelor, care privetereprezentarea numerelor sub form de produse de numere de un anumit tip (cum ar fireprezentarea numrului ca un produs de numere prime) i teoria aditiv a numerelorcare privete reprezentarea numerelor ca sume de numere de un anumit tip(reprezentarea numerelor naturale ca sume de numere prime, sume de ptrate, etc).

Recent, domeniul teoriei numerelor si al criptografiei a cunoscut o dezvoltare rapidan ceea ce priveste asigurarea securitatii calculatoarelor si a informatiei, ca si proiectareasi implementarea unui numar de criptosisteme si alte sisteme conexe.

Criptarea mesajelor i trimiterea lor sub aceast form este utilizat de foarte multtimp. Unul dintre primii care au folosit tehnici de criptare pentru trimiterea mesajelor afost celebrul mprat roman Cezar. n comunicarea privat cu o persoan, folosirea unuicod secret poate preveni citirea intenionat sau neintenionat a mesajelor de ctre ceicare intr n posesia acestora, fie pentru c trebuie s le transporte pn la destinatar, fie

pentru c le intercepteaz n timp ce mesajul este transmis.Prin aceast lucrare ne situm n cadrul teoriei elementare a numerelor, urmrind nu

att aspectul istoric al unor noiuni, ct mai ales aezarea lor ntr-o ordine logic, necesarabordrii unor teoreme celebre din teoria numerelor.

n Capitolul I Noiuni fundamentale de teoria numerelor, Capitolul II Numereprime i Capitolul III Congruene am prezentat noiuni necesare abordrii temeiprezentei lucrri: mulimea numerelor naturale, mulimea numerelor ntregi Z,divizibilitatea n N i Z, Numere prime, Teorema fundamental a aritmeticii, Funciinumerice, Congruene de gradul nti i de grad superior.

n Capitolul IV Teoreme celebre, sunt prezentate principalele teoreme din Teorianumerelor i anume: Teorema lui Euler, Teorema lui Fermat, Teorema lui Wilson,Teorema lui Clement, Teorema lui Lagrange, Lema chinez a resturilor

Apoi se trece la prezentarea unor Probleme diofantice i aplicaii ale noiunilorprezentate, ncheind cu prezentarea unui instrument important n protejarea informaiei nform digital i de a asigura servicii de securitate Criptografia

Ultimul capitol cuprinde consideraii generale i metodice, referiri la cercurile dematematic i un proiect didactic pentru o activitate de cerc.


4/90


CUPRINS

I. Noiuni fundamentale de teoria numerelorI.1. Mulimea numerelor naturale 5I.2. Mulimea numerelor ntregi Z 15I.3. Divizibilitatea n N i Z 21

II. Numere primeII.1. Numere prime. Numere indecompozabile 26

II.2. Teorema fundamental a aritmeticii 31II.3. Funcii numerice 32

III CongrueneIII.1. Noiuni i rezultate introductive 37III.2 Congruene de gradul nti 41III.3. Congruene de grad superior 42

IV Teoreme celebreIV.1. Teorema lui Euler 43IV.2. Teorema lui Fermat 44IV.3. Teorema lui Wilson 45IV.4.Teorema lui Clement 46

IV.5. Teorema lui Lagrange 47IV.6. Lema chinez a resturilor 49

V Probleme diofanticeV.1. Fracii continue 50V.2. Aproximri diofantice 52V.3. Ecuaii diofantice 59

VI. AplicaiiVI.1. irul lui Fibonacci 61VI.2. Criptografie 67

VII Consideraii metodiceVII.1. Rolul matematicii n coal 74

VII.2. Aspecte specifice evoluia notiunilor de teorianumerelor 79

VII.3. Cercurile de matematic 82Bibliografie 89


5/90


CAPITOLUL I

I. Noiuni fundamentale de teoria numerelor

I.1. Mulimea numerelor naturaleModul intuitiv de percepere a numerelor naturale se bazeaz pe noiunea de

numr cardinal i cardinalul unei mulimi, n cadrul mai larg al teoriei mulimilor.n principiu, abordarea axiomatic a mulimii numerelor naturale, datorat lui

Peano, folosete modelul metodei logice, ntrebuinat cu succes de Euclid n geometrienc din antichitate.I.1.1. Axiomatica Peano

Definiie.Numimsistem Peanoun triplet (N, o,s), unde:a) Neste o mulime nevid

b) oNc) s : NN este o aplicaie numit de succesiune, care verific

urmtoarele condiii (axiome):a) oIms(adic"nN, o s(n))b)s este o aplicaie injectivg)Axioma induciei:Dac MNsatisface proprietile:

i) oMii) nM s(n)M,atunci M=N.Vom notas(n) = n* i vom spune c n* estesuccesorullui n.Dnd statut de axiome proprietilor a), b), g) matematicianul Giuseppe Peano

(1858-1932), a reuit s construiasc cu ajutorul lor ntreaga teorie a numerelor naturale.Teoria axiomatic a lui Peano folosete pentru numere modelul metodei logice,ntrebuinat cu succes de Euclid n geometrie, nc din antichitate.

Conform definiiei axiomatice dat de Peano, numerele naturale sunt elementeleunei mulimiN, n care se fixeaz un element o, mpreun cu funcia de succesiune, astfelnct sunt satisfcute axiomelea),b),g).

Propoziie:Pentru orice nN, no, exist uN, astfel nct n = u*.Demonstraie: Considerm M=s(N) {o} atunci MN, oM i nM

s(n)M, pentru c s(N)M. Din axioma induciei rezult c M = N i cum os(N)rezult c orice element dinN, diferit de o, este succesorul unui alt element dinN.

Teorema recursiei. Dac (N, o, s) este un sistem Peano i (S, a, j) este untriplet, unde S este o mulime nevid, aS i j : SS o funcie, atunci exist o unicfuncie f :NS cu proprietile:

1) f(o) = a2) f(s(n)) =j(f(n)),"nN.


6/90


Demonstraie: Considerm produsul cartezian N S i fie F* = {UNS |(o,a)U i (n, b)U (s(n),j(b))U} . Observm c F* , deoareceNSF* n

plus, pentru orice familie nevid (U i)iI , unde"iI, UiF*, rezult c *FIIiiU .

Fie f =I

*FU

U . Conform observaiei anterioare, se obine c fF*. Artm c f

reprezint o funcie, adic satisface urmtoarele dou condiii:c1) "nN,$bS, astfel nct (n, b)fc2) dac (n, b)f i (n, b)f, atunci b = b.Pentru a verifica prima condiie, vom considera mulimea M={nN| $bS, astfel

nct (n, b)f}i vom arta c M=N, folosind axioma induciei. MNi oM, pentru c(o, a)f.

Din nM rezult c $bS, astfel nct (n, b)f i cum fF*, se obine (s(n),

j(b))f, decis(n)M. Aadar, M=N.Verificm acum condiia c2).

Considerm mulimea M={nN|(n, b)f i (n, b)fb=b}. Vom aplica i pentruMaxioma induciei. MN. Presupunem, prin reducere la absurd, c oM.Deoarece (o, a)f rezult c exist bS, ba, astfel nct (o, b)f.

Notm cu f1 = f- {(o, b)} deci f1 f, f1 f. Artm c f1F*. Mai nti, (o, a) f1 iconsidernd (n, b1) f1 f, obinem (s(n),j(b1))f i deci (s(n),j(b1)) f1, deoareces(n) o,"nN. Aadar, f1F* i din definiia lui f rezult f f1, ceea ce este absurd.Prin urmare, oM.

Conform cu c1), exist bS, nct (n, b)f i cum nM, rezult c b este unic. Se

obine de aici (s(n),j(b))f. Presupunnd cs(n)M, rezult c exist cS, c j(b),astfel nct (s(n), c)f.Notm cu f2 = f- {(s(n), c)} deci f2f, f2f. Artm c f2F*. Avem (o, a)f2

i considerm (m, s)f2f.Se obine (m*, j(s))f.Apar dou situaii:

I) Dac m n, atunci n baza injectivitii funcieis, rezult c m* s(n) ideci (m*,j(s))(s(n), c), de unde (m*, j(s))f2.

II) Dac n =m, atunci (m*,j(s)) =(s(n), j(s)).Din (m, s) = (n, s)f i din unicitatea lui b, rezult c s = b, deci, (m*, j(s)) =(s(n),j(b)).Deoarecej(b) c, se obine (s(n),j(b))(s(n), c), adic (m*,j(s)) = =(s(n), j(b))f2.

Aadar f2F*, de unde f f2, ceea ce este absurd. Prin urmare, s(n)M iconform axiomei induciei, obinem M=N.

Folosind notaiile consacrate funciilor, condiiile (o, a)f, respectiv (n, b)f(s(n),j(b))f se scriu astfel: f(o) = a, respectiv f(n) = b f(s(n)) =j(b), adic tocmaicondiiile ce trebuiau satisfcute de funcia f.

Unicitatea funciei f se demonstreaz prin reducere la absurd. Considerm ofuncie g care satisface condiiile 1) i 2).

Fie M={nN|f(n) = g(n)}. Avem M Ni oM, deoarece f(o) = g(o) = a.Dac nM, atunci f(n) = g(n), decij(f(n)) =j(g(n)), de unde f(s(n)) = g(s(n)), adics(n)M.


7/90


Aplicnd din nou axioma induciei, rezult M=N, adic f = g.Teorem. Dac (N, o, s) i (S, a, j) sunt sisteme Peano, atunci exist o unic

funcie f :N

S, astfel nct f(o) = a, fs

=j

f i f este o bijecie.

Demonstraie: Mai rmne de artat c f este bijectiv. Aplicnd teoremarecursiei pentru sistemul Peano (S, a,j) i tripletul (N, o,s), rezult c exist o unicfuncie g : SN, pentru care g(a) = o i gj= =sg. Vom arta c g este inversa lui f.

Pentru aceasta, vom aplica teorema recursiei pentru sistemul Peano (N, o, s) itripletul (N, o,s). Rezult c exist o unic funcie h :NN, astfel nct h(o) = o ihs=sh. ns 1N i gf verific condiiile satisfcute de h, deoarece: (gf)(o) = g(a) =o = 1N(o) i (gf)s= =g(fs) = g(jf) = (gj)f = (sg)f =s(gf), iar 1Ns=s1N. Din unicitatea lui h rezult c gf = 1N.

Similar, aplicnd de aceast dat teorema recursiei pentru sistemul Peano (S, a,j)i tripletul (S, a, j) se obine c fg = 1S.

Aadar f este bijectiv.n baza acestei teoreme, vom considera c exist un unic sistem Peano (pentru cntre oricare dou sisteme Peano exist o bijecie care satisface condiiile din teorema demai sus).

Nva fi numit mulimea numerelor naturale i vom nota o cu 0 (numrul naturalzero), succesorul lui 0 cu 1, succesorul lui 1 cu 2, .a.m.d.

Propoziie. Neste o mulime infinit.Demonstraie: Presupunem prin reducere la absurd c N este finit i aplicm

urmtorul rezultat:Dac A este o mulime finit, iar f :AA este o aplicaie, atunci urmtoarele

afirmaii sunt echivalente:

i) f este injectivii) f este surjectiviii) f este bijectiv.

Pentru A =Ni f =s, observm cseste injectiv, dar nu este surjectiv (0Ims), prinurmare presupunerea fcut este fals, deciNeste infinit.

I.1.2. Adunarea numerelor naturale

Fie m un element oarecare, dar fixat al luiN. Considerm n teorema recursiei S =N, a = m ij=s. Conform teoremei, rezult c exist o aplicaie unic fm :NN, astfelnct:

1. fm(0) = m2. fm(s(n)) =s(fm(n)),"nN.

Notm fm(n) = n + m.Condiiile 1. i 2. se vor scrie astfel:

1) 0 + m = m2) n* + m = (n + m)*,"nN

i vor fi numitecondiiile de definiie ale adunrii.Propoziie.Au loc urmtoarele afirmaii:

1. n + 0 = n, "nN2. n +m* = (n + m)*, "nN


8/90


Demonstraie: Se aplic, pentru demonstrarea ambelor afirmaii, axiomainduciei, considernd mulimile:

1M1 ={nN|n + 0 = n}, respectiv2M2 ={nN|n + m* = (n + m)*}1. Avem M1N, 0M1 (rezult din 1) pentru m = 0) i dac nM1, adic n + 0 =

n, atunci n baza condiiei 2) n*+ 0 = (n + 0)* = n*, adic n*M1. Deci M1 =N.2. Avem M2N, 0M2, deoarece n baza condiiei 1) avem 0 + m* = m* = (0 +

m)*. n plus, dac nM2, adic n + m* = (n + m)*, rezult c n*+ m* = (n + m*)* = ((n+ m)*)* = (n* + m)*, utiliznd condiia 2) pentru m* i apoi pentru m. Prin urmaren*M2 i deci M2 =N.

Considerm funcia + :NNN, care asociaz perechii (n, m)NNelementuln + m = fm(n). Aceast funcie se numeteadunarea numerelor naturale.

Propoziie: Au loc urmtoarele:

A1. Asociativitatea adunriipentru orice n, m, pN, (n + m) + p = n + (m + p)A2. Comutativitatea adunrii

pentru orice n, mN, n +m = m +nA3. 0 este elementul neutru la adunare

"nN, n +0 = 0 + nA4. Legea de simplificare la adunare (numit reducere)

"pN, n + p = m + pn = m Fie n, mN. Au loc implicaiile:A5. n +m = 0n = 0 i m = 0A6. m + n = 1(m = 1 i n = 0) sau (m = 0 i n = 1).

Demonstraie:A1. Considerm, mai nti m i p fixate.

Fie M1 ={nN | (n + m) +p = n + (m + p)} . Aplicnd axioma induciei pentru M1 seobine M1 =N, folosind condiiile de definiie ale adunrii, 1i 2.

Considerm acum n i p fixate i mulimea:M2 ={mN|(n + m) + p = n + (m + p)} aplicnd din nou axioma induciei se obine

M2 =N.Cazul n care m i n sunt fixate este similar primului caz. Prin urmare, pentru m,

n, p oarecare nN, are loc proprietatea: (n + m) + p = n + (m + p).Demonstraiile pentru A2 i A3 sunt similare cu cele de mai sus.Pentru A4, mulimea creia i se aplic axioma induciei este M ={pN|n +p =

m + pn = m}.A5. Presupunem n0. Atunci, exist uN, astfel nct n = u*.

Obinem n +m = 0u* + m = 0(u + m)* = 0, contradicie. Aadar n = 0 i deci 0 +m = 0, adic m = 0.

A6. Presupunem, prin reducere la absurd, c (m1 sau n0) i (m0 sau n1). Sunt posibile urmtoarele patru situaii:

1. m1 i m02. m0 i n03. m1 i n14. n0 i n1.


9/90


1. Din m0 rezult c exist uNaa nct m = u*.Se obine m + n = 1(u + n)* = 0*u + n = 0u = 0 i n = 0, n baza injectivitii

lui s

i a proprietii A5 i obinem m = 1, fals. Din contradicia obinut rezult caceast situaie nu poate avea loc.Similar se arat c situaiile 2i 4nu pot avea loc.3. Avem n0, pentru c altfel din m + n = 1 ar rezulta c m =1, fals. Putem acum repetaraionamentul de la 1i deducem c i aceast situaie este imposibil.Observaie:Pentru orice nN, avems(n) = (n + 0)* = n + 0* = n + 1.

I.1.3. nmulirea numerelor naturale

Fie m un element oarecare, dar fixat, al luiN. Aplicnd teorema recursiei pentru S=N, a = 0 ij= fm, rezult c exist o aplicaie unic gm :NN, astfel nct:

1. gm (0) = 02. gm (s(n)) = fm (gm (n)),"nN.Notm gm (n) = nm.Condiiile 1. i 2. se vor scrie astfel:

1) 0m = 02) n*m = nm + m,"nN.

i vor fi numitecondiiile de definiie ale nmulirii.Propoziie: Au loc urmtoarele afirmaii:

1n0 = 0, "nN2nm* = nm + n,"nN.

Demonstraie: n demonstraie se aplic axioma induciei procedndu-se n mod

asemntor cazului operaiei de adunare. Considerm funcia : NN N, careasociaz perechii (n, m)NNelementul nm = gm (n).Propoziie: Au loc urmtoarele:

D. Distributivitatea nmulirii fa de adunarepentru orice m, n, pN, n(m + p) = nm + np

M1. Asociativitatea nmuliriipentru orice n, m , pN, (nm)p = n(mp)

M2. Comutativitatea nmuliriipentru orice n, mN, nm = mn

M3. 1 este element neutru la nmulire"nN, n1 = 1n = n

M4. Legea de simplificare la nmulire"pN, p0, np = mpn = m.

Fie n, mN. Au loc implicaiile:M5. nm = 1n = 1 i m = 1M6. nm = 0n = 0 sau m = 0.

Demonstraie:D, M1, M2, M3 se demonstreaz utiliznd axioma induciei.Demonstrarea proprietii M4, va fi dat ulterior (dup introducerea relaiei de

ordine peN).M5. Observm c n0m, altfel nm ar fi zero. Deci exist u, vN, astfel nct

n = u* i m = v*. Avem nm = u*v* = uv* + v* = =(uv* + v)*,deci (uv* + v)* = 1, de


10/90


unde uv* + v = 0 i conform cu A5 se obine uv* = v = 0. Rezult c m = 1 i utilizndM3 rezult c n = 1.

M6. Presupunem, prin reducere la absurd, c n0 i m0. Atunci exist u, vN, astfel nct n = u* i m = v*.Avem nm = u*v* = u*v + u* i conform cu A5 se obine u*v = u*=0, contradicie.Deci n = 0 sau m = 0.

n vederea simplificrii scrierii vom mai nota mn n loc de mn.

I.1.4. Relaia de ordine pe mulimea N

Definiie:Fie m, nN. Spunem c mn dac exist pNastfel nct n = m + p.Spunem c m


11/90


OM3. Fie pN, p0 i m


12/90


Prin reducere la absurd, presupunem c nu ar avea loc inegalitatea m


13/90


(3) Principiul al II-lea al induciei matematice implic principiul I al inducieimatematice.

(1). Fie P(m) propoziia m s, "sS. Observm c P(0) este adevrat, dar pentrusS, P(s*) este fals. Conform principiului I al induciei matematice,$eN, pentru careP(e) este adevrat i P(e*) este fals. Din P(e) adevrat rezult c e s,"sS. n plus,eS, pentru c altfel e


14/90


I.1.10. Teorema mpririi cu rest (Euclid)

Pentru orice a, bN, cu b0, exist q, rN, unic determinate, astfel nct a = bq+ r, 0r


15/90


I.2. Mulimea numerelor ntregi ZI.2.1. Construcia mulimii ZConsiderm pe mulimeaNNurmtoarea relaie:

(m, n) ~ (p, q) dac m + q = n + p, unde (m, n), (p, q)NN.Aceasta este o relaie de echivalen:

- este reflexiv, deoarece m + n = n + m ceea ce implic (m, n) ~ (m, n)- este simetric, deoarece presupunnd (m, n) ~ (p, q) rezult c m + q = n + p,

de unde deducem p + n = q + m, deci (p,q) ~ (m,n)- este tranzitiv, deoarece presupunnd (m, n) ~ (p, q) i (p, q) ~ (r, s) rezult c

m + q = n + p i p + s = q + r, de unde deducem (m + s) + (p + q) = (m + q) + (p + s)=(n +

p)+ + (q + r) = (n + r) + (p + q), deci m + s = n + r, adic (m, n) ~ (r, s).Clasa de echivalen a lui (m, n) o vom nota cu

),( nm ={(p,q)NN/ (m,n) ~ (p,q)}.

Definiie. Mulimea factor { }NN/~NN = n)(m,),( nm se numete

mulimea numerelor ntregii se noteaz cuZ.

Se numetenumr ntregorice element ),( nm al luiZ.I.2.2. Adunarea numerelor ntregiDefinim pe Z urmtoarea lege de compoziie + : ZZ Z,

),(),(),( qnpmqpnm ++=+

+ este bine definit. ntr-adevr, dac (m, n) ~ (m , n) i (p,q) ~ (p, q), atunci m + n= n + mi p + q= q + p, de unde deducem c (m + p) +(n+ q) =(m + n) + (p + q)= (n+ m)+(q + p)= = (n + q) + (m+ p), adic (m + p, n + q) ~ (m+ p, n+ q).

Legea de compoziie + pe Z se numete adunarea numerelor ntregi, iar),( qnpm ++ se numetesumanumerelor ntregi ),( nm i ),( qp .

Au loc urmtoarele:

1) Asociativitatea. Date numerele ntregi x = ),( nm , y = ),( qp , z = ),( sr rezult c

(x + y) + z = ))(),(())(,)(( sqnrpmsqnrpm ++++=++++ = x + (y + z), deoareceadunarea numerelor naturale este asociativ.

2) Comutativitatea. Date numerele ntregi x = ),( nm , y = ),( qp rezult c y + x =),( nqmp ++ = ),( qnpm ++ = x + y, deoarece adunarea numerelor naturale este

comutativ.3) Elementul neutru.S observm c pentru orice nN, avem (n, n) ~ (0, 0), deci

),( nn = )0,0( .n plus, pentru orice y = ),( qp Z, avem,),(),()0,0()0,0(),( qpqpqp =+=+ adic )0,0( este element neutru la adunarea

numerelor ntregi.


16/90


4) Elemente simetrizabile.Pentru orice numr ntreg x = ),( nm , exist x= ),( mn Z,

astfel nct x + x= x+ x = )0,0( . Astfel orice numr ntreg x este simetrizabil n raportcu adunarea numerelor ntregi.

I.2.3. nmulirea numerelor ntregi

Definim pe Z urmtoarea lege de compoziie :ZZZ,),(),(),( npmqnqmpqpnm ++= .

este bine definit. ntr-adevr, dac (m, n) ~ (m, n) i (p, q) ~ (p, q), atunciavem m + n= n + mi p + q= p+ q, de unde rezult c (mp + nq) + (mq+ np) +(np + mq) = (m + n)p +(n + m)q + (mq+ np) = (n + m)p + (m + n)q + (mq+ np)= =(mq + np)+ m(p + q) + n(q+p)=(mq + np) + m(q + p) + n(p + q)= =(mq +np)+ (mp+ nq) + (np + mq), deci (mp + nq) + (mq+ np)= = (mq + np) + (mp+nq) adic (mp + nq, mq + np) ~ (mp+ nq, mq+ np).

Legea de compoziie pe Z se numete nmulirea numerelor ntregi, iar),( npmqnqmp ++ se numeteprodusulnumerelor ntregi ),( nm i ),( qp .

Au loc urmtoarele:

1) Asociativitatea.Date numerele ntregi x = ),( nm , y = ),( qp , z = ),( sr , rezult

c (xy)z = ))()(,)()(( rnpmqsnqmpsnpmqrnqmp ++++++ =

= ),( nprmqrnqsmpsnpsmqsnqrmpr ++++++ =

= ))()(),()(( qsprnqrpsmqrpsnqsprm ++++++ = x(yz).2) Comutativitatea. Date numerele ntregi x = ),( nm , y = ),( qp rezult c xy =

),( npmqnqmp ++ = ),( qmpnqnpm ++ = yx.3) Elementul neutru.S observm c pentru orice nN, avem (n*,n) ~ (1, 0), adic

)*,( nn = )0,1( . Mai mult, pentru orice y = ),( qp Zavem )0,1(),( qp = ),()0,1( qp

= ),( qp , adic )0,1( este elementul neutru la nmulirea numerelor ntregi.4) Distributivitatea nmulirii fa de adunare.Pentru orice trei numere ntregi x, y, z

avem x(y + z) = xy + xz.

ntr-adevr, dac x = ),( nm

, y = ),( qp

, z = ),( sr

atuncix(y + z) = ))()(),()(( rpnsqmsqnrpm ++++++ =

= ))()(),()(( nrmsnpmqnsmrnqmp ++++++ = xy + xz,deoarece nmulirea numerelor naturale este distributiv fa de adunarea numerelornaturale.


17/90


I.2.4. Relaia de ordine pe Z

Fie ),( nm , ),( qp dou numere ntregi.

Definiie: Spunem c ),( nm este mai mic sau egal fa de ),( qp , i scriem),( nm ),( qp , dac m + qn+p.

S observm c relaia binar astfel definit nu depinde de reprezentani. ntr-adevr, dac (m, n) ~ (m1, n1) i (p, q) ~ (p1, q1), iar m + qn + p, atunci m1 + q1n1 +

p1. Din m + qn + p rezult c$uN: n + p = m + q + u, de unde n 1 + p1 + m + q = (m+ n1) +(q + p1)= =(n + m1) + (p + q1) = n + p + m1 + q1 = m + q + u + m1 + q1, aadarn1 + p1 = m1 + q1 + u, adic m1 + q1n1 + p1.

Au loc urmtoarele:1) este o relaie de ordine total peZ:

- este reflexiv: "),( nmZ,

),( nm

),( nm, deoarece m + nn + m

- este antisimetric: dac ),( nm ),( qp i ),( qp ),( nm , atunci m + qn +p i p + nq + m, de unde m + q = n + p, adic (m, n) ~ (p, q) i deci

),( nm = ),( qp

- este tranzitiv: dac ),( nm ),( qp i ),( qp ),( sr , atunci m + qn + p ip + sq + r, de unde m + q + p + sn + p+ + q + r urmeaz c m +sn + r,

adic ),( nm ),( sr

- pentru orice ),( nm i ),( qp numere ntregi avem ),( nm ),( qp sau ),( qp

),( nm aceasta rezult din faptul c pentru numerele naturale m + q i n + pavem m + qn + p sau p + n = n + pm + q = q + m.

2) OA : Pentru orice x, y, zZ, avem xy x + zy + z.OM : Dac x, yZ, xy, atunci pentru orice zZ, avem xzyz i pentru orice zZ,

z0, avem yzxz, unde cu 0 am notat numrul ntreg )0,0( .

S artm c dac xy i z )0,0( , atunci yzxz. Fie x = ),( nm , y = ),( qp , z

= ),( sr . Din xy rezult c m + qn + p, iar din z0 rezult c rs, deci$uN: s = r+ u.

Avem yz = ),( qrpsqspr ++ = ),( qrpuprquqrpr ++++ , iar xz =),( nrmsnsmr ++ = ),( nrmumrnunrmr ++++ .

yzxzpr + qr + qu + mr + mu + nrpr + pu + qr + mr + nr + nu qu + mupu+ nu(m + q)u(n + p)u, care este adevrat deoarece m + qn + p . Deci, yzxz.

Similar se arat c dac xy i zZ, 0z, atunci xzyz.

Definiie.Spunem c ),( nm este mai micdect ),( qp i scriem ),( nm


18/90


I.2.5. Principiul trihotomiei numerelor ntregi

Oricare dou numere ntregi x, y se afl n una i numai una dintre situaiile: x


19/90


I.2.6. Scderea numerelor ntregi

Dac x, y sunt dou numere ntregi, notm cu x-y suma x + (-y).Legea de compoziie j : ZZZ definit prin j(x, y) = x-y se numete scdereanumerelor ntregi.

Au loc urmtoarele:- Pentru orice dou numere ntregi x i y avem x-y = 0x = y.

ntr-adevr, dac x =y avem x-y = x-x = x + (-x) = 0, deoarece - x este simetricul lui x.Reciproc, dac x-y = 0, avem y = 0 + y = (x-y) + y = =[x + (-y)]+ y = x +[(-y) + y]=x + 0 = x. Din x + y + (-x) + (-y) = 0 rezult c - (x + y) = (-x) + (-y).Egalitatea-(x-y) = (-x) + y rezult astfel: -(x-y) =-[x + (-y)]= =(-x)-(-y) = (-x) + y.Analog se demonstreaz c-(-x + y) = x-y i c-(-x-y) = x + y.

- Pentru oricare trei numere ntregi x, y, z avem x(y-z) = xy-xz.

ntr-adevr, avem x(y-z) + xz = x[(y-z) + z]= xy, de unde rezult c xy-xz =[x(y-z) +xz]+ (-xz) = x(y-z).Observaie:Pentru x, yZ, avem xy = 0x = 0 sau y = 0.

Demonstraie: : Considerm x = 0 = )0,0( , y = ),( nm . Rezult c xy =),()0,0( nm = )0,0( .

: Dac 0x i 0y, atunci x = )0,(u , y = )0,(v , unde u, vN. Rezult

c xy = )0,(uv i cum xy = 0 = )0,0( rezult c uv = 0, de unde u = 0 sau v = 0, adic x =0 sau y = 0.

Similar, dac x 0 i y 0, atunci x = ),0( u

, y = ),0( v

, unde u, vN. xy =)0,(uv = )0,0( , deci u = 0 sau v = 0, adic x = 0 sau y = 0.

Pentru 0x i y0, x = )0,(u i y = ),0( v unde u, vN. Atunci xy = ),0( uv =)0,0( , deci u = 0 sau v = 0, adic x = 0 sau y = 0.

Analog se trateaz cazul x0 i 0y.S remarcm faptul c demonstraia poate fi fcut i folosind identificarea

numerelor ntregi pozitive cu numerele naturale.Dac x, y, z sunt numere ntregi, avem xy = xz i x0y = z.

ntr-adevr, din egalitatea xy = xz rezult c x(y-z) = xy-xz = 0. Deoarece x0 rezult

c y-z = 0, adic y = z.Definiie:Se numetemodululunui numr ntreg x, numrul natural notat cu|x|,

definit astfel:

=

0dac,

0dac,0

0dac,

xx

x

x

x

x

.


20/90


I.2.7. Teorema mpririi cu rest pentru numere ntregi

Pentru orice dou numere ntregi x i y, y 0, exist i sunt unice numerelentregi q i r, astfel nct x = yq + r i 0r< |y|.

Demonstraie:Dac x, yN, y0, atunci aplicm teorema cu rest pentru numerenaturale i obinem c exist q, rN, deci ntregi, astfel nct 0r0, atunci pentru|x|i y exist q1, r1 naturale, deci ntregi, astfelnct-x =|x|= yq1 + r1 i 0r1


21/90


I.3. Divizibilitatea n N i ZI.3.1. Cel mai mare divizor comun. Cel mai mic multiplu comun.I.3.1.1. Relaia de divizibilitate pe N

Definiie:Fie a, b N. Spunem c b divide a sau c a este multiplu de b inotm b | a dac$cN, astfel nct a = bc.Observm c dac b = 0, atunci a = 0, deci n cele ce urmeaz, vom considera deseoridoar cazul b0.

Proprieti: 1."aN, 1 | a1. "bN, b | 0

2. reflexivitatea: "aN, a | a3. antisimetria: dac a, bN, astfel nct a | b i b | a, atunci a =b

4. tranzitivitatea: dac a, b, c N, astfel nct a | b i b | c,atunci ac

5. dac a, b, cN, astfel nct a | b i a | c, atunci pentru orice x,yN, avem a|(xb+ yc).

6. pentru orice a, bN, a0, din b | a, rezult ba.Demonstraie:4. Din b | a rezult c$cN, astfel nct a = bc i din a | b rezult

$dN, astfel nct b = ad. Obinem a = a (dc).Dac a = 0, atunci din a | b rezult b = 0, deci a = b.

Dac a0, atunci din a = a (dc) rezult 1 = dc (conform M4) i deci d = c = 1(conform M5). Aadar a = b.

7. Din b | a rezult c exist cN, astfel nct a = bc. Cum a0rezult c c0, deci exist uNaa nct c = u*.Se obine a = bu* = b + bu, de unde rezult ba.

Celelalte proprieti rezult, cu uurin, din definiie.Proprietile 3, 4, 5 arat c "|" este o relaie de ordine. Nu este ns o relaie de

ordine total, pentru c nu oricare dou numere naturale pot fi comparate (n sensul

relaiei |), de exemplu, 3 7 i 7 3.

I.3.1.2. Relaia de divizibilitate pe Z

Definiie:Date dou numere ntregi x i y, spunem c x divide y sau c y estemultiplual lui x, dac exist un numr ntreg z, astfel nct y = xz.

Vom scrie x | y.Ca i relaia de divizibilitate peN, relaia de divizibilitate pe Zse dovedete a fi

reflexiv i tranzitiv:- "xZ, avem x = x1, de unde x | x- dac x, y, zZ, aa nct x | y i y | z, atunci $x', y'Zaa nct y = xx', z = yy',deci, z = (xx')y' = x(x'y'), de unde x | z.


22/90


Relaia de divizibilitate peZnu este ns antisimetric. De exemplu, avem 2 | -2, -2 | 2, dar 2-2.

Definiie: Dou numere ntregi x i y se numesc asociate n divizibilitate iscriem x ~ y, dac x | y i y | x.

Propoziie: Dou numere ntregi x i y sunt asociate n divizibilitate dac inumai dac x = y sau x = -y.

Demonstraie: Dac x = y, avem x | y i y | x prin reflexivitatea relaiei dedivizibilitate. Dac x = -y, avem x = y(-1), deci y | x i y = - (-y) = -x = x(-1), deci x|y.

Reciproc s presupunem c x | y i y | x. Atunci exist x', y' Z, astfel nct y =xx' i x = yy'. Dac x = 0, atunci y = 0x' = 0 = x.

Dac x0, avem x = yy' = (xx')y' = x(x'y') de unde rezult x'y' = 1, deci x' = y'= 1 sau x' = y' = -1, adic y = x sau y = -x.

Observm c"xZ, avem x = 1x, deci 1 | x. Numerele ntregi pentru care avem

x | 1 se numesc uniti. Conform propoziiei anterioare, rezult c: x | 1 x~1x= 1sau x = -1.Aadar, singurele uniti ale luiZsunt 1 i -1.Propoziia anterioar poate fi enunat i astfel: "Dou numere ntregi x i y sunt

asociate n divizibilitate dac i numai dac exist o unitate u, astfel nct x = uy".Rezult c x ~ y | x| = | y|, iar de aici se obine c relaia de asociere n

divizibilitate este o relaie de echivalen, ale crei clase de echivalen sunt de forma {n,-n}, pentru n0 i {0}, pentru n = 0.

I.3.1.3. Cel mai mare divizor comun a dou numere naturale

Definiie: Fie a, bN. dN se numete cel mai mare divizor comun alnumerelor a i b (notm d = (a, b)), dac:1. d | a, d | b2. "d'N: d' | a, d' | bd' | d.Lem: Fie m, n, p trei numere naturale astfel nct m = n + p. Dac numrul

natural nenul q divide oricare dou dintre numerele m, n, p atunci q divide i pe al treileanumr.

Demonstraie: Fie q | n i q | p. Atunci $ u, vN: n = qu i p=qv. Rezultm=q(u+v), deci q | m. Fie acum q | m i q | n. Atunci $t, sN: m = qt i n = qs. Din qt =qs + p rezult qsqt i cum q > 0 obinem st, de unde rezult c$wNaa nct t = s+ w. Din qt = qs + p rezult qs + qw = qs + p, deci qw = p, de unde q | p.

Analog se arat c din q | m i q | p, rezult q | n.Lem:Dac x, y, q, rN, satisfac egalitatea x = yq + r atunci exist cel mai mare

divizor comun al lui x i y dac i numai dac exist cel mai mare divizor comun al lui yi r. n plus, avem (x,y) = (y,r).

Demonstraie:Presupunem c exist cel mai mare divizor comun al lui x i y, pecare-l notm cu d. Din d | x i d | y rezult, conform lemei anterioare, c d | r, deci avem d| y i d | r.

Fie acum d'N, aa nct d' | y i d' | r. Conform aceleiai leme, rezult c d' | x ideci d' | x i d' | y, adic d' | d.Aadar, d este cel mai mare divizor comun al lui y i r i avem (y,r)=d=(x,y).


23/90


Reciproc, presupunnd c exist cel mai mare divizor comun al numerelor y i r,pe care-l notm cu d, va rezulta d | y i d | r, de unde d | qy + r = x, deci avem d | x i d| y.

Fie acum d'N, aa nct d' | x i d' | y. Obinem d' | r, deci d' | y i d' | r, de unde d'| d. Astfel, d este cel mai mare divizor comun al lui x i y i avem (x,y) = d = (y, r).

Teorem:Fie a, bN. Atunci exist i este unic cel mai mare divizor comun alnumerelor a i b.

Demonstraie:Dac a = b = 0, atunci cel mai mare divizor comun este 0.Presupunem, n continuare, b0. Procedeul de determinare pe care-l vom folosi poartnumele de:

I.3.1.4. Algoritmul lui Euclid

Aplicm teorema mpririi cu rest pentru a i b. Rezult c exist q 0, r0N

, unicdeterminate astfel nct:(0) a = bq0 + r0, unde 0r0 < b.Dac r0 = 0, atunci a = bq0, de unde b | a, deci (a,b)=b.Dac r0 0, vom aplica teorema mpririi cu rest pentru b i r0, iar dac i noul rest r1 vafi nenul, vom repeta procedeul, mprind ri la ri+1(iN), pn cnd vom obine un restnul, astfel:(1) exist q1, r1N: b = r0q1 + r1, 0 < r1 < r0(2) exist q2, r2N: r0 = r1q2 + r2, 0 < r2 < r1...............................................................................(n) exist qn, rnN: rn-2 = rn-1qn + rn, 0 < rn < rn-1

(n+1) exist qn+1, rn+1N: rn-1 = rnqn+1 + rn+1, rn+1 = 0irul b > r0 > r1> ... > ri-1 > r1 > ri+1 >... este un ir strict descresctor de numerenaturale, deci cu siguran vom ajunge la un rest egal cu 0.Am considerat c acest rest este rn+1. Conform lemei anterioare avem:(a, b) = (b, r0) = (r0, r1) = .... = (ri, ri+1) = ....= (rn-1, rn) = rn deoarece rn | rn - 1. Deci (a, b) =rn

Verificm unicitatea lui d = (a, b).Presupunem c d1 Nsatisface cele dou condiii din definiia celui mai mare

divizor comun pentru a i b , adic:i) d1|a i d1|bii)"d2 N:d2|a i d2|bd2|d1.

Rezult atunci c d | d1 (din aceea c d | a, d | b) i, analog, d1 | d adic d1 = d.

I.3.1.5. Cel mai mare divizor comun a dou numere ntregi

Definiie:Fie x, yZ. Un element dZse numete uncel mai mare divizor comunal numerelor x i ydac:

1) dx i dy2) "dZ :dx i d yd d.S observm c dac d este un cel mai mare divizor comun al numerelor x i y, atunci

i d satisface condiiile de a fi un cel mai mare divizor comun al numerelor x i y.


24/90


Reciproc, dac d i d sunt fiecare un cel mai mare divizor comun pentru x i y, avemdd, folosind faptul c d este cel mai mare divizor comun al numerelor x i y apoi,folosind faptul c d este cel mai mare divizor comun pentru x i y, avem dd, adic d~ d, de unde d = d sau d = -d.

Observaie:Dac a, b, x, y, dZi dac dx i d y, atunci, n baza definiieidivizibilitii numerelor ntregi, rezult c d(ax + by).

Pentru demonstrarea existenei celui mai mare divizor comun a dou numere ntregise procedeaz n mod analog cazului numerelor naturale.

Fie x, yZ.Dac y = 0, atunci exist cel mai mare divizor comun al lui x i 0 i este (x,0) = x.

Presupunem acum y0. Dac yx, atunci (x,y) =y. Dac y x, atunci existnNi$q0, q1, ..., qn+1, r0, r1, ..., rnZ, aa nct:x = yq0 + r0, 0 < r0


25/90


Vom arta c m = [a,b].Din mMa,b rezult am i bm.Aplicm teorema mpririi cu rest pentru m i m. Rezult c $q,rNaa nct

m= mq + r, 0r < m. S presupunem acum c r0. Din am, am i m=mq + rrezult c ar. Analog din b|m i bm rezult c br. Aadar, rMa,b i cum mm,"mMa,b, obinem c mr, ceea ce este fals.

Prin urmare, r = 0, de unde mm i cu aceasta am verificat faptul c m=[a,b].Mai rmne de artat unicitatea lui m.Presupunem c exist m1N, astfel nct s fie satisfcute condiiile:i) am1, bm1ii) "m2N: am2, bm2m1m2.Rezult atunci c m1 | m i m | m1, deci m = m1.

I.3.1.7. Cel mai mic multiplu comun a dou numere ntregi

Definiie: Cel mai mic multiplu comun a dou numere ntregi x i y este unnumr ntreg m, satisfcnd urmtoarele condiii:

1) xm, ym2) "mZ: xm i ym mm.Ca i n cazul celui mai mare divizor comun a dou numere ntregi, cel mai mic

multiplu comun, dac exist, este unic pn la o asociere n divizibilitate, adic dac meste cel mai mic multiplu comun al elementelor x i y, atunci i m este cel mai micmultiplu comun al acestor dou elemente.

Prescurtat, notm cel mai mic multiplu comun al elementelor x i y cu c.m.m.m.c.

(x,y) sau cu [x,y].n vederea unicitii se poate impune condiia de pozitivitate pentru [x, y].Din proprietile divizibilitii numerelor ntregi, rezult c

c.m.m.m.c.(x,y)=c.m.m.m.c.(-x,y)=c.m.m.m.c.(x,-y)=c.m.m.m.c.(-x,-y), aadar putemreduce problema celui mai mic multiplu comun a dou numere ntregi la cel mai micmultiplu comun a dou numere naturale, despre care tim c exist mereu.

GeneralizareDefiniiile date pentru c.m.m.d.c. i c.m.m.m.c (att n cazulN, ct i n cazulZ)

pot fi extinse uor pentru cazul a n numere, anume condiiile 1 i 2 capt forma:1. d | x1,.., d | xn (respectiv x1 | m, ..., xn | m),2. d | x1,..., d | xnd | d (respectiv x1| m, ..., xn | m m | m).

Notnd corespunztor (x1, ..., xn), respectiv [x1, ..., xn], se obine c(x1,..., xn) = (...(x1, x2), x3), .... , xn)...) i[x1,..., xn] = [...[x1, x2], x3] .... , xn]...].Din acest egaliti pot fi decelate noi definiii (echivalente cu cele anterioare) pentru

(x1,..., xn), respectiv [x1, ..., xn].


26/90


CAPITOLUL II

Numere prime

II.1. Numere prime. Numere indecompozabile

Definiie:Un numr natural p 0, p 1 se numete prim dac oricare ar fi m, nnumere naturale, din pmn rezult pm sau pn.

Definiie:Un numr natural b 0, b 1 se numete indecompozabil (ireductibil)

dac din ub rezult u = 1 sau u = b.Un numr natural m 0, m 1, care nu este indecompozabil se numetedecompozabil.

Lema:Fie m un numr natural, m0, m1. Urmtoarele afirmaii sunt echivalente:1) m este decompozabil2) exist n, pN, astfel nct m = np, cu 1 < n < m i 1 1 admite un divizor indecompozabil.Demonstraie:Mulimea P = {qNq > 1, qm} nu este vid, deoarece conine

pe m. n conformitate cu P.B.O. ,$bP, bq, "qP.Vom arta c b este indecompozabil.Presupunem c b ar fi decompozabil atunci conform lemei anterioare, exist n, p

N, astfel nct b = np, 1 < n < b i 1 < p < b.Din nb i bm rezult nm i cum 1 < n rezult c nP.Dar n < b i nP contrazice alegerea lui b.Prin urmare, b este indecompozabil i este divizor al lui m.

Teorem: Fie p un numr natural, p 0, p 1. Urmtoarele afirmaii suntechivalente:1) p este prim2) p este indecompozabil.Demonstraie:1) 2). Fie k un divizor al lui p.

Exist tN, astfel nct kt = p, deci pkt.Cum p este prim, rezult pk sau pt. Dac pk, atunci$vN: k =pv.Din p = kt rezult p = pvt, deci 1 = vt, rezult v = t = 1, deci k = p.

Analog, dac pt deducem k = 1.Aadar, p este indecompozabil.


27/90


2)1) Presupunem c exist elemente indecompozabile, care nu sunt prime. Fiep cel mai mic element indecompozabil, care nu este prim (Neste bine ordonat). Cum pnu este prim, rezult c exist m, nN, astfel nct pmn i pPm i pPn. Dar m > 1,deoarece dac am avea m = 0, atunci pm, iar dac am avea m = 1, din pmn ar rezulta

pn.Similar, rezult n > 1.S artm acum c putem considera m < p i n < p.

Dac m > p, atunci conform teoremei mpririi cu rest, rezult c $ q, r N, unicdeterminate, astfel nct m = pq + r, cu 0 < r < p, de unde rezult mn = pqn + rn din

pmn i ppqn rezult c prn.

n plus, din 0 < r < p rezult c pr.

Deci, dac m > p, atunci am putea nlocui m cu r i vom avea prn, pr, pn i 0< r < p. La fel se procedeaz dac p < n.

Mai mult, putem alege m i n, astfel nct produsul mn s fie minim (deoarece Neste bine ordonat).

Din pmn rezult c exist qN, astfel nct mn = pq.Avem q > 1, deoarece q=1 implic mp i cum p este indecompozabil rezult m =

1 sau m = p.Dar m < p, deci singura posibilitate ar fi m = 1, de unde rezult n = p, ceea ce este

n contradicie cu alegerea lui n.Prin urmare q > 1 i vom considera b un divizor indecompozabil al lui q rezult

bq.Avem pq = mn < pn < pp. De aici rezult q < p, deci b q < p. Din bq i qmn

rezult bmn.Deoarece p este cel mai mic numr indecompozabil care nu este prim, rezult c beste prim i deci, din bmn rezult bm sau bn.

Presupunem c bm. Fie m1, q1Nastfel nct m = bm1 i q = bq1.

Din mn = qp rezult bm1n = bq1p, deci m1n = q1p. Aadar pm1n i pn i pm1,pentru c dac p ar divide m1, atunci din m = bm1 ar rezulta c p divide m, ceea ce estefals. Din b > 1 i m = bm1 rezult m > m1 i deci mn > m1n.

Aadar, pm1n, pm1, pn i m1n < mn, ceea ce intr n contradicie cu alegerealui mn, deci, presupunerea fcut este fals i teorema este demonstrat.

Teorema lui Euclid:Exist o infinitate de numere prime.Demonstraie: Presupunem c exist un numr finit de numere prime i anume

p1, p2, ..., pn.Considerm numrul a = p1p2 ... pn + 1. Deoarece orice numr prim este prin

definiie nenul, rezult c a > 1, prin urmare, a admite un divizor indecompozabil, deciprim, anume va fi unul dintre p1, p2, ..., pn.

Fie pi, cu i{1,2,...,n} acest divizor. Avem pia i pip1p2 ... pn i atunci, rezultc p i1, de unde pi1, ceea ce este fals.

Aadar, presupunerea fcut este fals, deci exist o infinitate de numere prime.Propoziie:Fie pN, p > 1. Dac p este prim i pa1a2...an, unde n2 i"

i{1,2,...,n}, aiN, atunci$i{1,2,...,n}, astfel nct pai.Demonstraie:Se verific uor prin inducie dup n.


28/90


Teorema de descompunere a numerelor naturale n factori primi

Teorem:Orice numr natural a > 1 poate fi descompus n mod unic (abstraciefcnd de ordinea factorilor) n produs finit de numere prime.

Demonstraie:S artm mai nti existena unei astfel de scrieri. Considerm A= {aN a > 1, a nu este prim i nici nu este produs de numere prime}.Vom arta c A =.Presupunem prin absurd c A i atunci n conformitate cu P.B.O.,$tA nct t

a,"aA. Din faptul c tA rezult c t nu este prim, deci t este decompozabil.Fie t1, t2Naa nct t = t1 t2 cu 1 < t1 < t i 1 < t2 < t.Din faptul c t1 < t i t2 < t i din alegerea lui t rezult c t 1A i t2A, deci t1 i t2 sunt

prime sau sunt produse de numere prime:

t1 = p1p2 ...ph , t2 = p1p2...pk ,unde h, kN, h1, k 1, iar p1, p2, ..., ph , p1, p2, ... , pk sunt numere prime.Rezult c t = t1t2 = p1 p2 ... ph p1 p2 ... pk, adic t este un produs de numere prime,contradicie cu tA. Prin urmare A = , deci orice numr natural a > 1 poate fidescompus n produs finit de numere prime.

n vederea demonstrrii unicitii scrierii, fie a = p1p2 ... ph = =q1q2...qk, unde h, kN, h 1, k1 i p1, p2, ..., ph , q1, q2, ... , qk sunt numere prime. Artm c h = k ieventual dup o renumerotare a factorilor, pi = q i, pentru orice i{1,2,...,k}.

Demonstrm prin inducie dup h.Dac h = 1, atunci a = p1 = q1 q2 ... qk i p1 fiind numr prim rezult c $ i{1,2,...,k},astfel nct p1qi. Dar qi este prim, deci indecompozabil, prin urmare p1 = q i. Presupunem

k >1. Obinem de aici egalitatea

=

=k

iss

sq1

1

, de unde rezult qs = 1, pentru orices{1,2,...,k}-{i}, ceea ce contrazice faptul c numrul q s este prim, pentru orices{1,2,...,k}-{i}.

Aadar, k = 1 i p1 = q1.Presupunem c unicitatea are loc pentru orice aN, a > 1, care se scrie ca un

produs de factori primi, iar numrul acestor factori primi este mai mic dect h i vomdemonstra c are loc pentru orice numr care se scrie ca un produs de h factori primi.Fie p1p2 ... ph = q1 q2 ... qk, unde"i{1,2,...,h}, "j{1,2,...,k}, pi i qj sunt prime.

Din faptul c ph este prim i phq1q2... qk rezult c $ j{1,2,...,k}, astfel nctphqj i cum qj este prim rezult ph=qj. Fr a restrnge generalitatea, putem presupunec j = k.

Obinem p1... ph 1 = q1... qk 1 i conform ipotezei inductive rezult c h1=k-1 i pi = q i,"i{1,2,...,h-1}, pn la o renumerotare (cu h-1, respectiv k-1, am notatnumrul natural al crui succesor este h, respectiv k).

Aadar, h = k i"i{1,2,...,h}, pi = qi.Observaie: Factorii p1, p2,..., ph din descompunerea de mai sus pot s i

coincid de aceea, putem scrie


29/90


k

kpppaaaa ...21 21= , unde " i{1,2,...,k}, pi este prim, ai N, ai 1 i " ij,

i,j{1,2,...,k}, pipj .

Scrierea de mai sus poart numele descrierea canonica lui a.Utiliznd aceast scriere, putem caracteriza divizorii lui a i anume: Propoziie:Fie aN, a > 1, cu scrierea canonic

k

kpppaaaa ...21 21= , unde"i{1,2,...,k}, pi este prim,ai N,ai 1 i"ij, i,j{1,2,...,k},

pipj.

Atunci da dac i numai dack

kpppdddd ...21 21= , cu 0 di ai,"i{1,2,...,k}.

Demonstraie: Dack

kpppdddd ...21 21= , cu 0 di ai, "

i{1,2,...,k}, atunci a = dc, undekk

kpppcdadada ---= ...2211 21 , deci da.

Dac da, atunci exist cN, astfel nct a=dc, decicpppa k

k

= ddd ...2121 adic pi intr ndescompunerea lui d cu exponentuldi ai, pentru orice i{1,2,...,k}.

Remarcm i c pentru dou numere naturale a i b putem pune n eviden doudescompuneri, n care apar aceeai factori primi, cu meniunea c exponenii acestora potfi i zero, astfel

a,bN,a1, b1,h

hpppaaaa = ...21 21 i

h

hpppbbbb = ...21 21 ,

unde"i{1,2,...,h},ai0 i bi0 i piprim, iar"i,j{1,2,...,h}, ij, pipj .Atunci:

( ) ( ) ( ) ( )hhhpppbadbababa ,min,min

2,min

1 ..., 2211 == ,

iar [ ] ( ) ( ) ( )hh

hpppbam bababa ,max,max2,max1 ..., 2211 == .Teorem:Pentru orice a,bN, a1, b1 are loc egalitatea ab=(a,b)[a,b].Demonstraie:Rezult din faptul c pentru orice i{1,2,...,h}, avem min(ai,b i) +

max(ai,bi) =ai +b i.Pentru orice numr ntreg x {0,1,-1} avem x = sgn(x)x, iar x este un

numr natural diferit de 0 i de 1. Pentruxaplicm teorema fundamental a aritmeticiinumerelor naturale. Rezult cxse scrie ca produs de numere prime i decix = sgn (x) p1p2...pm, unde"i{1,2,...,m}, pi este prim.

Din sgn(x) {1,-1} i din faptul c 1 i 1 sunt uniti, rezult c x =up1p2...pm, unde u este o unitate, iar p1, p2, ..., pm sunt numere prime.

Numerele p1, p2, ..., pm nu sunt neaprat distincte, deci grupndu-le pe toate celeegale ntre ele, obinem:n

npppuxaaa = ...21 21 ,

unde u este o unitate, p1, p2, ..., pn sunt numere prime distincte i a1, a2, ..., an suntnumere naturale. n egalitatea de mai sus putem face s apar orice numr prim p{ p1,

p2, ..., pn}, astfel:0

21 ...21 ppppux nn =aaa

.


30/90


Notnd cu P mulimea tuturor numerelor prime i cua(pi) exponentulai al lui pi,

putem scrie

( )

=Pp

ppuxa

(precizm ca(p)0 doar pentru un numr finit de elementedin P, altfel spus avem un produs finit).Propoziie: Fie x,y,zZ, aa nct xyz, iar x i y sunt prime ntre ele (au cel

mai mare divizor comun 1). Atunci xz.Demonstraie:Din faptul c x i y sunt prime ntre ele rezult c $ u,vZ aa

nct ux + vy = 1.Avem z = z1 = z(ux + vy) = (zu)x + v(yz), deci z = (zu)x + v(yz). Deoarece xyz rezultn baza ultimei egaliti c xz.

Corolar: Pentru orice numr prim p i orice numere ntregi x i y are locimplicaia:

pxy px sau py.

Demonstraie:Din (p,x)p i p numr prim rezult c (p,x) = 1 sau (p,x) = p.Dac (p,x) = 1 atunci py, conform propoziiei precedente, iar dac (p,x) = p avem c

px.Definiie:Se numeteordinullui p n x i se noteaz n = ordp(x) numrul natural

n, care satisface condiia: pnx iar pn+1x.

Avem ordp(x) = 0px i ordp(x) npnx.Corolar: Pentru"x,yZi pentru orice numr prim p, avem ordp(xy)= ordp(x) +

ordp(y).

Demonstraie: Notm ordp(x) = m i ordp(y) = n. Atunci x = pmx i px i

respectiv y = p

n

y i p

y.Rezult xy = p

m+n

xy, iar din corolarul anterior rezult cpxy, deci:ordp(xy)= m + n = ordp(x) + ordp(y).


31/90


II.2. Teorema fundamental a aritmeticii

Orice xZ {-1, 0, 1} admite o descompunere n factori primi

( )

=Pp

ppuxa

,

unic pn la o ordine a factorilor. Anume: dac

( )

=Pp

ppuxa

, u este o unitate ia(p)N*numai pentru un numr finit de elemente din P, atunci u = sgn(x) ia(p) = ordp(x),

pentru orice pP.Demonstraie: Existena rezult din consideraiile anterioare. Din

( ) ( ) ( ) ( )mpm

pp

Pp

p ppuppuxaaaa ==

...21 21rezult c"q numr prim, avem: ordq(x)= ordq(u)

+a(p1) ordq(p1) +a(p2) ordq(p2) + ... + a(pm) ordq(pm) = ordq(u) + ( ) ( )Ppq pordpa .

Din ordq(u) = 0 (deoarece u este o unitate) i ordq(p) = 1q = p, iar pentru qp,avem ordq(p) = 0, rezult c ordq(x) =a(q), pentru orice qP. Pe de alt parte, este clarc u = sgn(x).

Propoziie: Fie x, yZ*. Avem yx "pP, ordp(y)ordp(x).Demonstraie: Din yx rezult c$ zZ, aa nct x = yz, de unde" pP,

avem ordp(x) = ordp(y) + ordp(z) ordp(y).

Presupunem c ordp(y)ordp(x),"pP i fie

( )

=Pp

ppuxa

,

( )

=Pp

ppvyb

, unde

u i v sunt uniti, iar pentru"

p

P, b

(p) = ordp(y)

ordp(x) =a

(p).Fie

( ) ( )

-=Pp

pppuvz

ba

. Obinem

yz = uv2( ) ( ) ( ) ( )

- =Pp

pp

Pp

pp puppabba

, deci y |x.Observaie:

Dac considerm acum x, z Z,

( )

=Pp

ppux a

i

( )

=Pp

ppwz g

, atunci( ) ( ) ( )( )

=Pp

pppyx

ga ,min,, iar

[ ] ( ) ( )( )

=Pp

pppyx

ga ,max,i cum "pP, min(a(p),g(p))

+ max(a(p),g(p)) =a(p) +g(p), obinem c xy = (x,y)[x,y].


32/90


II.3. Funcii numerice

Prinfuncie numericvom nelege orice funcie definit peN(sauN*) cu valorinumerice (nN, Z, Q).

O funcie numeric este numit multiplicativ dac pentru orice m, nN, aanct (m,n) = 1, avem f(mn) = f(m)f(n).

Dac funcia multiplicativ f nu este identic nul ($nNaa nct f(n)0), atuncif(1) = 1. ntr-adevr, avem f(n) = f(n 1) = f(n)f(1), de unde rezult f(1) = 1 (din f(n)0).

Dac pentru orice m,nN, avem f(mn) = f(m)f(n) atunci se spune c funcia festetotal multiplicativ.

Teorem:Dac f1 i f2 sunt funcii multiplicative, atunci i f =f1 f2 este funciemultiplicativ.Demonstraie: ntr-adevr, dac m,n N, nct (m,n) = 1, atunci f(mn) =

f1(mn)f2(mn) = f1(m) f1(n) f2(m) f2(n) = f(m)f(n).

Funcia numeric F definit prin( ) ( )

=nd

dfnFse numete funcia sumatoriea

lui f(n).Teorem:Dac f este multiplicativ, atunci F este multiplicativ.Demonstraie:Fie m,nN, aa nct (m,n) = 1 i fie dmn. Avem d=d1d2, unde

d1m, d2n i (d1,d2) = 1.

Atunci ) ) ) ) ) ) )

nFmFdfdfddfdfmnF ndmdnd

mdmnd

=

21

2

1

2121

.

Teorem: Dac f este o funcie multiplicativ ih

hpppaaaa = ...21 21 este

descompunerea canonic a numruluia, atunci:) ) ) ))

) )

))

h

hhh

ad

pf...pfpf

...pf...pfpfdf

2

1

2

11

1

1 1

(n cazula= 1 membrul al doilea se consider egal cu 1).Demonstraie:n membrul al doilea, obinem o sum de termeni de forma:

( ) ( ) ( ) ( )kk kk pppfpfpfpf bbbbbb = ...... 2121 2121 , unde"i{1,2,...,k}, 0 b i ai.

Observm c astfel, nu se omit i nici nu se repet termenii din)

d|a

df, adic

suma considerat este chiar)

d|a

df.

Fie mN, m>1 cu descompunerea canonick

k

p...ppm 2121 .

Divizorii lui m sunt numerele naturale d de forma:k

kpppdbbb = ...21 21 , 0 b i ai,"

i{1,2,...,k}. Rezult c m are (a1 + 1)(a2 + 1)...(ak + 1) divizori. Singurul divizoral lui 1 este 1. Dintre toi divizorii lui 0 l considerm numai pe 0 (care nu-l depete pe0).


33/90


Putem defini o funcie astfel:

Definiie:Funciat:NN, dat prin:

( )( )( ) ( )

===>+++

=10,1

,...,1,1...11 21 2121nsaundac

pppnndacn

k

kk

aaaaaa

t

este numit funcianumrul divizorilor.Teorem:Funciateste funcie multiplicativ.Demonstraie:Fie m,nN, astfel nct (m,n) = 1.Vom verifica egalitatea:t(mn) =t(m) t(n).

Dac m = 0, atunci din (m,n) = 1 rezult n = 1 i decit(01) =t(0)t(1).Dac m = 1, atuncit(1n) =t(1)t(n).Considerm acum cazul m > 1, n>1 avnd descompunerile canonice

k

kpppm

aaa

= ...21

21 ,h

hqqqn

bbb

= ...21

21 .Din (m,n) = 1 rezult c"i{1,2,...,k}, "j{1,2,...,h} piqj.Obinem:

hk

h

k

q...qqp...ppnm 2121 2121 de undet(mn) = (a1 +1)(a2 +1)...(ak + 1) (b1

+ 1)(b2 + 1) ...(bh + 1) =t(m)t(n).

Fie numrul natural m > 1, care are descompunerea canonic:k

kpppmaaa = ...21 21 .

Avem

=

-

-

-

-

-

- +++

1

1

1

1

1

1 1

2

12

1

11

21

k

k

p

p.....

p

p

p

p k

( )( )( )

{ }

==+++

++++++=

md,...,k,i

k

kkk

dp...ppp...pp

...p...ppp...pp

ii

kk

210

212

22221

211

21

21

1

11

Definiie:Funcias:NN, dat prin:

( )

==

=>--

--

--

=

+++

0011

111

11

11

21

21

21

1

2

12

1

11

mdac,

mdac,

p...ppm,mdac,p

p...

p

p

p

p

m

k

k

k

k

k

se numete funciasuma divizorilor.Similar cu teorema precedent, se arat c are loc:Teorem:Funciaseste funcie multiplicativ.Definiie: Indicatoarea lui Euler, notat cu j, este funcia numeric definit

astfel:j :N* N* i" n N*,j(n) este numrul de numere naturale mai mici sauegale cu n i prime cu n.

Remarcm c, dac n = p, unde p este numr prim atuncij(p) = =p 1.

Fie acumk

kpppnaaa = ...21 21 .


34/90


Pentru a calculaj(n), formm, mai nti, irul: (*) 1, 2, 3, ..., n.Eliminm din acest ir p1 i toi multiplii si.

Acetia sunt: p1, 2p1, 3p1, ...,1

1pp

n

i numrul lor este 1pn

.

Din irul (*) rmn:

-=-

11

11

pn

p

nn

elemente.

Multiplii lui p2 din (*) sunt: p2, 2p2, ...,2

2

pp

n

i numrul lor este 2pn

.

ntre acestea, unele sunt divizibile i cu p1 i numrul acestora este 21ppn

.Eliminm dintre multiplii lui p2, pe numerele divizibile cu p1. Rmn

-=-12212

11

pp

n

pp

n

p

n

. Dup eliminarea acestor elemente din irul (*), mai rmn

-

-=

---

212121

11

11

ppn

pp

n

p

n

p

nn

.Continund raionamentul n acest mod, se obine:

( )

( )( ) ( ) .111

11

11

11

2111

21

1

21

21 ---=

=

-

-

-=

---k

k

k

p...ppp...pp

p...

ppnn

k

j

ntr-adevr, presupunnd c dup eliminarea multiplilor lui p1, p2, ..., pi obinem

-

-

-

ipppn

11...

11

11

21 , atunci, la urmtorul pas vom elimina i multiplii lui pi+1,

care sunt n numr de 1+ipn

.

Dintre acetia 11 +ippn

sunt i multipli de p1, 12 ippn

sunt i multipli de p2, ..., 1+iippn

sunt

i multipli de pi, iar 121 +ippp

n

sunt i multipli de p1 i p2 etc.Deci, ar trebui s mai eliminm din (*)

)

12111

121112111

...1.......

......

-

i

i

ii

iiiiii

ppp

n

ppp

n

ppp

n

pp

n

pp

n

pp

n

p

n

i atunci rmn

-

-

-

121

11

11

11

ip

...pp

n.


35/90


n acest mod se obine cj(n) =

-

-

-

kpppn

11...

11

11

21 .Teorem: Funciajeste multiplicativ.Demonstraie: Rezult din faptul c pentru orice n N*, avem

( )

-

-=

kppnn

11...

11

1

j, unde

k

kpppnaaa = ...21 21 .

Definiie:Funciam:N*Z

( )( ) { }

=

"=-

-

=

1ndac,1

i

,...,2,1prim,cu...ppndac,1

unitatedediferitptratunprintrdividesendac,0

k21

ji

i

k

ppji

kippnm

este numitfuncia lui Moebius.

Teorem: Fie f o funcie multiplicativ ik

kpppaaaa = ...21 21

descompunerea canonic a numrului a. Atunci

( ) ( ) ( )( ) ( )( ) ( )( )kad

pfpfpfdfd ---=

1...11 21m

(dac a = 1, membrul al doilea se consider egal cu 1)Demonstraie:Funciameste evident multiplicativ, de aceea va fi multiplicativ

i funciam f, pe care o notm cu g.Conform unei teoreme anterioare, avem

) ) ) )) ) ) )),..1....1 212111

ad

kkk

kpgpgpgpgpgpgdg aa

undek

kpppaaaa = ...21 21 .

Utiliznd acum c g(p) = - f(p) i g(ps) = 0 pentru s > 1 i p prim, obinemegalitatea din enun.

Cazuri particulare:1. Pentru f(a) = 1, "aN*, egalitatea din teorema anterioar devine:

)

=

>

=

1dac,1

1dac,0a

ad

ad

m

2. Pentru f(a) = a1

," aN*, egalitatea din teorema anterioar devine:

( )

=

>

-

-

-=

1dac1

1dac1

11

11

121

a,

a,p

...pp

d

dk

ad.

Are loc i urmtoarea:


36/90


Propoziie:(formula de inversiune a lui Moebius)Fie (G, +) grup abelian i f, g :N*G.

Atunci( ) ( )= nd dfng | , "nN* ( ) ( ) = d|n dgdnnf ,"nN*.

(n scriere multiplicativ, pentru (G, ),

( ) ( ) ( ) ( ) "="=

d|n

d

n

d|n

*n,dgnf*n,dfng NN)

Demonstraie:

se demonstreaz n mod analog folosind faptul c td i dn tn i td i

t

n

t

d

.

n ambele situaii s-a inut cont c)

=

=

.n,

n,d

d|n 2dac0

1dac1

) ) )

) )

) ) )

=

=

=

=

=

t|n

t

nd'|

t

nd'|

t|n

d|nt|dd|n t|dd|n

nftfd'tfd'

tfd

ntf

d

ndg

d

n


37/90


CAPITOLUL IIICONGRUENE

III.1. Noiuni i rezultate introductiveIII.1.1 Inelul claselor de resturi modulo n

Fie n N, n >1. Pe inelul Z al numerelor ntregi definim urmtoarea relaiebinar, numitcongruena modulo n:dac a, bZ, spunem c a este congruent cu b modulo n i scriem a b (mod n) dacn(a - b).

Vom mai nota relaia de congruen modulo n prinn (atunci cnd n nu se deducedin context).Aceast relaie binar este o relaie de echivalen, deoarece:1. "aZ, avem n(a a), deci aa (mod n) 2. dac a, bZ, aa nct ab (mod n), adic n(a b), atunci n-(a b) sau,altfel spus, n(b a), adic ba (mod n)3. dac a, b, cZ, aa nct ab (mod n) i bc (mod n),

atunci n(a b) i n(b c), de unde n(a b) + (b c), adic n(a c), prin urmare ac (mod n).

Pentru aZ, vom nota cu ( ){ }nbaZba mod = clasa de echivalen a lui a,

(va fi numitclas de resturi modulo n). Mulimea factor, { }

ZaaZn

= , o vom nota

cuZn.

Dac ab(mod n) vom spune c a i b suntdistincte modulo n.Observaie:1. Pentru n = 0, avem ab (mod 0)0(a b)a = b deci," aZ, avem

{ }aa= i atunci mulimea factor0

Z este echipotent (n bijecie) cuZ.

2. Pentru n = 1, avem ab (mod 1)1(a b), ceea ce are loc pentru orice a,b

Z. Deci," aZ, Za= , de unde rezult c mulimea factor1

Z este echipotent (n

bijecie) cu orice mulime format dintr-un singur element.S considerm, n cele ce urmeaz, n N, n > 1. Dac a,b Z, din teorema

mpririi cu rest pentru numere ntregi, avem:a = nq1 + r1, unde 0r1 < n

b = nq2 + r2, unde 0r2 < n.De aici, se obine a b = n (q1 q2) + (r1 r2) i, deci avem n(a b)n(r1

r2). Pe de alt parte, 0 r1 r2< n, deci n(r1 r2)r1 = r2.Aadar, dac a,bZ, atunci ab (mod n) dac i numai dac a i b dau acelai

rest la mprirea cu n.


38/90


Deci, dac aZ, atunci a = nq + r, unde 0 r < n i deci n(a r), adic a r(mod n), de unde ra = . n plus, s remarcm c dac 0 r1 < n i 0 r2 < n cu r1 r2,

atunci r1r2 (mod n) i deci 21 rr .Prin urmare, mulimea claselor de resturi modulo n este :

-= 1,...,1,0 nnZ

.Pe aceast mulime putem defini operaiile de adunare i nmulire astfel:

+=

+

baba i

=

baba pentru orice

nZba , .Cele dou operaii nu depind de alegerea reprezentanilor.ntr-adevr, dac ' aa= i ' ba= , adic n(a a) i n(b b), atunci n(a + b)

(a + b), deci

+=

+ '' baba

.Rezult c adunarea este bine definit.Pentru verificarea faptului c nmulirea este bine definit, considerm ' aa= ,

' bb= , de unde rezult c$k, lZ, aa nct a = a + kn i b = b + ln. Avem ab = ab

+ n (al + kb + kln), de unde n(ab ab), deci=

baba .

Pe baza proprietilor adunrii i nmulirii numerelor ntregi, rezult c pentruorice

nZcba ,, , au loc egalitile:

cbacba ++=++abba +=+

aaa 00 =+=+( ) ( )

0 =+-=-+ aaaa

cbacba =

cabacba +=+

cbcacba +=+

aaa 11 ==De aici rezult urmtoarea :

Teorem: Mulimea Zn = {

-1,......,1,0 n } a claselor de resturi modulo n,nzestrat cu operaiile de adunare i nmulire a claselor de resturi formeaz un inelunitar i comutativ.

Propoziie:O clas de resturi a Zn este inversabil n inelulZn dac i numaidac (a, n)=1.

Demonstraie: Dac a este inversabil nZn , atunci exist bZn, aa nct

ab =1 , adic n | (ab-1), de unde$kZ, nct ab 1 = nk.Deci ab + n(-k)=1, de unde rezult, n baza proprietilor celui mai mare divizor

comun a dou numere ntregi, c (a, n) = 1.


39/90


Dac (a, n) = 1, atunci $ h, k Z, aa nct ah + nk = 1, de undehaknhankah 1 =+=+= adic a este element inversabil al luiZn.

Vom nota U(Zn) = { a Zn| (a, n)=1}.Corolar: Urmtoarele afirmaii sunt echivalente:1. Zn este domeniu de integritate2. n este numr prim3. Zn este corp comutativ.Demonstraie:1 2. Dac n nu ar fi numr prim, atunci ar exista h, k N, 1 1,3n=M8+3 deci 4 divide 1n+2n+3n+4n. Cum pentru n impar a+ban+bn rezult c 51n+4n

i 52n+3n deci 51n+2n+3n+4n . Deci 201n+2n+3n+4npentru n impar i n>1Exerciiul 5:Numrul 1919+6969 se divide cu 44Soluie: Fie n=1919+6969=1919+1+6969-1=(1919+1)+( 6969-1). Cum pentru n impara+ban+bn i 1919+1=1919+119 i se divide cu 19+1=20=45. Analog 6969-1 se divide cu69-1=68=417, deci n se divide cu 4Dar n=1919+6969=1919+319+6969-369-319+369=(1919+319)+( 6969-369)+( -319+369)

Cum 1919+319 se divide cu 19+3=22=112, 6969-369 se divide cu 69-3=66=116 iar369-319=319(350-1)= 319((35)10-1)= 319(24310-1) dar 24310-1 se divide cu 243-1=242=1122.Deci n de divide cu 11. Am demonstrat c n se divide cu 44.Exerciiul 6:(Problema lui Diofant) S se gseasc trei numere ntregi n progresiearitmetic, astfel nct suma oricror dou dintre ele s fie un ptrat perfect.Soluie: (dup A. Korselt) Fie a-d,a,a+d cele trei numere n progresie aritmetic. Rezultc a-d+a=2a-d=r2, a-d+a+d=2a=t2, a+a+d=2a+d=u2, unde r,t,u sunt numere ntregi.

r2+u2=2a-d+2a+d=22a=2 t2, de unde rezult (r+u)2+(r-u)2=(2t)2.Deci r+u, r-u i 2t sunt rdcinile ecuatiei pitagorice x2+y2=z2.


86/90


Avem r+u=m(p2-q2), r-u=2mp i 2t=m(p2+q2) din care se deduce uor expresiilenumerelor cutate: (r+u)(r-u)=r2-u2=2m2(p4-q4) dar r2-u2=-2d, atuncid=m2(q4-p4)i

( )

aqqppm

t 2244224

2

2 =++= . Deci numerele sunt:

a-d= ( )42242

28

qqppm

++ - m2(q4-p4)

a= ( )42242

28

qqppm

++

a+d= ( )42242

28

qqppm

++ + m2(q4-p4)

Exerciiul 7:S se gseasc numrul solutiilor ntregi i pozitive ale ecuaiei

-=

1a

x

a

x

Soluie: Fie

-=

1ax

a

x=k, unde k este numr ntreg , k=0,1,2,

Deducem c 11

+

Date post:	01-Mar-2018
Category:	Documents
Upload:	radu-daniel
View:	238 times
Download:	1 times

teoreme_celebre_de_teoria_numerelor.pdf

Documents