375 ARITMETIC I TEORIA NUMERELOR Prof. univ. dr. Ion. D. Ion I. TEOREMA FUNDAMENTAL A ARITMETICII Vom nota cu`mulimea numerelor naturale { } 0,1, 2,..., ,... n = `Dac, a b`,spunemca estemaimicsauegalcub dacexist x` astfel ncta x b + =i, n acest caz, scriema b . Relaia binar definit mai sus este: -reflexiv:a a ,a ` ; -antisimetric;a b ib a implica b = ; -tranzitiv:a b ib c implica c . Aadar, esteorelaiedeordinepe`,cunoscutsubnumelede ordinenatural.Proprietateafundamentalarelaiei este:oricarearfio partenevidAalui`exista A ,astfelncta x ,x A (adic,orice parte nevid a lui` are un prim element). Se spune c este o bun ordine au nc,` este o mulime bine ordonat cu relaia de ordine natural . O alt relaie binar important definit pe`este relaia de divizibilitate. Dacdiasunt dou numere naturale, spunem cddivide peai scriemd a , dacexistunnumrnaturalq ,astfelncta dq = ;sespunenacestcazcdeste divizor al luiasau caeste multiplu ded . Unnumrnatural1 p > esteireductibildacsinguriisidivizorisunt1ip . Unnumrnatural1 p > esteprimdacdinp ab cu, a b`rezult p a saup b .Searatcunnumr1 p > esteprimdacinumaidaceste ireductibil. Daca` ,1 a >i { }i d>1 A d d a = ` , atunciA (pentru c a A ) i dacp A este primul element al luiA, atuncipeste prim. Aadar, orice numr natural1 a >are cel puin un divizor prim. Se poate demonstra acum: Teorema1(teoremafundamentalaaritmeticii). Oricarearfia` , 1 a > ,existnumereleprime 1 2, ,...,np p p (nuneapratdistincte)unic determinate, astfel nct 1 2...na p p p = . Astfel30 2 3 5 a = = , 354 2 3 3 3 2 3 a = = = etc. 376Teorema 2 (teorema lui Euclid). Exist o infinitate de numere prime. nadevr,dacnumrulnumerelorprimeestefinit,fieacestea 12 p = , 23 p = , 35 p = ,, kp .Fienumrul 1 2... 1 1kN p p p = + > .Existunnumr primp , astfel nctp N . Cum{ }1 2, ,...,kp p p p , rezult c 1 2...kp p p p , deci pdivide 1 2... 1kN p p p = . Contradicie! Un rezultat mai general este: Teorema3(Dirichlet).Daca ir suntdounumerenaturaleprime ntre ele (adic nu admit un divizor comun1 d > ), atunci n progresia aritmetic , , 2 ,... ,... a a r a r a nr + + +exist o infinitate de numere prime distincte. nirul1, 2,..., ,... n apariianumerelorprimeprezintmarineregulariti. Exist numere prime gemene, adic de forma, 2 k k + , de exemplu 5 i 7 sau 17 i 19.Pedealtparte,pentruorice *n` existn numerenaturaleconsecutive care nu sunt prime, anume: ! 2, ! 3,..., ! m m m m + + + , cu1 m n = + . Informaiiasupradistribuieinumerelorprimenirul1, 2,..., ,... n al numerelor naturale sunt date de: Teorema 4 (conjunctura Bertrand). Oricare ar fi2 n exist un numr primp , astfel nct2 n p n < < . Teorema5(anumruluiprim).Dac( ) n estenumrulnumerelor primep n , atunci ( )lim 1lnnnnn=| | |\ . II. CONGRUENE Fie *m` .Dac, a b] spunemca estecongruentcub modulo mdaca b sedivideprinmiscriem( ) mod a b m .Seobservc congruenamodulomestereflexiv,simetricitranzitiv,deciorelaiede echivalen pe]. Dac( ) mod a b m i( ) mod c d m , atunci ( ) mod a c b d m + + , ( ) mod ac bd m . Exemplu.( ) 10 1 mod3 i deci( ) 10 1 mod3k= ,k ` . 377Dac 11 1 0 1 1 0... 10 10 ... 10n nn n n nN a a a a a a a a = = + + +este o reprezentare a numruluiNn baza 10, atunci ( )11 1 0 1 1 010 10 ... 10 ... mod3n nn n n na a a a a a a a + + + + + +deciN estedivizibilcu3dacinumaidacsumacifrelorsalezecimaleeste divizibil cu 3 (criteriul de divizibilitate cu 3). Dac *m` , atunci( ) m este prin definiie ( ){ }1 ,astfel nct, 1 card a a m a m = `unde( ) , a m estec.m.m.d.c.alluia im.Astfel,( ) 4 2 = ,( ) 8 4 = , ( ) 1 p p = dacpeste numr prim. n inelul n{ } 0,1,..., 1mm = ]al claselor de resturi modulom o clas aesteinversabildacinumaidac( ) , 1 a m = i,deci,grupul( )mU] al elementelorinversabiledininelul m] areordinul( ) m .nparticular,rezultc ( ) 1ma= ,( )ma U ] . Aadar: Teorema 1 (Euler). Fie *m`ia] , astfel nct( ) , 1 a m = . Atunci, ( )( ) 1 modma m . Teorema 2 (Fermat). Fiepun numr prim ia] , astfel nct| p a/. Atunci, ( )11 modpa p . Dac, a b]i1 m > , atunci ( ) mod ax b m (1) este numit congruen liniar n necunoscutax . Rezolvarea congruenei liniare (1) revine la a determina valorile din] pentrux , astfel nct congruena (1) s fie verificat. Dou soluii 1 2, x x ] ale congruenei (1) sunt distincte modulom dac ( )1 2mod x x m / . Teorema 3. Fiedc.m.m.d.c. al luiaim. 1.Dac| d b/, atunci congruena (1) nu are soluii. 2.Dac| d bi 1a da = , 1m dm = , 1b db = ,atunci ( ) 110 1 1mx b a = esteo soluie particular pentru congruena (1) i aceasta aredsoluii distincte modulom, anume ( )0 0 1 0 1 0 1, , 2 ,..., 1 x x m x m x d m + + + . 378Exemplu.Fiecongruenaliniar( ) 6 9 mod15 x .Cum( ) 6,15 3 = i 3| 9,rezultccongruena( ) 6 9 mod15 x aresoluia ( )303 2 24 4 mod5 x = = i,deci,4,4 5 9 + = ,4 10 14 + = suntsoluii distincte modulo 15 ale congruenei( ) 6 9 mod15 x . Teorema4(lemachinezaresturilor).Fie *1 2, ,...,rm m m ` ,astfel nct ( ), 1i jm m =oricare ar fii j . Atunci, sistemul de congruene liniare ( )( )( )1 12 2modmodmodr rx b mx b mx b m """""" are soluie unic modulo 1 2...rm mm m = . Dac 11...llrrm p p = estedescompunerealuimcaprodusdeputeride numereprimedistinctei( ) | |f X X ] ,atunci,cum ( ), 1ll jii jp p = pentru i j ,congruenapolinomial( ) ( ) 0 mod f x m sereducelarezolvarea congruenelor liniare( )( )0 modliif x p folosind lema chinez a resturilor. Deasemenea,rezolvareacongruenei( ) ( )0 modlf x p ,cup numr primi *l ` ,sereducelarezolvareacongruenei( ) ( ) 0 mod f x p iaunor congruene liniare. ncazulncare( ) f x estepolinomdegradul2,atuncicongruena ( ) ( ) 0 mod f x p se reduce la congruena ( )2mod x a p (2) Fie2 m ia] ,astfelnct( ) , 1 a p = .Spunemca esterest ptraticmodulop dacexistx],astfelnct( )2mod x a p ,adic congruena(2)admitesoluie.ncazcontrar,spunemca nuesterestptratic modulop . 379Dac2 p > esteprimia] ,astfelnct( ) , 1 a p = ,atuncisimbolul Legendre ap| | |\ . este definit prin 1 dac este rest ptratic modulo 1 dac nu este rest ptratic modulo defa paa p p| | = |\ . . Dac2 p > esteunnumrprimi, a b] ,astfelnct ( ) ( ) , , 1 a p b p = = , atunci (i)dac( ) mod a b p , atunci a bp p| | | |= ||\ . \ .; (ii) 21ap| |= |\ .; (iii)( )12modpaa pp| ||\ .; (iv)( )1211pp| | = |\ .; (v)( )21821pp| | = |\ .. Rezultatul fundamental este legea reciprocitii ptratice. Teorema5(legeareciprocitiiptratice).Dacp iq suntdou numere prime impare i distincte, atunci ( )1 12 21p qp qq p | || | = | |\ .\ .. Exerciiu. S se precizeze dac( )22223 mod3779 x are soluii n]. Se observ c numrul3779 p =este prim i numrul2223 a =se scrie 23 13 19 a = . Avem 2 22223 3 13 19 3 13 193779 3779 3779 3779 3779| | | | | | | || |= = |||| |\ . \ .\ .\ . \ . Aplicndlegeareciprocitiiptratice,scrissubforma ( )1 12 21p qp qq p | | | |= ||\ . \ ., avem ( )212 37782 213 3779 9 31 13779 13 13 13 | || | | | | |= = = = ||||\ . \ . \ .\ . 380pentru c( ) 3779 9 mod13 . De asemenea,( ) 3779 2 mod19 , deci ( ) ( ) ( )218 3778 18 19 12 2 2 819 3779 2 1 21 1 1 13779 19 19 19 19 | | | | | | | || |= = = = = |||| |\ . \ . \ . \ .\ .. Aadar, 222313779| | = |\ . i, deci, congruena( )22223 mod3779 x nu are soluii. Observaie.Ometodcatastrofaldinpunctdevederealvolumului calculului ce trebuie efectuat este s verificm succesiv c numerele0 x = ,1 x = , 2 x = , ,3778 x =nu sunt soluii ale congruenei( )22223 mod3779 x . III. FRACII CONTINUE Dac 0 1, ,...,na a asunt numere reale, astfel nct0ia > ,0 i n , atunci numrul 0123111111nnaaaaaa++++++"% senoteazcu | |0 1 2; , ,...,na a a a isenumetefraciecontinufinit.Dac,n plus, ia ] ,0 i n ,atunci | |0 1 2; , ,...,na a a a senumetefraciecontinu simpl finit. (fcsf). Orice fcsf | |0 1 2; , ,...,na a a aeste un numr raional. Astfel, | |1 552;3, 2, 3 21243123= + =++. Reciproc,oricenumrraionalsepoatereprezentacaofcsf.Astfel,dat numrul raional 5524, efectund algoritmul lui Euclid pentru 55 i 24, avem 55 7 155 24 2 7 2 22424 247= + = + = + , 38124 3 124 7 3 3 3 377 73= + = + = + , 7 17 3 2 1 23 3= + = + , de unde | |55 12 2;3, 2, 31243123= + =++. Dac 0 1 2, , ,..., ,...na a a a esteunirinfinitdenumererealecu0ia > , 0 i > , atunci expresia 01211aaa+++"% se numete fracie continu infinit (fci) i se noteaz | |0 1 2; , ,..., ,...nC a a a a = . Dac,nplus, ia ] ,0 i ,atunciC senumetefraciecontinu simpl infinit (fcsi). Dac | |0 1 2; , ,..., ,...nC a a a a = esteofci,atuncinumrulreal | |0 1 2; , ,...,n nC a a a a =se numete a anconvergen a luiC . Dac existlimnnC = , spunem ceste valoarea fciC . Reciproc, dat un numr real , atunci, dac exist fciCastfel nctlimnnC = , spunem cCreprezint pe . Prin inducie se poate demonstra: Lema 1. Fie fci | |0 1 2; , ,..., ,...nC a a a a = , 0 0p a = , 01 q = , 1 1 01 p a a = + , 1 1q a = ,iarpentru2 n , 1 2 n n n np a p p = + , 1 2 n n n nq a q q = + ,atunci nnnpCq= , oricare ar fi0 n . 382Corolar 1. Fie fci | |0 1 2; , ,..., ,...nC a a a a = . Atunci, (1)pentru1 n ( )11 11nn n n np q p q = , ( )1111nn nn nC Cq q = , (2)Pentru2 n ( )12 21nn n n n np q p q a = , ( )1221nnn nn naC Cq q =Corolar 2. Dac | |0 1 2; , ,..., ,...nC a a a a =este o fci, atunci 0 2 2 2 1 3 1... ... ...s tC C C C C C+< < < < < < < < , oricare ar fi, s t `. Teorem.Fie | |0 1 2; , ,..., ,...nC a a a a = ofcsi.Atunci,irul( )0nnCeste convergent. Demonstraie.Seobservcirul( )0nnqesteunirstrictcresctorde numere naturale. irurile( )20ssC i( )2 10ttC+ sunt convergente (corolar 2.). Cum 2 1 22 2 110n nn nC Cq q++ = , rezult c 2 2 1lim lim lims t ns t nC C C+ = = . Observaie.Fie | |0 1 2; , ,..., ,...nC a a a a = ofcsiilimnnC = .Definim 0 = , | |10 01 =, | |21 11 =, , atunci | |n na = ,0 n . Exerciiul1.Fie2 = ,ssedeterminefcsi | |0 1 2; , ,..., ,...nC a a a a = , astfel nctlim 2nnC= . Conform observaiei precedente, avem 02 1 a (= = , 112 1 22 1a ( (= = + = ( , 21 12 1 2,2 1 2 2 1a (( (= = = + = (( + , de unde | |1; 2, 2,..., 2,... C = . Exerciiul 2. S se determine o aproximare raional a lui2cu o eraore inferioar lui 1100. Aplic lema 1 fcsi | |1; 2, 2,..., 2,... C =care reprezint pe2 . 383n 01234 np 1371741 nq 1251229 nnnpCq=11 32 75 1712 4129 Cum ( )34 31112 29 100C C = > ,avem 3 41100C C < .icum 4 32 C C < < , rezult c 4411, 41...29C = =este aproximarea raional dorit. BIBLIOGRAFIE 1.HardyandWright,AnIntroductiontotheTheoryofNumbers,Oxford Univ.Press. 2.I.D.Ion,C.Nia,Elementedearitmeticcuaplicaiintehnicidecalcul, Ed.Tehnic, Bucureti, 1978. 3.V.Alexandru,N.Goonoi,Elementedeteorianumerelor,Tipografia Universitii Bucureti, 1999. 4.Allenby and Refern, Introducion to Number Theory with Computing, London, 1989.