Lect. univ. Stelian Corneliu ANDRONESCU Absolvent: Ioan-Andrei POPESCU { 2017 { 2 Cuprins 1MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE,… [618050]

Byadmin

UNIVERSITATEA DIN PITES TI
FACULTATEA DE S TIINT  E, EDUCAT  IE FIZIC A S I INFORMATIC A
LUCRARE DE LICENT  A
FUNCT II ARITMETICE
Coordonator  stiint i c:
Lect. univ. Stelian Corneliu ANDRONESCU
Absolvent: [anonimizat]-Andrei POPESCU
{ 2017 {

2

Cuprins
1MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE
CU REST 5
1.1 Mult imea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Legi de compozit ie ^ n mult imea N. . . . . . . . . . . . . . . . . . 6
1.3 Relat ia de ordine natural a pe mult imea N. . . . . . . . . . . . . 6
1.4 A doua form a a principiului induct iei . . . . . . . . . . . . . . . . 8
1.5 Propriet at i ale lui N. . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Numere ^ ntregi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Relat ia de ordine pe mult imea numerelor ^ ntregi . . . . . . . . . 12
1.8 ^Inmult irea numerelor ^ ntregi . . . . . . . . . . . . . . . . . . . . . 12
1.9 Modulul unui num ar ^ ntreg . . . . . . . . . . . . . . . . . . . . . 13
1.10 Relat ia de divizibilitate pe mult imea numerelor ^ ntregi . . . . . . 13
1.11 Teorema de ^ mp art ire cu rest ^ n Z. . . . . . . . . . . . . . . . . 13
1.12 Algoritmul lui Euclid . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.13 Numere perfecte, numere mersenne, numere prime Fermat . . . . 16
1.14 C^ ateva observat ii asupra  sirului numerelor prime . . . . . . . . . 18
1.15 Ciurul lui Eratostene . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.16 Rezultate ale lui L. Euler despre  sirul numerelor prime . . . . . . 19
1.17 Funct ii aritmetice . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.17.1 Funct ia lu M obius . . . . . . . . . . . . . . . . . . . . . . 21
1.17.2 Propriet at i ale funct iei lui M obius . . . . . . . . . . . . . 22
1.17.3 Indicatorul lui Euler . . . . . . . . . . . . . . . . . . . . . 22
1.18 Alte considerat ii despre funct iile aritmetice . . . . . . . . . . . . 23
1.19 Inegalit at ile lui Ceb^ a sev . . . . . . . . . . . . . . . . . . . . . . . 24
2 Not iuni generale 27
2.1 Divizibilitatea pe N. . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Cel mai mare divizor comun . . . . . . . . . . . . . . . . . . . . . 29
2.3 Cel mai mic multiplu comun . . . . . . . . . . . . . . . . . . . . . 32
2.4 Criterii de divizibilitate pentru numere scrise ^ n baza 10 . . . . . 32
2.5 Divizibilitatea pe Z. . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Numere prime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Funct ii aritmetice 39
3.1 De nit ii  si exemple . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Funct ia lui M obius . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Indicatorul lui Euler . . . . . . . . . . . . . . . . . . . . . . . . . 40
3

4 CUPRINS

Capitolul 1
MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU
REST
1.1 Mult imea
Mult imea numerelor naturale este obiectul fundamental de studiu pentru arit-
metic a  si pentru ^ ntreaga matematic a. Prima prezentare axiomatic a a mult imii
Na fost dat a ^ n anul 1891 de matematicianul italian G. Peano.
De nit ia 1.1.1. Mult imea numerelor naturale este un triplet ( N;0; s), undeN
este o mult ime, iar seste o aplicat ie astfel^ nc^ at s a e satisf acute axiomele lui Peano
:
P1) 0 2N
P2)s:N!Nn f0g
P3) Dac a PNare propriet at ile
a) 02P
b)x2P)s(x)2P
atunciP=N:
Elementul 0 se nume ste zero sauelement init ial ^ n mult imea N:Funt ia s
se nume ste funt ie succesor . Elementele mult imii Nse numesc numere naturale ,
iar pentru ecare num ar natural n, num arul s(n) se nume ste succesorul luin.
Succesorul lui 0 se noteaz a cu 1.
Axioma P2) spune c a elementul 0 nu este succesorul nici unui num ar natural,
iar dac a dou a numere naturale au acela si succesor, atunci ele coincid.
Axioma P3) se nume ste principiul induct iei matematice :
Se poate ar ata urm atorul fapt:
Dac a (M; m0; t) este un triplet ce ^ ndepline ste condit iile P1,P2,P3, atunci
exist a o unic a biject ie :N!Mastfel ^ nc^ at (0) = m0, iar diagrama s a e
comutativ a(adic a ◦s=t◦).
Existent a unui triplet ( N;0; s) care s a satisfac a P1,P2,P3 este o axiom a a
teoriei mult imilor (a se vedea spre exemplu: I. Bucur, Capitole speciale de alegbr a ,
Editura Academiei, 1980). Folosind principiul induct iei, se de nesc pe Noperat iile
de adunare  si ^ nmult ire.
5

6CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
1.2 Legi de compozit ie ^ n mult imea N
A) Adunarea este o lege de compozit ie φ:NN!N, cuφ(x; y)not=x+y
astfel ^ nc^ at:
A1) x+ 0 = x;(8)x2N;
A2) x+s(y) =s(x+y);(8)x; y2N:
Observat ia 1.2.1. Deoarece x+ 1 = s(x), A2) se reformuleaz a prin
x+ (y+ 1) = ( x+y) + 1 ;(8)x; y2N:
I)^Inmult irea este o lege de compozit ie : N!N, cu ( x; y) =xy=xy
astfel ^ nc^ at :
I1)x0 = 0 ;(8)x2N:
I2)xs(y) =xy+x;(8)x; y2N:
Altfel spus, x(y+ 1) = xy+x;(8)x; y2N:
Se constat a(folosind P3) c a φ si  sunt de nite peste tot ^ n N. Se poate demon-
stra de asemenea prin induct ie c a φ si  sunt determinate de propriet at ile
ment ionate A1, A2, I1, I2.
Propozit ia 1.2.2. I. a) (N;+)este monoid comutativ cu proprietatea de
simpli care (x+a=x+b)a=b);
b)x+y= 0)x=y= 0;
II. a) (N;)este monoid comutativ;
b) 1 este element neutru;
c) dac a xy=xz six̸= 0, atunci y=z(proprietatea de simpli care).
III. ^Inmult irea este distributiv a fat  a de adunare: x(y+z) =xy+xz, pentru
orice x; y; z 2N:
1.3 Relat ia de ordine natural a pe mult imea N
De nit ia 1.3.1. Fiea; b2N. Spunem c a abdac a exist a x2Nastfel ^ nc^ at
a+x=b:
Propozit ia 1.3.2. Relat ia ""este re
exiv a, antisimetric a  si tranzitiv a (deci
este o relat ie de ordine pe mult imea N).
Demonstrat ie. Pentru orice a2Navem a=a+0, astfel c a re
exivitatea relat iei
"" este veri cat a.
Dac a pentru numere naturale a sibastfel ^ nc^ at ab siba, atunci
exist a numerele naturale x siyastfel ^ nc^ at a+x=b sib+y=a. Obt inem
a=b+y= (a+x)+y=a+(x+y), de unde, conform propriet at ii de simpli care,
rezult a 0 = x+y, iar de aici x=y= 0, astfel c a a=b. Prin urmare relat ia
"" este antisimetric a.
Fie acum numerele naturale a; b; c astfel ^ nc^ at ab sibc. Atunci exist a
x; y2Na sa ^ nc^ at b=a+x sic=b+y. De aici rezult a c=b+y= (a+x)+y=
a+ (x+y) astfel c a ac, ceea ce dovede ste tranzitivitatea relat iei " ":
Numim " " relat ie de ordine natural a pe N:

1.3. RELAT IA DE ORDINE NATURAL A PE MULT IMEA N 7
De nit ia 1.3.3. i) Dac a ab sia̸=b, atunci vom nota a < b . De
asemenea, se poate nota ba^ n loc de ab sib > a ^ n loc de a < b:
ii) Dac a ab sia+x=b, atunci not am x=ba:
Propozit ia 1.3.4. Pentru orice a; b; c2Nabeste echivalent cu a+cb+c,
iar dac a c̸= 0; ab,acbc:
Teorema 1.3.5. (N;)este o mult ime bine ordonat a(orice submult ime nevid a
are un cel mai mic element).
Demonstrat ie. FieAN; A̸=∅. Consider am mult imea
P=fx2Njxapentru orice a2Ag:
Este clar c a 0 2P. Dac a pentru orice x2Pam avea s(x)2P, atunci
conform principiului induct iei matematice, ar rezulta P=N si aleg^ and un
element a2A, vom avea s(a)2P, astfel c a s(a) =a+ 1a, ceea ce este
imposibil. Prin urmare exist a un element 2Pastfel ^ nc^ at s( )̸2P. Vom
ar ata c a 2A.^Intr-adev ar, dac a ̸2A, atunci oricare ar a2Aavem
< a (pentru c a 2P), deci s( )a, oricare ar a2A, adic a s( )2P, ceea
ce este fals. Prin urmare 2A si cum 2P, rezult a = min A:
Corolarul 1.3.6. (N;) este o mult ime total ordonat a (oricare dou a elemente
sunt comparabile).
Demonstrat ie. Fiea; b2N si e A=fa; bg. Cum A̸=∅, exist a min A. Dac a
minA=a, atunci avem ab, iar dac a min A=b, atunci avem ba.
Corolarul 1.3.7. Nu exist a  siruri strict descesc atoare formate cu numere nat-
urale(altfel spus, un  sir descrec ator de numere naturale este stat ionar).
Observat ia 1.3.8. Prin de nit ie b̸=a^ nseamn a ab:
De nit ia 1.3.9. Numim segment ^ n mult imea N si not am 1; ndef=fx2Nj1
xng:^In particular, 1;0 =∅:
De nit ia 1.3.10. Spunem c a mult imea Aeste nit a  si are nelemente, dac a
exist a o biject ie f:A!1; n:
Notat ia 1.3.11. Not am jAjsauCardA clasa de echivalent  a cardinal a a mult imii
A(^ n cazul nostru, num arul de elemente ale lui A).
^In continuare vom folosi unele propriet at i ale mult imilor nite.
Observat ia 1.3.12. i) Dac a BA siAeste nit a, atunci Beste nit a  si
avem A=B, jAj=jBj:
ii) Dac a A siBsunt mult imi nite, atunci A[Beste nit a  si avem jAj+jBj=
jA[Bj+jA\Bj:
Observat ia 1.3.13. 1) a) O consecint  a a propriet at ii i) este urm atoarea:
Dac a f:A! Beste o funct ie, iar A siBsunt mult imi nite
cujAj=jBj, atunci feste injectiv a ,feste surjectiv a ,feste
bijectiv a.

8CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
b) Proprietatea ii) admite urm atoarea generalizare (demonstrat ia se face
prin induct ie dup a n):
FieA1; A2; :::; A nmult imi nite. Atuncin∪
i=1Aieste nit a  si avem:
n∪
i=1Ai =n∑
i=1 Ai ∑
1i<jn Ai\Aj +∑
1i<j<k n Ai\Aj\Ak +:::+(1)n n∩
i=1Ai :
(egalitate cunoscut a sub numele de "principiul includerii  si exclud-
erii").
2) Este evident c a mult imea numerelor naturale este in nit a(nu este nit a).
Mai general, o mult ime Meste in nit a dac a  si numai dac a exist a o funct ie
injectiv a i:N!M. Se poate ar ata c a o mult ime Meste in nit a dac a
 si numai dac a exist a o funct ie i:M!M; i injectiv a, dar nebijectiv a.
1.4 A doua form a a principiului induct iei
Propozit ia 1.4.1. FiePo submult ime a lui Nav^ and proprietatea:
(x < n )x2P))n2P:
Atunci P=N:
Demonstrat ie. Avem 0 2P, deoarece premiza implicat iei
(x <0)x2P))02P
este adev arat a. Fie A=NP. S a presupunem c a A̸=∅. Conform teoremei
1.3.5, exist a un cel mai mic element aal lui A. Dar prin ipotez a ( x < a )x2
P))a2P, deci a̸2A. Contradict ia obt inut a arat a c a A=∅, deci P=N:
1.5 Propriet at i ale lui N
Teorema 1.5.1 (Teorema ^ mp art irii cu rest ^ n N).Fiea; b2N; b̸= 0.
Atunci exist a q; r2Nastfel ^ nc^ at a=bq+r, cu0r < b .^In plus q sirsunt
unic determinate de a sib.
Demonstrat ie. FieA=ft2N (9)s2N; a=bs+tg. Dat ind c a a=b0 +a;
deducem c a a2A, deci A̸=∅:Conform teoremei 1.3.5 exist a r= min A:Deci
exist a un q2Nastfel c a a=bq+r:Demonstr am c a r < b: Dac a (prin absurd)
am avea br;atunci ar exista u2Nastfel ^ nc^ at r=b+u si am putea scrie
a=bq+b+u=b(q+ 1) + u;de unde u2A si cum u < r (deoarece b̸= 0),
se contrazice minimalitatea lui r^ nA:
Demonstrat ia unicit at ii. S a presupunem c a a=bq1+r1=bq2+r2;curi<
b; i= 1;2  sir1̸=r2:Putem presupune r1< r 2 si atunci rezult a q2< q 1:Acum
putem scrie bq1bq2=r2r1sau
r2r1=b(q1q2); q1q22N(
undeNnot=Nnf0g)
:(1)
Pe de alt a parte avem 0 < r 2r1< b; ceea ce intr a ^ n contradict ie cu relat ia
(1).

1.5. PROPRIET AT I ALE LUI N 9
De nit ia 1.5.2. D^ andu-se numerele naturale a sib, spunem c a adivide bdac a
exist a num arul natural castfel ^ nc^ at b=ac:
Notat ia 1.5.3. Faptul c a " adivide b" se va nota ajbsaub…a, iar c a " anu divide b"
se va nota a̸ jb:
Observat ia 1.5.4. Relat ia "divide" are urm atoarele propriet at i (ale c aror demonstrat ii
le propunem ca exercit iu).
i) este re
exiv a ( aja);
ii) este tranzitiv a (dac a ajb sibjc, atunci ajc);
iii) este antisimetric a(dac a ajb sibja, atunci a=b). Deci relat ia "divide"
este o relat ie de ordine part ial a pe N, ^ n care 1 este prim  si 0 este ultim
element.
iv) Dac a ajbi; i= 1;2; :::; n , atunci a n∑
i=1cibi;(8)ci2N:
De nit ia 1.5.5. Fiep2Nnf0;1g:Spunem c a peste ireductibil dac a dintr-o
relat ie de forma p=abrezult a a= 1 sau b= 1:
Observat ia 1.5.6. Dac a not am aN=fakjk2Ng;atunci ajb,aNbN:
Teorema 1.5.7 (Teorema fundamental a a aritmeticii ). 1. Oricare ar
num arul natural n; n > 1, exist a num arul natural s si numerele ireductibile
p1; :::; p s; s1astfel ^ nc^ at s a avem n=p1ps:
2. Dac a n > 1 sin=p1ps=q1qt, unde (pi)1is;(qj)1jtsunt
numere ireductibile  si p1p2   ps; q1q2   qt, atunci s=t
 sipi=qi, pentru orice i;1is:
Demonstrat ie. Folosim induct ia matematic a. Fie n= 2 = s(1) = 1+1 :Num arul
2 este ireductibil, deci a rmat iile sunt adev arate pentru acesta.
Fien >2. Dac a num arul neste ireductibil, atunci concluzia este adev arat a.
Dac a este reductibil, o factorizare a sa are forma n=ab; a; b 2N, unde 1 < a <
b < n:
S a presupunem c a a rmat ia 1. din enunt  nu este adev arat a, iar n0este
cel mai mic num ar din Nnf0;1gcare nu se descompune ^ n produs de factori
ireductibili. Avem n0=ab, cu 1 < ab < n 0, iar a sibse descompun
^ n produs de factori ireductibili ( ind strict mai mici ca n0). Deci  si n0se
descompune ^ n produs de factori ireductibili, ceea ce ^ ns a contravine alegerii
f acute.
S a presupunem c a a rmat ia 2. din enunt  este fals a. Fie n02Nnf0;1gcel
mai mic num ar care admite dou a descompuneri distincte ^ n produs de factori
ireductibili. Fie pcel mai mic divizor ireductibil al lui n0 sin0=p1p2ps; s
2; p1p2:::ps; p1=po descompunere a lui n0^ n care apare p si e
n0=q1q2:::qtcuq1q2:::qt, o descompunere a lui n0^ n factori
ireductibili, diferit a de prima(desigur n0este reductibil).
Dac a p1=q1, atunci se obt in dou a descompuneri pentru un num ar mai mic
dec^ at n0(1< p 2:::ps=q2:::qt< n 0)  si se contrazice minimalitatea lui n0:
^In cazul p=p1< q 1consider am num arul
n1=n0p1p2:::qt=p1p2:::psp1q2:::qt:

10CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Observ am c a operat ia are sens deoarece n0=q1q2:::qt> p 1q2:::qt, dat ind
c ap1< q 1.^In plus avem 1 < n 1< n 0 sip1jn1. Din alegerea lui n0rezult a c a
n1se descompune ^ n produs de factori ireductibili  si orice dou a descompuneri
coincid. Dar relat ia n1=p1(p2:::p2q2:::qt) arat a c a exist a o factorizare a lui
n1^ n produs de factori ireductibili ^ ntre care se a
 a  si q1. Pe de alt a parte avem
n1=n0p1q2:::qt=q1q2:::qtp1q2:::qt= (q1p1)q2:::qt
iarp=p1̸ j(q1p1) (pentru c a din p1j(q1p1) ar rezulta p1jq1 si cum q1este
ireductibil am avea p1=q1, ceea ce nu se poate). Avem chiar p1< q j;(8)j
 si deci exist a o factorizare a lui n1care nu cont ine ^ ntre termenii s ai factorul
p=p1. A sadar s-au pus ^ n ecvident  a dou a descompuneri distincte ale lui n1.
Darn1< n 0 si astfel se contrazice minimalitatea lui n0.
Demonstrat ia de mai sus a fost dat a de matematicianul german Zermelo.
Corolarul 1.5.8. Oricare ar num arul natural n > 1 exist a numerele ire-
ductibile distincte (dac a s2)p1; p2; :::; p s si numerele naturale nenule 1; 2; :::; s
astfel ^ nc^ at
n=p 1
1p 2
2p s
s:(1)
^In plus, dac a n=p 1
1p 2
2p ss=q 1
1q 2
2q t
t, unde q1; q2; :::; q tsunt numere
ireductibile distincte, dar i1, atunci (modulo o permutare a indicilor) avem
s=t; pi=qi; i= i, pentru orice 1 is:
De nit ia 1.5.9. Descompunerea unui num ar natural ^ n forma (1) se nume ste
scrierea ^ n form a canonic a saudescompunerea canonic a .
De nit ia 1.5.10. Spunem c a un num ar natural peste prim dac a p >1  si din
pjabrezult a pjasaupjb:
Corolarul 1.5.11. Dac a p2N, atunci peste ireductibil ,peste prim.
De nit ia 1.5.12. a) Fie a; b2N. Spunem c a deste cel mai mare divizor
comun (c. m. m. d. c) pentru numerele a sibdac a  si numai dac a sunt
^ ndeplinite condit iile:
1)dja sidjb; 2)ja sijb)jd:
b) Dac a ( a; b) = 1, spunem c a numerele a sibsunt relativ prime .
c) Spunem c a meste cel mai mic multiplu comun (c. m. m. m. c. ) pentru
numerele a sibdac a  si numai dac a sunt ^ ndeplinite condit iile:
1)ajm sibjm; 2)ajm′ sibjm′)mjm′:
Observat ia 1.5.13. Condit iile din de nit ie determin a ^ n mod unic c. m. m.
d. c.  si c. m. m. m. c. ale numerelor a sib. Not am d= (a; b)  sim= [a; b].
Desigur, avem ( a;1) = 1  si [ a;1] = a, iar ( a;0) = a;[a;0] = 0 pentru orice a2N:
Corolarul 1.5.14. Fiea sibdou a numere naturale strict mai mari ca 1 ; a=
p 1
1:::p ss; b=p 1
1:::p ss, descompunerile canonice. Atunci exist a d= (a; b)  si
m= [a; b]  si avem d=pmin( 1; 1)
1 :::pmin( s; s)
s ; m=pmax( 1; 1)
1 :::pmax( s; s)
s :

1.6. NUMERE ^INTREGI 11
Observat ia 1.5.15. Avem md=ab(pentru c a min( i; i) + max( i; i) =
i+ i).
Observat ia 1.5.16. 1. Din observat ia 1.5.14 rezult a c a ^ n mult imea part ial
ordonat a ( N;j) (^ n care consider am " amai mare dec^ at " b" dac a ajb), pen-
tru orice a; bexist a max fa; bg= (a; b)  si min fa; bg= [a; b]. Prin urmare
(N;j) este o latice (av^ and ca prim element pe 0  si ca ultim element pe 1).
2. Se constat a c a avem aN\bN= [a; b]N:
1.6 Numere ^ ntregi
Am v azut c a ( N;+) este un monoid comutativ cu proprietatea de simpli care.
Consider am pe NNrelat ia " " de nit a astfel:
(a; b)(c; d)def,a+d=b+c:
Propozit ia 1.6.1. Relat ia " " are propriet at ile:
1. este re
exiv a, simetric a  si tranzitiv a.
2. dac a ab, atunci (a; b)(ab;0):
3.(a; a)(0;0):
Demonstrat ie. Este evident a.
FieZ=NN=={
[(a; b) a; b2N}
:PeZintroducem operat ia "+" prin:
\(a1; b1) +\(a2; b2)def=\ (a1+a2; b1+b2):
Operat ia este bine de nit a: dac a ( a1; b1)(c1; d1)  si ( a2; b2)(c2; d2),
atunci avem  si ( a1+a2; b1+b2)(c1+c2; d1+d2):
Se veri c a u sor c a ( Z;+) este monoid comutativ. Elementul neutru este
[(0;0)not= 0;[(a; a);(8)a2N:
Propozit ia 1.6.2. (Z;+)este grup comutativ.
Demonstrat ie. Fie =[(a; b)  si ′=[(b; a). (De observat c a ′este bine deter-
minat). Atunci + ′=\(a+b; a+b) =[(0;0) = 0. Deci ′=[(b; a) este opusul
lui =[(a; b) ^ n (Z;+). Not am ′= :
Observat ia 1.6.3. ^InZecuat ia a+x=bare solut ie unic a.
x=b+ (a)not=ba:
Propozit ia 1.6.4. i:N!Z; i(n) =[(n;0)este mor sm injectiv de monoizi.
Demonstrat ie. S a observ am c a aplicat ia ieste bine de nit a.
1)i(n1+n2) =i(n1)+i(n2);
2) dac a i(n) =i(m), atunci [(n;0) =\(m;0), de unde n=m:

12CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Observat ia 1.6.5. \(n; m) =\(nm;0) = i(nm), dac a mn:
De nit ia 1.6.6. Not amZ+=i(N) ={
[(n;0)jn2N}
={
\(n; m) n; m2N; n
m}
:
Mult imea Z+o vom numi mult imea numerelor ^ ntregi pozitive . AvemN≃Z,
(izomor sm de monoizi comutativi). Identi c^ and NcuZ+, vom considera ^ n
continuare NZ. De asemenea, vom nota Z=Znf0g:
De nit ia 1.6.7. Not amZ={
[(0; a)ja2N; a > 0}
 si o numim mult imea
numerelor ^ ntregi negative.
Observat ia 1.6.8. Au loc relat iile:
a)Z={
[(b; a)ja; b2N; b < a}
;
b)Z+[Z=Z;
c)Z+\Z=∅(deciZ+ siZconstituie o partit ie a mult imii Z).
1.7 Relat ia de ordine pe mult imea numerelor
^ ntregi
De nit ia 1.7.1. i) Fie ; 2Z. Dac a = + ( )2Z+=N, atunci
not am   si spunem c a este mai mic sau egal cu :
ii) < def,   si ̸= (altfel spus, 2N).
Se constat a c a relat ia " " este o relat ie de ordine pe Zcare extinde relat ia
de ordine natural a de pe N:
Propozit ia 1.7.2. (Z;)este o mult ime total ordonat a (pentru orice ; 2Z
avem  sau  ).
Demonstrat ie. Fie ; 2Z. Deoarece Z=Z+[Z, avem 2Z+sau
2Z. Dac a 2Z+, atunci  , iar dac a 2Z, atunci
 :
Observat ia 1.7.3. Dac a ; ;
2Z si  , atunci +
 +
(relat ia
de ordine este compatibil a cu structura de grup de pe mult imea Z(altfel spus
(Z;+;) este grup comutativ ordonat)).
1.8 ^Inmult irea numerelor ^ ntregi
De nit ia 1.8.1. Se va de ni o operat ie de ^ nmult ire pe Zcare s a extind a
^ nmult irea din N. Pentru operat ia ZZ!Zse va folosi aceea si notat ie,
( ; )!  , ca ^ n cazul ^ nmult irii din N:
De nim:
 =8
><
>:  dac a ; 2N
( ) dac a 2N; 2Z
( )( ) dac a 2Z; 2Z

1.9. MODULUL UNUI NUM AR^INTREG 13
^In acest fel operat ia de ^ nmult ire este bine de nit a pe Z:
Presupunem s a se probeze, ca exercit ii, urm atoarele a rmat ii:
1. (Z;+;) este inel comutativ cu unitatea 1 = [(1;0):
2. Dac a  = 0, atunci = 0 sau = 0:
3. Dac a   si
0, atunci

:
4. Dac a

 si
>0, atunci  :
5. Dac a   si
0, atunci

:
1.9 Modulul unui num ar ^ ntreg
De nit ia 1.9.1. Funct ia jj:Z!Nde nit a prin j j= max( ; ) se nume ste
funct ia modul sauvaloare absolut a , iarj jse nume ste modulul num arului :
Propozit ia 1.9.2. Funct ia modul are propriet at ile:
1.j + j  j j+j j;
2.j j=j j  j j;
3.j j= 0() = 0:
1.10 Relat ia de divizibilitate pe mult imea nu-
merelor ^ ntregi
De nit ia 1.10.1. Fie ; 2Z. Spunem c a "divide" dac a exist a
2Z
astfel ^ nc^ at
= . Dac a divide vom nota j :
Observat ia 1.10.2. 1. 1j ;(8) 2Z;
2. j0;(8) 2Z:
3. Relat ia " j" este re
exiv a  si tranzitiv a, dar nu este antisimetric a. Din j
 si j se obt ine j j=j j(spunem c a  si sunt asociate ^ n divizibilitate ).
4. Dac a j 1 si j 2, atunci j(b1 1+b2 2);(8)b1; b22Z:
5. Not am cu aZ=fakjk2Zgsubgrupul lui Zformat de multiplii num arului
^ ntreg a. Not am de asemenea aZ+bZ=fak+bljk; l2Zg:
1.11 Teorema de ^ mp art ire cu rest ^ n Z
Teorema 1.11.1. Fiea; b2Z; b̸= 0. Atunci exist a  si sunt unice numerele
^ ntregi q sirastfel ^ nc^ at
a=bq+r si0r <jbj:

14CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Demonstrat ie. Existent a. Deosebim urm atoarele cazuri:
Cazul 1. Dac a a= 0, atunci din 0 = b0 + 0  si 0 = 0 <jbjrezult a c a putem
luaq= 0  si r= 0:
Cazul 2. Dac a a > 0  si b > 0, atunci a sibsunt numere naturale  si
putem aplica teorema ^ mp art irii cu rest pentru numere naturale( ::::::::::: ): exist a
numerele naturale q sirastfel ^ nc^ at a=bq+r si 0r < b , deci q sirsunt
numere ^ ntregi  si are loc relat ia 0 r <jbj:
Cazul 3. Dac a a < 0  sib > 0, atunci a sibsunt numere naturale  si ,
aplic^ and teorema ::::::::: , exist a numerele naturale q′ sir′astfel ^ nc^ at a=bq′+
r′ si 0r′< b. Dac a r′= 0 , atunci avem a=bq′, deci a=b(q′)  si putem
luaq=q′; r= 0. Dac a r′>0, atunci avem : a=bq′r′=b(q′1)+br′
 si lu^ and q=q′1; r=br′, putem scrie: a=bq+r.^In plus, din 0 < r′< b
rezult a b <r′<0, a sa c a 0 < br′< b=jbj, adic a 0 < r < jbj:
Cazul 4. Dac a a > 0  si b < 0, atunci a sibsunt numere naturale
 si , aplic^ and teorema……….., exist a numerele naturale q′ sir′astfel ^ nc^ at a=
(b)q′+r′ si 0r′<b. Lu^ and q=q′ sir=r′, avem a=b(q′)+r′=bq+r,
cu 0r <b=jbj:
Cazul 5. Dac a a < 0  si b < 0, atunci a sibsunt numere naturale
 si,aplic^ and teorema……….., exist a numerele naturale q′ sir′astfel ^ nc^ at a=
(b)q′+r′ si 0r′<b. Dac a r′= 0, atunci avem a==bq′, deci a=bq′
 si putem lua q=q′; r= 0. Dac a r′>0, atunci avem: a=bq′r′=b(q′+
1) + (br′)  si lu^ and q=q′+ 1; r=br′, putem scrie: a=bq+r.^In
plus, din 0 < r′<brezult a b <r′<0, a sa c a 0 <br′<b=jbj, adic a
0< r < jbj.
Unicitatea c^ atului  si restului. S a presupunem c a avem a=bq+r si
a=bq′+r′, cu 0 r <jbj si 0r′<jbj. Atunci am avea b(qq′) =r′r,
deci
jbj  jqq′j=jrr′j: (1.11.1)
Dac a r′r, atunci 0 rr′r <jbj, iar dac a rr′, atunci 0 
r′rr′<jbj, deci ^ n ambele situat ii avem jrr′j<jbj. Dac a am avea
jqq′j ̸= 0, atunci ar ^ nsemna c a jqq′j 10, iar din relat ia (1)ar rezulta
jbj  jbj  jqq′j=jrr′j<jbj, ceea ce este imposibil. Prin urmare qq′ si
r′=r.
De nit ia 1.11.2. Numerele q sirse numesc c^ atul  si respectiv restul ^ mp art irii
num arului alab.
De nit ia 1.11.3. Fiea; b2Z. Un num ar dse nume ste un cel mai mare divizor
comun al numerelor a sibdac a:
i)dja;djb;
ii) din ja sijb, rezult a jd:
Not am un cel mai mare divizor comun al numerelor a sibcu (a; b). Se observ a
c adeste determinat de i)  si ii) p^ an a la o asociere ^ n divizibilitate. Convenim s a
lu am ( a; b)0. Determinarea este complet a.
Observat ia 1.11.4. Este clar c a avem ( a; b) = (jaj;jbj). Deoarece anterior am
probat existent a c. m. m. d. c. pentru orice dou a numere naturale, rezult a

1.12. ALGORITMUL LUI EUCLID 15
existent a c. m. m. d. c. pentru orice a; b2Z. O determinare e cient a a lui d
este asigurat a de "algoritmul lui Euclid".
^In cele ce urmeaz a vom presupune cunoscute construct ia mult imii Qa nu-
merelor rat ionale drept corp de fract ii al inelului integru Z, construct ia mult imii
Ra numerelor reale drept completare a lio Qfat  a de distant a de nit a de
d(x; y) =jxyj, precum  si construct ia corpului Cal numerelor complexe.
Vom utiliza de asemenea incluziunile canonice ZQRC:
De nit ia 1.11.5. Fie 2R. De nim partea ^ ntreag a a num arului  si not am
cu [ ] cel mai mare num ar ^ ntreg ce nu dep a se ste pe . Rezult a c a f gdef=
[ ]2[0;1)  si numim f gpartea fract ionar a a lui . Dac a a; b2Z; b > 0
 sia=bq+r, cuq; r2Z;0r < b , se constat a c a avem q= [a
b]:
1.12 Algoritmul lui Euclid
^In continuare prezent am un mod de determinare a c. m. m. d. c. a doi ^ ntregi.
Fiea; b2Z; b̸= 0. Conform teoremei …………exist a  si sunt unice numerele
^ ntregi q sirastfel ^ nc^ at a=bq+r si 0r <jbj:
Dac a r= 0, atunci ( a; b) =b. Vom presupune acum c a bja si vom nota
r=r0>0. deoarece r̸= 0, atunci tot conform teoremei ……….exist a  si sunt
unice numerele ^ ntregi q1 sir1astfel ^ nc^ at
b=br0+r1 si 0< r 1< r 0:
Dac a r1̸= 0, atunci exist a  si sunt unice numerele ^ ntregi q2 sir2astfel ^ nc^ at
r=r1q2+r2 si 0< r 2< r 1:
Dac a rk1̸= 0, atunci exist a  si sunt unice numerele ^ ntregi qk srkastfel
^ nc^ at
rk2=rk1qk+rk si 0rk< rk1:
Obt inem astfel numerele naturale r1> r 2>> r k: : :. Cum mult imea
Neste bineordonat a , exist a un n2Nastfel ca rn+1= 0 (^ n caz contrar s-ar
construi inductiv un  sir strict descresc ator de numere naturale).
Teorema 1.12.1. Num arul rndeterminat de condit iile rn̸= 0 sirn+1= 0este
cel mai mare divizor comun al numerelor a sib.
Demonstrat ie. Din relat iile rn+1= 0  si rn1=rnqn+1+rn+1rezult a rnjrn1; rnjrn2; : : : ; r nja
 sirnjb. Pe de alt a parte avem r02aZ+bZ, deci r12r0Z+bZaZ+bZ.
Folosind principiul induct iei matematice se obt ine ri+12riZ+ri1ZaZ+
bZ;(8)i; i1. Prin urmare exist a x; y2Zastfel ^ nc^ at rn=ax+by, de unde
rezult a c a dac a ja sijb, atunci jrn, deci rn^ ndepline ste condit iile din de nit ia
c. m. m. d. c. Se mai constat a c a avem aZ+bZ=rnZ.
Exemplu. S a a
 am (1987 ;675). Efectu^ and calculele cum se indic a al aturat,
obt inem (1987 ;675) = 9 :
Observat ia 1.12.2. Fiea; b2Znf0g. Se constat a u sor c a A= (aZ+bZ)\N̸=
∅. Dac a d= min A, atunci d= (a; b):
Indicat ie. Este su cient s a demonstr am c a dja sidjb, ceea ce rezult a din
minimalitate  si folosind teorema de ^ mp art ire cu rest.

16CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Observat ia 1.12.3. Fiea; b; c 2Z. Se veri c a faptul c a avem (( a; b); c) =
(a;(b; c)), ceea ce permite a de ni valoarea lor comun a ca ind ( a; b; c ) = c. m.
m. d. c al numerelor a; b; c . Inductiv putem de ni ( a1; a2; : : : ; a n).
^In mod dual se de ne ste [ a; b; c ] ca ind valoarea comun a a [[ a; b]; c] =
[a;[b; c]]  si , prin induct ie, [ a1; a2; : : : ; a n] = c. m. m. m. c. al numerelor
^ ntregi a1; a2; : : : ; a n:
De nit ia 1.12.4. Fiep2Znf1;0;1g:
Spunem c a peste ireductibil dac a din p=abrezult a jaj= 1 sau jbj=
1(spunem c a pnu admite descompunerea proprii).
1.13 Numere perfecte, numere mersenne, nu-
mere prime Fermat
De nit ia 1.13.1. Un num ar n2 se nume ste perfect dac a (n) = 2 n.
Exemple. 6;28;496 sunt numere perfecte.
Lui Euclid ^ i apart ine urm atorul rezultat:
Propozit ia 1.13.2. Dac a 2p1; p2este prim, atunci n= 2p1(2p1)este
un num ar perfect.
Demonstrat ie. ^Intr-adev ar , dac a n= 2p1(2p1), cu a= 2p1 num ar prim,
atunci, conform observat iei …………….. putem scrie:
(n) =(2p1(2p1)) = (2p1)(2p1)
deoarece numerele 2p1 si 2p1 sunt prime ^ ntre ele. T  in^ and seama de coro-
larul…………….. avem (2p1) = 1 + 21++ 2p1=2p1
21= 2p1. Dar,
dac a qeste num ar prim, atunci (q) = 1 + q, iar ^ n cazul nostru (2p1) =
1 + (2p1) = 2p:
deci(n) = 2p1(2p1) = 2 2p1(2p1) = 2 n:
Euler a demonstrat o reciproc a a acestei propozit ii:
Propozit ia 1.13.3. Dac a un num ar natural par neste perfect, atunci el este
de forma n= 2q(2q+11), unde 2q+11este prim.
Demonstrat ie. Putem scrie n= 2qu, unde q >0, iar ueste impar. Num arul n
ind perfect , avem (n) = 2n= 2q+1u. dar, conform corolarului……………..,
avem:
(n) =(2qu) =(2q)(u) = (2q+11)(u):
Deci
(2q+11)(u) = 2q+1u (1.13.2)
Cum 2q+11 este impar, rezult a c a 2q+1j(u), adic a exist a un num ar natural
dastfel^ nc^ at (u) = 2q+1d. Relat ia (1.13.2) devine: (2q+11)2q+1d= 2q+1u,
de unde u= (2q+11)d:
presupun^ and c a d̸= 1, am obt ine (u)1 +d+ (2q+11) +d(2q+11)>
d+d(2q+11) = d2q+1=(u), ceea ce este absurd. Prin urmare d= 1, iar
u= 2q+11 nu admite divizori diferit i de 1  si 2q+11, adic a ueste prim, iar
n= 2q(2q+11):

1.13. NUMERE PERFECTE, NUMERE MERSENNE, NUMERE PRIME FERMAT 17
Observat ia 1.13.4. Nu se  stie dac a exist a numere perfecte impare. Se poate
ar ata relativ simplu c a un astfel de num ar ar trebui s a aib7u a cel put in patru
factori primi distinct i. Pe de alt a parte de  stie c s un num ar perfect impar ar
trebui s a e mai mare dec^ at 250.
Propozit ia 1.13.5. Dac a x sinsunt numere naturale, x1; n2, astfel
^ nc^ at xn1este num ar prim, atunci x= 2, iar neste num ar prim.
Demonstrat ie. Din relat ia: xn1 = ( x1)(xn1++x+ 1) rezult a c a
pentru x >2, num arul xn1 este reductibil.
Dac a deste un divizor al ui n;1< d < n , putem scrie n=dm, cum > 1,
iar relat ia
2n1 = 2dm1 = (2d)m1 = (2d1)((2d)m1++ 2d+ 1)
arat a c a 2n1 este ireductibil ^ n acest caz. Propozit ia este demonstrat a.
De nit ia 1.13.6. Un num ar de forma Mp= 2p1 cupprim se nume ste num ar
al lui Mersenne (sau num ar Mersenne ).
O problem a interesant a o constituie stabilirea faptului dac a un anumit num ar
al lui Mersenne este num ar prim sau nu.
Exemplu. M2= 221 = 3 ; M3= 231 = 7 ; M5= 251 = 31 ; M7=
271 = 127 sunt numere prime, dar M11= 2111 = 2047 = 23 89.^In schimb
M13; M17; M19sunt prime.
Observat ia 1.13.7. Euler a stabilit(^ n anul 1750)c a M13este num ar prim;
Lucaz a stabilit(^ n anul 1876) c a M127de asemenea este prim; se  stie c a dac a
peste unul din numerele: 61, 89,107, 257, 521, 607, 1279, 2203, 2281, 3217,
4253, 4423, 9689, 9941, 11213, atunci num arul lui Mersenne corespunz ator este
prim. Cel mai mare num ar prim cunoscut ^ n mod explicit(^ n 1994) este Mpcu
p= 859433, num ar ce are, ^ n reprezentare zecimal a, 258716 cifre.
Propozit ia 1.13.8. Numere prime Fermat. Pierre Fermat(1601- 1665) a
studiat  sirul Fn= 22n+ 1. Observ^ and c a termenii  sirului sunt relativ primi
doi c^ ate doi  si c a F0; F1; F2; F3; F4sunt numere prime, el a emis conjectura c a
Fneste prim pentru orice n2N.^In 1732 Euler a ar atat c a F5= 232+ 1 =
6416700417 . Prezent am o demonstrat ie simpl a a faptului c a 641 divide F5:
Not am a= 27 sib= 5, deci ab3= 3;1 +abb4= 1 + 3 b= 24. Se obt ine
c a
232+ 1 = (2 a)4+ 1 = (1 + abb4)a4+ 1 = (1 + ab)a4+ 1a4b4
este divizibil cu 1 +ab= 641 :
P^ an a ^ n prezent nici un num ar Fnn-a fost identi cat ca ind prim, pentru
n5:
Observat ia 1.13.9. Gauss a ar atat c a un poligon regulat cu nlaturi poate
construit cu rigla  si compasul dac a  si numai dac a neste de forma n= 2ap1p2
ps, unde pisunt prime distincte din  sirul ( Fn)n2N(pentru o demonstrat ie ele-
mentar a se poate consulta:H. G. Forder "Fundamentele geometriei euclediene",
Editura S tint i c a, 1970). P^ an a ^ n prezent nu s-au identi cat numere prime Fn
pentru n5, dr nici nu s-a demonstrat c a exist a o in nitate de numere Fn
reductibile.

18CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
1.14 C^ ateva observat ii asupra  sirului numerelor
prime
Propozit ia 1.14.1. Mult imea Pa numerelor prime este in nit a.
Demonstrat ie. Dac a mult imea numerelor prime este presupus a nit a, P=fp1=
2; : : : ; p ng, equn factor prim al num arului M=p1 pn+ 1. Se obt ine qjM
 siq2 P, de unde qj1, ceea ce constituie o contradict ie.
O ^ nt arire a rezultatului anterior este dat a de urm atoarea.
Propozit ia 1.14.2. Fief(X) =anXn++a1X+a02Z[X], cu n1
 sian̸= 0. Atunci mult imea divizorilor ai elementelor din ff( )j 2Zgeste
in nit a.
Demonstrat ie. Dac a a0= 0, atunci a rmat ia este evident a, conform propozit iei
1.14.1. Fie a0̸= 0  si polinomul g(X)2Z[X] determinat prin relat ia f(a0X) =
a0g(X). Evident g(0) = 1. Dac a vom demonstra a rmat ia pentru polinomul
g(X), atunci ea va adev arat a  si pentru polinomul f(X). Mai ^ nt^ ai facem
observat ia c a mult imea fx2Zjg(x) =1gare cel mult 2 nelemente. Prin
urmare mult imea notat a Sga divizorilor primi ai valorilor ^ ntregi ale lui geste
nevid a. S a presupunem c a Sgeste o mult ime nit a, anume fq1; : : : ; q sg. Fie
g(X) =bnX6n++b1X+ 1. Pentru un inNsu cient de mare, not^ and
=q1   qs , vom avea g( ) =bn n++b1 + 1̸=1. Fie qjg( ),q
prim. Atunci q̸ j , deoarece altfel qar divizor al lui 1. Aceasta ^ ns a vine ^ n
contradict ie cu faptul c a q2Sg:
De nit ia 1.14.3. Dac a n2N, de nim (n) = fpjp2 P; png , adic a
num arul numerelor prime care nu dep a sesc pe n.
Obt inem astfel funct ia :N!N. Aeast a funct ie se extinde la o funct ie
:R!N; (x) = fpjp2 P; pxg :
Observat ia 1.14.4. i)(x) =([x]), unde [ x] reprezint a partea ^ ntreag a a
num arului real x.
ii) lim
x!1(x) =1(rezult a din 1.14.1)
De nit ia 1.14.5. Dac a n=p1:::pk, unde p1; :::; p ksunt numere prime
distincte, atunci psunem c a num arul neste liber de p atrate . Vom considera de
asemenea c a  si num arul -1 este liber de p atrate.
Observat ia 1.14.6. Dac a neste num ar ^ ntreg nenul, atunci putem scrie n=
a2b, unde a2N, iar beste liber de p atrate. Aceast a reprezentare este unic a,
avem apn, iar b=p 1
1:::p (n)
(n), cu i2 f0;1g:
Propozit ia 1.14.7. Dac a x2, atunci are loc relat ia (x)logx
2ln 2:
Demonstrat ie. Putem presupune x2N. Numerele din mult imea A=f1; :::; xg
se descompun ^ n cel mult (x) puteri de numere prime. Dac a neste num ar
natural, nx, atunci putem descompune n=a2b, unde a2N, iar beste
liber de p atrate. Avem apnpx, iar b=p 1
1:::p (n)
(n), cu i2 f0;1g.
Cum pentru aavem cel multpxposibilit at i, iar pentru bavem cel mult 2(x)
posibilit at i, rezult a pentru n=a2bcel multpx2(x)posibilit at i de alegere,

1.15. CIURUL LUI ERATOSTENE 19
de unde x=jAj px2(x). De aici reult a ln x1
2lnx+(x) ln 2, de unde
obt inem (x)lnx
2ln 2:
^In anul 1800 Legendre propune ^ n lucrarea sa "Theorie des Nombres " o
formul a empiric a pentru funt ia (x)  si observ a o leg atur a str^ ns a ^ ntre (x)  si
funct iax
logx. Un rezultat semni cativ ^ n acest sens a fost demonstrat ^ n 1850
de Ceb^ a sev.
1.15 Ciurul lui Eratostene
Propozit ia 1.15.1. Dac a n2, iar neste num ar compus (reductibil), atunci
exist a p2 P astfel ^ nc^ at ppn sipjn.
Demonstrat ie. Dac a n=p1:::ps, unde p1:::ps,s2, atunci p1pn:
Corolarul 1.15.2. Fien2. Dac a pentru orice p2 P, cuppnavem p̸ jn,
atunci neste num ar prim.
Corolarul 1.15.2 pune ^ n evident  a un algoritm de construire a  sirului nu-
merelor prime, algoritm numit ciurul lui Eratostene .
Iat a un tabel cu c^ ateva numere prime:
n 12310 25 100 200 1000 1229 1230
pn23529 97 541 1223 7917 9973 10007
1.16 Rezultate ale lui L. Euler despre  sirul nu-
merelor prime
Marele matematician elvet ian Leonhard Euler a deschis drumul^ n folosirea metode-
lor analizei matematice la chestiuni de aritmetic a.
Teorema 1.16.1. (Euler, 1737) Seria∑
p2P1
peste divergent a.
Demonstrat ie. Fien2  sifp1; p2; :::; p (n)gmult imea numerelor prime ce nu-l
dep a sesc pe n. Not am (n) =(n)∏
i=11
11
pi. S a remarc am c a avem
(n) =(n)∏
i=1(
1 +1
pi+1
p2
i+:::)
=∑
1;:::; (n)2N1
p 1
1:::p (n)
(n)>1 +1
2+:::+1
n:
Am folosit faptul c a , datorit a unicit at ii descompunerii, termenii sumei me-
diane sunt distinct i. Se obt ine lim
n!1(n) =1, dat ind c a 1 +1
2+:::+1
n! 1 ,
iar de aici rezult a c a mult imea Peste in nit a.
Pentru a demonstra 1.16.1 este nevoie de urm atorul rezultat:
Lema 1.16.2. Avem log(
11
pi)
=1∑
m=11
mpm
i(^ n continuare se va nota
log = ln).

20CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Demonstrat ie. ^Intr-adev ar, dac a jtj<1, atunci1
1+t= 1t+t2t3+::: si
putem integra termen cu termen:x∫
0dt
1+t=x∫
0(1t+t2t3+:::)dt, deci
log(1 + x) =xx2
2x3
3+:::+ (1)n+1xn
n+:::pentru jxj<1:
^Inlocuind xcux, obt inem: log(1 x) =xx2
2x3
3:::xn
n:::, de
unde, pentru a2, log(
11
a)
=1
a1
2a21
3a3:::1
mam:::
A sadar pentru orice num ar prim p, avem log(
11
p)
=1∑
m=11
mpm:
Utiliz^ and 1.16.2 se obt ine ^ n continuare log(
11
p)1
=1∑
m=11
mpm, de unde
log(n) =(n)∑
i=1log(
11
pi)1
=∑
i=1(n)1∑
m=11
mpm
i=1
p1+:::+1
p(n)+(n)∑
i=11∑
m=21
mpm
i:
^Ins a oricare ar i,
1∑
m=21
mpm
i<1∑
m=21
pm
i=1
p2
i(
1 +1
pi+1
p2
i+:::)
=1
p2
i1
11
pi2
p2
i;
(^ n ultima inegalitate t inem seama c a1
11
pi2).
Dar
1∑
m=21
mpm
i<2(n)∑
i=21
p2
i<∑
pi2P1
p2
i<∑
k2N1
k2<1;
rezult^ and c a log (n) =1
p1+:::+1
p(n)+ (n), unde  sirul ( (n))n2este m arginit.
Cum lim
n!1(n) =1, rezult a  si log (n) =1
p1+:::+1
p(n)+ (n)! 1 , deci
lim
n!1(1
p1+:::+1
p(n))
=1:
Observat ia 1.16.3. Se poate ar ata c a exist a  si este nit a
lim
n!1(1
p1+:::+1
p(n)log log n)
:
Acest fapt a fost stabilit de Euler ca o consecint  a a convergent ei  sirului
an= 1 +1
2+:::+1
nlogn:
De nit ia 1.16.4. Se de net e funct ia
: (1;1)!R;prin (s) = 1 +1
2s+1
3s+:::+1
ns+:::
Aceast a funct ie se nume ste funct ia zeta saufunct ia lui Riemann . Funct ia 
se poate extinde (cu aceea si de nit ie ) la semiplanul fz2CjRe(z)>1g, unde
Re(z) =x, dac a z=x+iy, cux; y2R

1.17. FUNCT II ARITMETICE 21
Observat ia 1.16.5. Avem lim
s!1(s) =1(consecint  a a faptului c a seria 1 +1
2+
:::+1
n+:::este divergent a ).
Propozit ia 1.16.6. Dac a n2, atunci avem
(n)∏
i=11
11
ps
i=(n)∏
i=1(
1 +1
ps
i+1
p2s
i+:::)
=∑
1;:::; (n)2N1
ps 1:::ps (n)
(n)
1< (s):
Dac a not am s(n) =(n)∏
i=11
11
ps
i, atunci avem s(n)< (s) silim
n!1s(n) =
(s).
Demonstrat ie. Inegalitatea are loc pentru c a numitorii ce apar ^ n suma din
st^ anga sunt numere naturale distincte pentru exponent ii jdistinct i (consecint  a
a teoremei fundamentale a aritmeticii). Deci pentru s xat ( s(n)n) este un  sir
strict cresc ator  si m arginit de numere reale. Reult a c a exist a lim
n!1s(n)(s):
S a ar at am c a are loc egalitatea.
Avem 0 < (s)(n)1
(n+1)s+1
(n+2)s+:::, pentru c a suma 1+1
2s+:::+1
nsse
reg ase ste ^ n dezvoltarea lui s(n), iar diferent a (s)s(n) tinde la 0 c^ and n!
1. Se obt ine astfel identitatea lui Euler: (s) = lim
n!1s(n) =∏
p2P(
1
11
ps)
:
Studiul funct iei ( si al unor funct ii str^ ans legate de aceasta) este deosebit
de important ^ n teoria numerelor. Multe rezultate semni cative privind  sirul
numerelor prime au fost demonstrate ^ n leg atur a cu anumite propriet at i ale
funct iei .
^In acela si timp, multe probleme deschise admit formul ari echivalente care
se refer a la anumite propriet at i ale funct iei . O lucrare foarte interesant a ^ n
acest domeniu este Riemann's Zeta Function de H.M. Edwards, Academic Press,
1974.
1.17 Funct ii aritmetice
De nit ia 1.17.1. Prin funct ie aritmetic a se^ n ctelege o funct ie av^ and ca dome-
niu de di nit ie mulc timea Na numerelor naturale.
^In particular, orice  sir ( an)n2Neste o funct ie aritmetic a.
Exemplu. 1.d(n) = num arul divizorilor pozitivi ai lui n
2.(n) = suma divizorilir pozitivi ai lui n
3.φ:N!R; φ(n) = fk2N 1kn;(k; n) = 1g , indicatorul lui
Euler.
1.17.1 Funct ia lu M obius
De nit ia 1.17.2. Fie funct ia :N!Zde nit a astfel:
(n) =8
><
>:1; dac a n= 1;
0; dac a9p2 P a.^ .p2jn;
(1)k;dac a n=p1p2:::pk;cup;p2; :::; p kprime distincte.
Aceast a funct ie de nume ste funct ia lui M obius.

22CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
1.17.2 Propriet at i ale funct iei lui M obius
Propozit ia 1.17.3. Fien2N. Atunci∑
djn(d) ={
1; n = 1;
0; n̸= 1(suma se face
dup a tot i divizorii pozitivi ai lui n).
Demonstrat ie. Dac a n2N, atunci putem scrie n=p 1
1:::p k
k, unde k1,
iarpi2 P sunt distincte. Din djnrezult a d=p 1
1:::p k
k, unde 0  i i.
Avem:
∑
djn(d) =∑
( 1;:::; k)
0 j j(p 1
1:::p k
k) =∑
i2f0;1g(p 1
1:::p k
k) =
=∑
Af1;2;:::;kg(1)jAj=k∑
i=1(1)iCi
k= (11)k= 0:
Teorema 1.17.4. Teorema de inversiune a lui M obius Fief:N!C
o funct ie aritmetic a. De nim F:N!Cprin F(n) =∑
djnf(d). Atunci avem
identitatea:
f(n) =∑
djnF(d)(n
d)
=∑
djn(d)F(n
d)
:
Demonstrat ie. Not^ and S=∑
djnF(d)(
n
d)
, atunci S=∑
djn(
(d)∑
 n
df())
.
Dar n
d,djn,d n
:Deci S=∑
jn(
f()∑
d n
(d))
:
Cum∑
d n
(d) ={
1;dac a =n
0;dac a < n, rezult a S=f(n).
1.17.3 Indicatorul lui Euler
De nit ia 1.17.5. Funct ia φ:N!R, de nit a prin
φ(n) =jfk2Nj1kn;(k; n) = 1gj
se nume ste funct ia (sau indicatorul) lui Euler . (Altfel spus, φ(n) este num arul
numerelor naturale nenule mai mici dec^ at n si relativ prime cu n).

1.18. ALTE CONSIDERAT II DESPRE FUNCT IILE ARITMETICE 23
Propozit ia 1.17.6. Are loc egalitatea∑
djnφ(d) = n(suma se face dup a tot i
divizorii pozitivi ai lui n).
Demonstrat ie. FieA=f1
n;1
n; :::;n1
n;n
ngmult imea tuturor fract iilor mai mici
sau egale cu unitatea, av^ and numitorul n. Avem A=∪
djnAd, unde Adeste
mult imea fract iilor din Acare ^ n form a ireductibil a au numitorul d:
Ad={k
nj(9)l;1ld;k
n=l
d;(l; d) = 1}
:
Deoarece mult imile Adconstituie o partit ie a lui A, avem n=jAj=∑
djnjAdj si
cumjAdj=φ(d), deducem relat ia n=∑
djnφ(d):
Observat ia 1.17.7. Folosind propozit ia de mai sus  si aplic^ and teorema de
inversiune a lui M obius obt inem:
φ(n) =∑
djn(d)n
d(1.3)
egalitate ce permite deducerea unei formule pentru φ(n) plec^ and de la de-
scompunerea canonic a a lui n.
Dac a 1 < n =p 1
1:::p k
k; piprimi, atunci ^ n relat ia 1.3 suma se va face
doar dup a divizorii liberi de p atrate(vezi de nit ia funct iei ), deci putem scrie:
φ(n) =∑
djn(d)n
d=∑
i2f0;1g(p 1
1:::p k
k)n
p 1
1:::p k
k=
=nk∑
i=1n
pi+∑
1ijkn
pipj+:::=n(
11
p1)
:::(
11
pk)
:
1.18 Alte considerat ii despre funct iile aritmet-
ice
De nit ia 1.18.1. 1) O funct ie f:N!Cse nume ste funct ie multiplicativ a
dac a oricare ar m; n2N, cu ( m; n) = 1, avem f(mn) =f(m)f(n):
2) O funct ie f:N!Cse nume ste funct ie total multiplicativ a dac a oricare
ar m; n2N, avem f(mn) =f(m)f(n):
Exemplu. Funct iile φ;   sid(notat a uneori  si ) sunt funct ii multiplicative.

24CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Propozit ia 1.18.2. Fiem; n2Ncu(m; n) = 1  si mult imile A=f(d1; d2)jd22
N; d22N; d1jm; d 2jm;(d1; d2) = 1g siB=fdjd2N; djmng. Atunci jAj=jBj.
Demonstrat ie. Exist a o corespondent  a biunivoc a natural a^ ntre elementele mult imilor
A siB, anume ( d1; d2) d=d1d2, unde d1= (d; m); d2= (d; n). Egalitatea
(d; m)(d; n) =dasigur a faptul c a ^ ntre mult imile A siBexist a o corespondent  a
biunivoc a.
Propozit ia 1.18.3. Fief:N!Co funct ie multiplicativ a. Atunci  si funct ia
F:N!C; F(n) =∑
djnf(n)este o funct ie multiplicativ a.
Demonstrat ie. Fiem; n2Ncu (m; n) = 1. Atunci
F(m)F(n) =(∑
d1jmf(d1))(∑
d2jnf(d2))
=∑
(d1;d2)
d1jm;d 2jnf(d1)f(d2) =∑
d1d2jmnf(d1d2) =F(mn):
Observat ia 1.18.4. Dac a feste o funct ie multiplicativ a, atunci feste bine
determinat a de valorile sale pe elementele mult imii fpkjp2 P; k0g:
1.19 Inegalit at ile lui Ceb^ a sev
Am de nit anterior funct ia :R!N, prin (x) = fpjp2P; pxg :
Observat ia 1.19.1.
1. Faptul c a mult imea Peste in nit a este echivalent cu
lim
x!1(x) =1
2. Mai mult, dup a cum s-a ar atat, pentru x > 1 avem (x)>logx
2 log 2, unde
logx= lnx.
3.^In 1850 Ceb^ a sev a demonstrat un rezultat semni cativ: Exist a constantele
pozitive c1 sic2astfel ^ nc^ at c2x
logx< (x)< c 1x
logxpentru x >1.
^In continuare prezent am demonstrat ia teormei lui Ceb^ a sev asupra funct iei
(x).
Fie: [1;1)!R+de nit a prin (x) =8
<
:0 ,dac a 1 x <2;∑
px;pprimlogp,dac a x2:

1.19. INEGALIT AT ILE LUI CEB ^AS EV 25
Propozit ia 1.19.2. Pentru orice m1are loc relat ia: 2m+1log 2 > (2m).
Demonstrat ie. Dac a n2N, putem scrie:
22n= (1 + 1)2n> Cn
2n=(n+ 1):::(2n1)(2n)
12:::n>p2n∏
p>n
pprimp;
de unde, prin logaritmare, rezult a:
2nlog 2 >p2n∏
p>n
pprimlogp=(2n)(n): (1.4)
Fiem1  sin2 f1;2; :::;2m1g. Conform relat iei 1.4, avem succesiv:
2log 2 > (2)(1);
22log 2 > (22)(2);

2mlog 2 > (2m)(2m1);
de unde, prin ^ nsumare, obt inem:
(2 + 22+:::+ 2m)log 2 > (2m);
deci
2m+1log 2 > (2m):
Propozit ia 1.19.3. Pnetru orice x >1avem (x)<(4 log 2) x:
Demonstrat ie. Deoarece x > 1, exist a un mastfel ^ nc^ at 2m1< x2m.
Funct ia  ind cresc atoare, avem: (x)(2m)<2m+1log 2 = 4 2m1log 2 <
4xlog 2.
Observat ia 1.19.4. Pentru x4 avemx
logx>px:
Demonstrat ie. Fieg(x) =pxlogx. Atunci
g′(x) =1
2px1
x=px2
2x;
deci pentru x4 obt inem
g(x)g(4) = 2 log 4 = loge2
4>0:
Decipxlogx >0, de undex
logx>px.

26CAPITOLUL 1. MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE, TEOREMA DE ^IMPART IRE CU REST
Propozit ia 1.19.5. Exist a c12(0;1)astfel ^ nc^ at pentru orice x2(1;1)are
loc inegalitatea: (x)< c 11
logx:
Demonstrat ie. Avem
(x) =∑
pxlogppx∑
p>pxlogp(logpx)((x)(px))(logpx)(x)pxlogpx:
Deci
(x)(x)
logpx+px(8 log 2)x
logx+px(1 + 8 log 2)x
logx:
A sadar, lu^ and c1= 1 + 8 log 2, avem (x)< c 1x
logx. Pentru x4 am folosit
inegalitateax
logx>px, iar pentru 1 < x < 4 inegalitatea de demonstrat se
veri c a direct.
Observat ia 1.19.6. c1= 1 + 8 log 2 = 6 ;54517744448 : : : :
Observat ia 1.19.7. Fien2N sipprim ( p2 P). Dac a n! =pep(n!)q, unde
(q; p) = 1, atunci not am ep(n!) =ordp(n!). Vom folosi urm atorul rezultat al lui
Legendre: ordp(n!) =1∑
j=0[
n
pj]
, unde [ x] reprezint a partea ^ ntreag a a num arului
x. S a observ am c a suma1∑
j=0[
n
pj]
este nit a, pentru c a ^ nce^ and de la un anumit
javem pjn, deci pentru k > j vom avea[
n
pk]
= 0:

Capitolul 2
Not iuni generale
2.1 Divizibilitatea pe N
De nit ia 2.1.1. Fiind date dou a numere naturale a sib, spunem c a adivide b
dac a exist a num arul natural castfel ^ nc^ at b=ac.
Dac a adivide bvom nota ajbsaua…b si mai citim aeste divizor al lui b,bse
divide la asau c a beste multiplu de a. Dac a a̸= 0,  si ajbavem restul ^ mp art iri
luiblaaeste zero.
^In caz contrar, spunem c a anu divide b si scriem a̸ jb. De exemplu, 2 j6, dar
2̸ j7.
Propriet at i ale relat iei de divizibilitate:
D1: 0jb() b= 0;aj0;8a2N;
D2: 1jb sibjb;8b2N;bj1() b= 1;8b2N; b̸= 1 admite cel put in doi
divizori;
D3: Relat ia de divizibilitate de pe Neste re
exiv a, antisimetric a  si tranzitiv a,
adic a (N;j) este o mult ime ordonat a ^ n care 1 este cel mai mic element,
iar 0 este cel mai mare element.
-re
exiv a: aja;8a2N;
-antisimetric a: ajb sibja)a=b;
-tranzitiv a: ajb sibjc)ajc;
-nu este total a: 9a; b2Nastfel ^ nc^ at a̸ jb sib̸ ja:
D4:ajb)ab, relat ia de divizibilitate este compatibil a cu relat ia de ordine;
D5:ajb siajc)ajbx+cy;8x; y2N, relat ia de divizibilitate este compatibil a
cu operat iile de adunare  si ^ nmult ire;
D6:ajb+c siajb)ajc:
Demonstrat ie. Pentru cazul a̸= 0. Deoarece:
ajb+c) 9x2Nastfel ^ nc^ at b+c=ax
ajb) 9y2Nastfel ^ nc^ at c=ay:
27

28 CAPITOLUL 2. NOT IUNI GENERALE
Avem b+cbdeci axay; a̸= 0, de unde obt inem xy:^In
consecint  a 9z2Nastfel ^ nc^ at x=y+z. Avem b+c=ax=a(y+z) =
ay+az=ay+c)c=az)ajc:
De nit ia 2.1.2. Un num ar natural pse nume ste ireductibil dac a p2  si
dintr-o relat ie de forma p=ab)a= 1 sau b= 1:
^In caz contrar, pse nume ste num ar reductibil sau decompozabil.
De nit ia 2.1.3. Un num at natural p; p2, se nume ste num ar prim dac a pjab
implic a pjasaupjb:
^In caz contrar, num arul se nume ste compus.
Teorema 2.1.4. Fiepun num ar natural, p2. Urm atoarele a rmat ii sunt
echivalente:
1.peste num ar prim;
2.peste num ar ireductibil.
Demonstrat ie. 1:)2:Fiepun num ar prim despre care presupunem prin re-
ducere la absurd c a este decompozabil. Exist a deci numerele naturale a sib,
1< a; b < p astfel ^ nc^ at p=ab. Aceasta ^ nseamn a c a pjab si cum peste prim
obt inem pjasaupjb. Dar p=ab si deci ajp sibjp, de unde obt inem p=asau
p=b, ceea ce contrazice faptul c a a < p  sib < p .
2:)1:Fiepun num ar ireductibil despre care presupunem prin reduc-
ere la absurd c a nu este prim. Folosind Principiul bunei ordon ari (( N;) este
o mult ime bine ordonat a. Aceasta ^ nseamn a c a orice submult ime nevid a a
mult imii numerelor naturale admite un prim element) pot presupune c a peste
cel mai mic num ar cu aceast a proprietate. Deoarece pnu este num ar prim
obt inem c a 9a; b2Nastfel ^ nc^ at pjab; pnu divide a sipnu divide b, iar
produsul abeste minim cu aceast a proprietate.
Demonstr am c a a < p  sib < p . Dac a prin reducere la absurd presupunem
c aa > p , conform Teoremei ^ mp art irii cu rest(pentru orice 2 numere naturale
a sib, cub̸= 0, exist a  si sunt unice numerele q sirastfel ^ nc^ at a=bq+r,
cur < b )a=pq+r; q1;0< r < p: Obt inem ab=pqb+rbde
unde rezult a pjrb,pnu divide b,pnu divide r sirb < abceea ce contrazice
alegerea perechii ( r; b).^In consecint  a 1 < a < p  si 1< b < p .
Deoarece pjabexist a q >1(q̸= 1 deoarece pireductibil) asifel ^ nc^ at pq=
ab. Deoarece 1 < a < p  si 1< b < p obt inem pq=ab < ppde unde se obt ine
q < p . Fie cun divizor ireductibil al lui q,cq < p . Avem cjqjab)cjab, este
ireductibil  si cum este mai mic dec^ at p, din alegerea lui p(cel mai mic neprim cu
propriet at ile pe care le are  si q) se obt ine cnum ar prim. Deoarece cjab)cja
saucjb:
Presupunem cja)a=ca1. Cum ab=pq)ca1b=pcq1)a1b=
pq1,  si deci pja1bceea ce contrazice alegerea perechii ( a; b) cu produsul ab
minim a1b < ab).
Observat ia 2.1.5. Conform teoremei 2.1.4, prin num ar reductibil vom ^ nt elege
num ar compus.
Teorema 2.1.6. Teorema lui Euclid Exist a o in nitate de numere prime.

2.2. CEL MAI MARE DIVIZOR COMUN 29
Demonstrat ie. Prin reducere la absurd presupunem c a exist a o mult ime nit a
de numere prime P=fp1; p2; :::; p kg. Consider am num arul N=p1p2pk+1.
Cum N > 1 exist a un num ar prim pastfel ^ nc^ at pjN. Cum pprim rezult a c a
exist a i2 f1;2; : : : ; k gastfel^ nc^ at p=pi. Deoarece pjN sipjp1p2pkobt inem
c apj1 ceea ce este fals.
Teorema 2.1.7. Teorema fundamental a a aritmeticii Orice num ar nat-
urala >1admite o scriere unic a, p^ an a la ordinea factorilor, ca produs nit de
numere prime.
Demonstrat ie. Existent a scrierii: Not am M=fa2N; a > 1; nnu se poate
scrie ca un produs nit de numere ireductibile g. Dac a prin reducere la absurd
presupunem c a M̸=∅, conform Principilui bunei ordon ari, exist a aun prim
element al mult imii M.
a̸= num ar prim )a=bc;1< b; c < a )b; cnu apart in lui M si deci b si
cse pot scrie ca un produs nit de factori primi.
^Inseamn a c a aare aceea si proprietate, ceea ce contrazice a2M:
Unicitatea scrierii: Presupunem a=p1p2pn=q1q2qm. Demonstr am
prin induct ie dup a nc an=m si dup a o eventual a permutare a factorilor pi=qi:
Pentru n= 1 avem p1=q1q2qm)p1jq1q2qm si deci 9j2
f1;2; : : : ; m gastfel ^ nc^ at p1jqj. Deoarece qjeste ireductibil reult a p1=qj si
m=n= 1:
Presupunem proprietatea adev arat a pentru n1  si consider am p1p2pn=
q1q2qm:
pnjq1q2qm)pnjqm. Deoarece qmeste ireductibil obt inem pn=qm si
decip1p2pn1=q1q2qm1:
Folosind ipoteza inductiv a avem n1 =m1  si dup a o eventual a renu-
merotare pi=qi;8i2 f1;2; : : : ; n 1g:
Corolarul 2.1.8. Oricare ar num arul natural a >1 exist a numere ireductibile
distincte (dac a n2)p1; p2; : : : ; p n si numerele naturale nenule 1; 2; : : : ; n
astfel ^ nc^ at
a=p 1
1p 2
2:::p n
n (2.1)
^In plus, dac a a=p 1
1p 2
2:::p nn=q 1
1q 2
2:::q mm, unde q1; q2; : : : ; q nsnt
numere ireductibile distincte, iar i1 atunci avem n=m; p i=qi; i= i,
pentru orice i;1in:
De nit ia 2.1.9. Descompunerea unui num ar natural ^ n forma ecuat iei (2.1) se
nume ste scrierea ^ n form a canonic a sau descompunerea canonic a.
2.2 Cel mai mare divizor comun
De nit ia 2.2.1. Spunem c a num arul natural deste cel mai mare divizor comun
al numerelor a sib(scriem d=c. m. m. d. c. fa; bgsaud= (a; b)) dac a:
1.dja sidjb;
2. pentru d′2Navem d′ja sid′jbatunci d′jd:
Exemplu. a= 420 = 22357
b= 504 = 23327
Atunci, ( a; b) = 2237 = 84 :

30 CAPITOLUL 2. NOT IUNI GENERALE
Teorema 2.2.2. Teorema de existent  a  si unicitate a celui mai mare
divizor comun Pentru orice dou a numere naturale a sibexist a  si este unic
cel mai mare divizor comun al lor.
Demonstrat ie. Existent a: (Algoritmul lui Euclid) Dac a a= 0 sau b= 0 atunci
d=bsaud=a. Presupunem a̸= 0  si b̸= 0. Aplic^ and teorema ^ mp art irii cu
rest, exist a q0; r0astfel ^ nc^ at
a=bq0+r0;0r0< b:
Dac a r0= 0)a=bq0 sid= (a; b) =b:
Dac a r0̸= 0 aplic am din nou teorema ^ mp art irii cu rest pentru b sir0.
Continu am procedeul p^ an a obt inem un rest nul.
b=r0q1+r1;0< r 1< r 0;
: : : : : : : : : : : : : : : ;
rn2=rn1qn+rn;0< rn< rn1; (2.2)
rn1=rnqn+1:
Algoritmul prezentat are un num ar nit de pa si deoarece  sirul de numere
naturale b > r 0>> rneste strict descrec ator. Vom emonstra c a rn= (a; b).
Deoarece rnjrn1se obt ine rnjri;8i sirnjb; rnja. Dac a d′ja sid′jbse obt ine
d′jr0; : : : ; d′jrn. Rezult a rn= (a; b):
Unicitatea: Fie d sid′numere naturale care satisfac condit iile 1.  si 2. din
de nit ia 2.2.1 rezult a c a djd′ si apoi d′jdde unde rezult a d=d′:
Exemplu. 1) Pentru ilustrare, algoritmul lui Euclid se poate utiliza pentru a
g asi cel mai mare divizor comun al lui a= 1071  si b= 462 :Pentru ^ nceput,
multiplii lui 462 sunt sc azut i din 1071 p^ an a r am^ ane un rest mai mic dec^ at 462.
Se pot sc adea doi astfel de multipli( q0= 2), l as^ and num arul 147.
1071 = 2 462 + 147 :
Apoi multiplii lui 147 sunt sc azut i din 462 p^ an a c^ and restul este mai mic
dec^ at 147. Trei multipli se pot sc adea ( q1= 3)  si r am^ ane restul 21.
462 = 3 147 + 21
Apoi se scad multiplii lui 21 din 147 p^ an a c^ and restul este mai mic dec^ at 21.
Se pot sc adea  sapte multipli( q2= 7)  si nu r am^ ane niciun rest.
147 = 7 21 + 0
Cum ultimul rest este zero, algoritmul se termin a cu 21 ca cel mai mare
divizor comun al lui 1071  si 462.
2) Fie numerele 180  si 630.
Pentru a determina cel mai mare divizor comun al numerelor date, descom-
punem numerele ^ n produse de factori numere prime.
180 = 22325

2.2. CEL MAI MARE DIVIZOR COMUN 31
630 = 2 3257
Divizorii comuni trebuie s a cont in a cel put in unul din factorii primi comuni
cu exponentul cel mai mic. A sadar, cel mai mare divizor comun, ind cel mai
mare num ar care divide ecare din numerele date, va cont ine factorii primi
comuni cu exponentul cel mai mic.
180 = 22325
630 = 2 3257
(180; 630) = 2 325 = 90
De nit ia 2.2.3. Spunem c a dou a numere a sibsunt prime ^ ntre ele dac a
(a; b) = 1 :
Fiea=p 1
1:::p nn sib=p 1
1:::p nn:
Obt inem c a a sibsunt prime ^ ntre ele dac a  si numai dac a min( i; i) =
0;8i2 f1;2; : : : ; n g:
Enunt  am c^ ateva propriet at i ale c. m. m. d. c.  si demonstr am o parte din
ele.
1. 1) (a; a) =a(idempotent a); ( a; b) = ( b; a)(simetria);
2) (a; b) =d)(ac; bc) =dc;8a; b; c2N;
3) (a;(b; c)) = (( a; b); c)(asociativitatea, permite s a de nim c. m. m. d.
c. pentru mai mult de dou a numere, astfel putem de ni ( a; b; c ) :=
(a;(b; c));8a; b; c2N);
4) (a; b) = 1  si ( a; c) = 1() (a; bc) = 1;
5)ajc; bjc;(a; b) = 1)abjc;
6) (a; b) =d)a=a1d; b=b1dastfel ^ nc^ at ( a1; b1) = 1;
7)ajbc si (a; b) = 1)ajc:
De nim, prin recurent  a, c. m. m. d. c. a nnumere a1; a2; : : : ; a n;((a1; a2; : : : ; a n1); an):
Von demonstra o parte din cele enunt ate .
Demonstrat ie. 3) Not am d1= (b; c); d2= (a;(b; c)) = ( a; d 1); d3= (a; b)  si
d4= ((a; b); c) = ( d3; c). Pentru a demonstra c a d2=d4vom ar ata d2jd4 si
d4jd2:Deoarece d2= (a; d 1) rezult a d2ja sid2jd1. Cum d1= (a; b))d1ja sid1jb
ceea ce implic a d2jb sid2jc. Din d2ja; d 2jb sid3= (a; b) obt inem d2jd3. Folosind
d2jd3; d2jc sid4= (d3; c) se obt ine d2jd4.^In mod asem an ator se demonstreaz a
d4jd2.
4) Folosind propriet at ile anterioare avem 1 = ( a; b) = ( a; b(a; c)) = ( a;(a
b; bc)) = (( a; ab); bc) = ( a; bc):
5) Vom ar ata c a abjc, ar at^ and c a ( ab; c) =ab. Pentru aceasta avem
(ab; c) = ( ab; c(a; b)) = ( ab;(ac; bc)) = (( ab; ac); bc) = ( a(b; c); cc)
=
(ab; bc) =b(a; c) =ba:
Exemplu. Fie numerele a= 450 = 2 3252 sib= 77 = 7 11. Numerele a si
bau un singur divizor comun, pe 1. Scriem ( a;b) = 1 :

32 CAPITOLUL 2. NOT IUNI GENERALE
2.3 Cel mai mic multiplu comun
De nit ia 2.3.1. Spunem c a num arul natural meste cel mai mic multiplu
comun al numerelor a sib(scriem m=c:m:m:m:c fa; bgsaum= [a; b]) dac a:
1)ajm; bjm;
2) pentru m′2Navem ajm′ sibjm′atunci mjm′.
Teorema 2.3.2. (Teorema de existent  a  si unicitate a celui mai mic multiplu
comun)
Pentru orice dou a numere naturale a sibexist a  si este unic cel mai mic
multiplu comun al lor.
2. 1) [a; a] =a(idempotent a); [ a; b] = [b; a](simetria);
2) [a; b] =m)[ac; bc] =mc;8a; b; c2N;
3) [a;[b; c]] = [[ a; b]; c](asociativitatea, permite s a de nim c. m. m. m. c.
pentru mai mult de dou a numere, astfel putem de ni [ a; b; c ] := [ a;[b; c]];8a; b; c2
N);
4) (a;[a; b]) =a si [a;(a; b)] =a;8a; b2N(absorbt ie);
5) (a; b)[a; b] =ab;8a; b2N;
6) (a;[b; c]) = [( a; b);(a; c)] si [a;(b; c)] = ([ a; b];[a; c]);8a; b; c2N(distributivitate);
7)ajc sibjc)[a; b]jc:
Exemplu. Pentru a determina cel mai mic multiplu comun al numerelor 180  si
630, descompunem numerele ^ n produse de factori numere prime, apoi efectu am
produsul factorilor primi comuni  si necomuni, considerat i o singur a dat a cu
exponentul cel mai mare.
180 = 22325
630 = 2 3257
[180; 630] = 223257 = 1260 :
2.4 Criterii de divizibilitate pentru numere scrise
^ n baza 10
Enunt  am principalele criterii de divizibilitate ^ nsot ite de c^ ateva exemple.
Prin criteriu de divizibilitate al unui num ar natural mcu un num ar natural
d^ nt elegem o condit ie necesar a  si su cient a pentru ca num arul ms a se ^ mpart a
exact prin num arul d si se noteaz a m=Md( spunem c a meste multiplu al
num arului d). Cum baza de numerat ie utilizat a este 10, aceste criterii se refer a
la cifrele scrierii ^ n baza zece a num arului m.
Scrierea unic a a num arului m^ n baza 10 este urm atoarea:
m=ap10p+ap110p1++a1101+a100, cu notat ia m=apap1: : : a 0,
unde a0; a1; : : : ; a p2 f0;1; : : : ; 9g:
Criteriul de divizibilitate cu 10, respectiv cu 2 sau 5

2.4. CRITERII DE DIVIZIBILITATE PENTRU NUMERE SCRISE ^IN BAZA 10 33
Pentru ca un num ar ms a e divizibil cu 10, respectiv cu 2 sau cu 5 este
necesar  si su cient ca ultima cifr a a num arului ms a e 0, respectiv ca ultima
cifr a s a e divizibil a cu 2 sau 5. Astfel c a numerele naturale mdivizibile cu 10
au ultima cifr a 0, divizibile cu 2 au ultima cifr a par a 0, 2, 4, 6, 8  si numerele
naturale mdivizibile cu 5 au ultima cifr a 0 sau 5.
Exemplu. a) 10j200;10j5000
b) 2j58;2j66
c) 5j245;5j8100
Criteriul de divizibilitate cu 100, respectiv cu 4 sau 25
Pentru ca un num ar natural ms a e divizibil cu 100, respectiv cu 4 sau 25
necesar  si su cient ca ultimele dou a cifre ale num arului ms a e 0, respectiv ca
num arul format din ultimele dou a cifre s a e divizibil cu 4 sau cu 25.
Exemplu. a) 100 j5000
b) 4j2032 pentru c a 4 j32
c) 25j7850 pentru c a 25 j50
Criteriul de divizibilitate cu 3, respectiv cu 9
Pentru ca un num ar natural ms a e divizibil cu 3, respectiv cu 9 este necesar
 si su cient ca suma S=a0+a1++ap1+aps a e divizibil a cu 3, respectiv
cu 9.
Exemplu. 32139…3
3 + 2 + 1 + 3 + 9 = 18
3j18;deci 3j32139
139977 = M9deoarece a0+a1+a2+a3+a4+a5= 7+7+9+9+3+1 = 36 = M9
Criteriul de divizibilitate cu 8
Pentru ca un num ar natural ms a e divizibil cu 8 este necesar  si su cient ca
suma S=a0+ 2a1+ 4a2s a e divizibil a cu 8. Mai putem spune c a suma dintre
dublul num arului de dou a cifre format din cifra sutelor  si cifra zecilor plus cifra
unit at ilor, este un num ar divizibil cu 8.
Exemplu. 453864…8
a0+ 2a1+ 4a2= 4 + 2 6 + 48 = 48…8)453864…8
sau 286 + 4 = 172…8
Criteriul de divizibilitate cu 11
Pentru ca un num ar natural ms a e divizibil cu 11 este necesar  si su cient
ca suma S=a0a1+a2a3+a4a5+: : :s a e divizibil a cu 11.
Exemplu. 563618 = M11deoarece a0a1+a2a3+a4a5= 81 + 6
3 + 65 = 11 = M11
Sau putem s a spunem c a un num ar natural se divide cu 11 dac a  si numai dac a
diferent a dintre suma cifrelor de rang par  si suma de rang impar din num arul
dat, se divide cu 11.

34 CAPITOLUL 2. NOT IUNI GENERALE
Exemplu. Fie num arul 72424
(a0+a2+: : :)(a1+a3+: : 🙂 = (4 + 4 + 7) (2 + 2) = 15 4 = 11 :
Deci 11 j72424 :
Criteriul de divizibilitate cu 7, respectiv cu 13
Un num ar natural se divide cu 7, respectiv 13, dac a  si numai dac a diferent a
dintre cele dou a numere naturale obt injte prin "t aierea " num arului dat ^ n dou a,
astfel ^ nc^ at la dreapta s a r ama^ an a un num ar de trei cifre, este divizibil a cu 7,
espectiv 13.
Exemplu. 398874…7
a2a1a0a5a4a3= 874 398 = 476 = 68 7, divizibil cu 7
83564…13
56483 = 481 ;481…13:
Criteriul de divizibilitate cu 19
Un num ar natural este divizibil cu 19 dac a  si numai dac a suma dintre dublul
cifrei unit at ilor  si num arul format din celelalte cifre, este divizibil a cu 19.
Exemplu. 47063…19
4706 + 2 3 = 4712
471 + 2 2 = 475
47 + 2 5 = 57
5 + 27 = 19…19
Criteriul de divizibilitate cu 27, respectiv 37
Pentru ca un num ar natural m=apap1: : : a 1a0s a e divizibil cu 27, re-
spectiv cu 37 este necesar  si su cient ca suma apap1: : : a 4a3+a2a1a0s a e
divizibil a cu 27, respectv 37.
Exemplu. 1236133…37
1 + 236 + 133 = 370…37
2.5 Divizibilitatea pe Z
^In acest paragraf ne propunem s a extindem anumite lucruri legate de divizibil-
itatea pe N, pe mult imea numerelor ^ ntregi.
De nit ia 2.5.1. Funct ia jj:Z!N, de nit a prin jaj= max( a; a) se nume ste
funct ia modul sau valoarea absolut a, iar jajse nume ste modului num arului a.
Propozit ia 2.5.2. Funct ia modul are propriet at ile:
1.ja+bj  jaj+jbj;
2.jabj=jaj  jbj;
3.jaj= 0,a= 0:
De nit ia 2.5.3. Fie numerele ^ ntregi a sib. Spunem c a adivide b si scriem ajb
dac a exist a un ^ ntreg castfel ^ nc^ at b=ac:

2.5. DIVIZIBILITATEA PE Z 35
Observat ia 2.5.4. i) 1ja;8a2Z;
ii)aj0;8a2Z;
iii) Ca  si ^ n cazul relat iei de divizibilitate de nite pe N, relat ia " j" este re-

exiv a ( 8a2Z)aja) si tranzitiv a ( ajb sibjc)ajc), dar nu mai este
antisimetric a. De exemplu: 2j2  si 2j2, dar 2̸= 2:
Dinajb sibjase obt ine jaj=jbj(spunem c a a sibsunt asociate ^ n diviz-
ibilitate).
iv) Dac a ajb1 siajb2)aj( 1b1+ 2b2), oricare ar 1; 22Z:
De nit ia 2.5.5. Fiea sibnumere ^ ntregi. Spunem c a un num ar ^ ntreg deste
un cel mai mare divizor comun al numerelor a; bdac a:
1)dja sidjb:
2) Pentru orice d′ja sid′jb, rezult a d′jd:
Un cel mai mare divizor comun al lui a sibeste unic determinat, mai put in o
asociere ^ n divizibilitate. Putem presupune c acesta este un num ar natural. Un
astfel de cel mai mare divizor comun este unic determinat  si ^ l not am d= (a; b).
^In mod canonic, convenim d= (a; b)0:
(a; b) = ( a;b) = (a; b) = (a;b) = (jaj;jbj)
(8;12) = (8 ;12) = 4
(60;70) = (60 ;70) = 10
Dac a ( a; b) = 1, spunem c a numerele a sibsunt prime ^ ntre ele saurelativ
prime .
Propozit ia 2.5.6. Fiea sibnumere ^ ntregi  si d= (a; b). Atunci a=a′d; b=
b′d, unde a′b′sunt numere ^ ntregi prime ^ ntre ele.
Din de nit ia celui mai mare divizor comun da dou a numere a sib, rezult a
c adj(ab). Euclid a folosit acest rezultat pentru a determina cel mai mare
divizor comun a dou a numere naturale folosind metoda sc aderii a num arului
mic din cel mare.
Exemplu. Alegem a= 34; b= 19. Algoritmul realizeaz a perechile urm atoare:
(a1; b1) = (34 ;19)
(a2; b2) = (19 ;3419) = (19 ;15)
(a3; b3) = (15 ;1915) = (15 ;4)
(a4; b4) = (15 4;4) = (11 ;4)
(a5; b5) = (11 4;4) = (7 ;4)
(a6; b6) = (4 ;74) = (4 ;3)
(a7; b7) = (3 ;43) = (3 ;1)
(a8; b8) = (3 1;1) = (2 ;1)
(a9; b9) = (2 1;1) = (1 ;1)
de unde obt inem c. m . m. m. c. (34 ;19) = c:m:m:d:c: (1;1) = 1 :
De nit ia 2.5.7. Fie 2R. De nim partea ^ ntreag a a num arului  si not am
[ ] cel mai mare num ar ^ ntreg ce nu dep a ste ste pe . Rezult a c a f g= [ ]2
[0;1)  si numim f gpartea fract ionar a a lui . Dac a a; b2Z; b > 0  sia=bq+r,
cuq sir2Z;0r < b , se constat a c a avem q=[a
b]
.
Teorema 2.5.8. (Algoritmul lui Euclid) Pentru orice dou a numere ^ ntregi
exist a un cel mai mare divizor comun.

36 CAPITOLUL 2. NOT IUNI GENERALE
Demonstrat ie. Fiea sibcele dou a numere ^ ntregi. Dac a b= 0, atunci ( a; b) =a.
Dac a b̸= 0, aplic am teorema ^ mp art irii cu rest.
Exist a q22Z; r22Nastfel ^ nc^ at a=bq2+r2;0r2<jbj: (2.3)
Dac a r2̸= 0;exist a q32Z; r32Nastfel ^ nc^ at b=r2q3+r3;0r3< r 2:(2.4)
Dac a r3̸= 0;exist a q42Z; r42Nastfel ^ nc^ at r2=r3q4+r4;0r4< r 3:
(2.5)
Dac a rk̸= 0;exist a qk+12Z; rk+12Nastfel ^ nc^ at rk1=rkqk+1+rk+1;0rk+1< rk:
(2.6)
:
:
:
Obt inem astfel c a resturile veri c a relat iile:
jbj> r 2> r 3>> rk> rk+10:
Dac a t inem cont c a mult imea numerelor naturale este bine ordonat a, exist a
un rand nastfel ^ nc^ at rn+1= 0:
Ultimele dou a relat ii din lant ul de ^ mp art iri cu rest sunt:
rn2=rn1qn+rn (2.7)
rn1=rnqn+1 (2.8)
Din relat ia (2.8) rezult a rn= (rn; rn1):
Din relat iile (2.7), . . . , (2.6), . . . , (2.4), (2.3) obt inem:
rn= (rn; rn1) = ( rn1; rn2) == (r2; r3) = ( b; r2) = ( a; b):
Pentru a uniformiza relat iile (2.3), (2.4), . . . , (2.8), facem notat iile a=r0 si
b=r1:Astfel, relat iile din algoritmul lui Euclid pot scrise sub forma:
rk1=rkqk+1+rk+1;1kn; rn+1= 0:
Obt inemrk1
rk=qk+1+rk+1
rkunde qk+12Z si 0rk+1
rk<1:
De aici putem concluziona c a qk+1=[rk1
rk]
:
Forma ^ n care folosim ^ mp art iri pentru a realiza algoritmul lui Euclid nu este
doar mai rapid a, ea are o aplicabilitate mult mai larg a dec^ at varianta sc aderilor
succesive. Aplicabitatea algoritmului pentru numere ^ ntregi se reduce la apli-
carea acestuia pentru numere naturale. ^In rolul lui bse poate alege cel mai mic
dintre cele dou a numere.
De nit ia 2.5.9. Pentru dou a numere ^ ntregi a sibspunem c a num arul ^ ntreg
meste cel mai mic multiplu comun al lor (scriem m=c:m:m:m:c: fa; bgsau
m= [a; b]) dac a:
1)ajm sibjm;
2)ajm′ sibjm′)mjm′:

2.6. NUMERE PRIME 37
Observat ia 2.5.10. Dac a m sim′sunt c. m. m. m. c. a dou a numere ^ ntregi
a sibatunci m sim′sunt asociative ^ n divizibilitate.
[30;24] = [30 ;24] = 120
[18;36] = [18 ;36] = 36
Teorema 2.5.11. (Teorema fundamental a a aritmeticii) Pentru orice
num ar ^ ntreg nenul n, exist a o descompunere a lui ^ n factori primi n= (1)a(n)∏
pprim
p2pe(p)cu exponent ii e(p)^ n mod unic determinat i de n.
Demonstrat ie. Produsul se poate scrie sub forma n=up 1
1p 2
2p ss, cu u
unitate, p1; : : : ; p snumere prime distincte  si 1; : : : ; s1:
Pentru un num ar prim qavem ordqn=ordqu+∑
p2P pordqp:
Cum ueste unitate, ordqu= 0; ord qp= 1, dac a p=q, astfel ordqp= 0.
Rezult a astfel c a 1=ordp1n; : : : ; s=ordps; n1:
Unicitatea descompunerii ^ n factori primi a fost prima dat a ment ionat a de
Karl Friedich Gauss ^ n anul 1801. Forma canonic a a descompunerii este aceea de
a scrie num arul ca produs de numere prime distincte la puterile corespunz atoare,
^ n ordine cresc atoare, de exemplu 12600 = 2339527:
2.6 Numere prime
Numerele prime pot privite ca blocuri din care se formeaz a numerele naturale,
cum orice num ar natural 2 este produs de numere prime.
Teorema 2.6.1. (Teorema numerelor prime) Enunt  am urm atoarea teore-
ma a:
lim
n!1((n)
n
lnn)
= 1, unde (n) =num arul numerelor prime < n.
Teorema 2.6.2. Pentru orice num ar natural n1, exist a cel put in nnumere
naturale compuse consecutive.
Demonstrat ie. Consider am numerele ( n+1)!+2 ;(n+1)!+3 ; : : : ; (n+1)!+ n+1:
Este evident c a pentru 2 kn+ 1; kj(n+ 1)! + k, deci cele nnumere
construite init ial sunt toate compuse.
Teorema 2.6.3. (Dirichlet) Fiea sibnumere naturale prime ^ ntre ele. Atun-
ci, progresia aritmetic a an+b; n1cont ine o in nitate de numere prime.
Teorema 2.6.4. Exist a o in nitate de numere prime de forma 4n1, cu
n2N:
Demonstrat ie. S a presupunem prin reducere la absurd c a mult imea f4n1; n2
Ngcont ine numai un num ar nit de numere prime, e acestea q1; : : : ; q t si s a
consider am num arul q= 4q1q2: : : q t1. Num arul qtrebuie s a aib a un factor
prim de forma 4 k1(dac a tot i factorii primi ai lui qar de forma 4 k+ 1 ,
atunci  si qar trebui s a e de forma 4 k+ 1) deci ar trebui ca qis a devid a q, ceea
ce este absurd, de unde concluzia din enunt .
Teorema 2.6.5. Exist a o in nitate de numere prime de forma 6n1, cu
n2N:

38 CAPITOLUL 2. NOT IUNI GENERALE
Demonstrat ie. S a presupunem prin absurd c a exist a doar un num ar nit de
numere prime de forma 6 n1  si anume q1; q2; : : : ; q k si s a consider am num arul
q= 6q1q2: : : q k1. Cum un num ar prim este de forma 6 t1 sau 6 t+1, deducem
c aqtrebuie s a cont in a un factor prim de forma 6 t1. Deci ar trebui ca qis a
divid a pe q, ceea ce este absurd, de unde rezult a concluzia din enut .
Una din celebrele probleme nerezolvate despre numerele prime este urm atoarea
a rmat ie, ^ nt^ alnit a  si sub numele de Conjectura lui Goldbach- Orice num ar
par mai mare sau egal dec^ at 4 este suma a dou a numere prime impare.
I. Vinogradov a ar atat c a orice num ar impar su cient de mare este suma a
trei numere prime, iar V. Brun a probat c a orice num ar par su cient de mare
este suma a dou a numere, ecare av^ and cel mult 9 factori primi.
O problem a nerezolvat a este  si aceea dac a exist a o in nitate de numere
p2Ppentru care  si p+ 22P(p sip+ 2 se numesc numere prime gemene. )^In
leg atur a cu aceasta, J. R. Chen a demonstrat c a exist a o in nitate de numere
p2Ppentru care  si p+ 22Psaup+ 2 are doi factori primi ^ n descompunerea
canonic a.
O alt a problem a di cil a nerezolvat a este aceea dac a exist a o in nitate de
numere prime de forma n2+ 1( Hua a ar atat c a pentru o in nitate de numere
navem n2+ 12Psaun2+ 1 este produs de dou a numere prime).
Ciurul lui Eratostene
Propozit ia 2.6.6. Dac a n2, iar neste un num ar compus(reductibil), atunci
exist a p2Pastfel ^ nc^ at ppn sipjn.
Demonstrat ie. Dac a n=p1:::ps, unde p1   ps; s2, atunci p1pn:
Corolarul 2.6.7. Fien2. Dac a pentru orice p2P, cuppnavem p̸ jn,
atunci neste num ar prim.
Corolarul pune ^ n evident  a un algoritm de construire a  sirului numerelor
prime, algoritm numir ciurul lui Eratostene.
Iat a un tabel cu c^ ateva numere prime:
n 12310 25 100 200 1000 129 1230
pn23529 97 541 1223 7917 9973 10007

Capitolul 3
Funct ii aritmetice
3.1 De nit ii  si exemple
Prin funct ie aritmetic a se ^ nt elege o funct ie av^ and ca domeniu de de nit ie
mult imea Na numerelor naturale. ^In particular, orice  sir ( an)n2Neste o
funct ie aritemtic a.
Exemplu. 1)d(n) =num arul divizorilor pozitivi ai lui n.
2)(n) = suma divizorilor pozitivi ai lui n.
3)φ:N!R; φ(n) =jfk2Nj1kn;(k; n) = 1g, indicatorul lui Euler.
Teorema 3.1.1. Dac a un num ar n >1, are descompunerea n=pa1
1pa2
2pak
k,
atunci d(n) = ( a1+ 1)( a2+ 1): : :(ak+ 1)
(n) =pa1+1
11
p11pa2+1
21
p21:::pak+1
k1
pk1:
Exemplu. 1) Pentru 72 = 2332avem d(72) = (3 + 1) (2 + 1) = 4 3 = 12
2)(72) =241
21331
31= 195
3) Pentru 210 = 2 357 avem d(210) = (1 + 1) (1 + 1) (1 + 1) (1 + 1) = 16
4)(210) =221
21321
31521
51721
71= 576
Exemplu. S a se arate c a d(n) este impar dac a  si numai dac a neste p atrat
perfect.
Solut ie. Se  stie c a pentru n=p 1
1p 2
2:::p rr; pi2P; i2N; i=1; r; d(n) =
r∏
j=1( j+ 1); d(1) = 1 :
d(n) este impar , i+ 1 este impar , i= 2 i; i=1; r:
A sadar n=r∏
i=1p i
i,n= (r∏
i=1p i
i)2:
Exemplu. S a se arate c a exist a o in nitate de numere compuse n, pentru care
(n) se divide cu d(n):
Alegem n=p3, cu pprim  si avem(n)
d(n)=1+p+p2+p3
4=(1+p)(p2+1)
42N
deoarece p+ 1  si p2+ 1 sunt pare.
39

40 CAPITOLUL 3. FUNCT II ARITMETICE
3.2 Funct ia lui M obius
De nit ia 3.2.1. Not am P=f2;3;5; : : : ;gmult imea numerelor prime. Fie
funct ia :N!Z, de nit a astfel:
f(n) =8
<
:1 ,dac a n= 1
0 ,dac a9p2Pastfel ^ nc^ at p2jn
(1)k, dac a n=p1p2:::pk, cup1; : : : ; p kprime distincte
Aceast a funct ie se nume ste funct ia lui M obius.
Propozit ia 3.2.2. Fien2N.∑
djn(d) ={1 ,dac a n= 1
0 ,dac a n̸= 1
(suma se face dup a tot i divizorii pozitivi ai lui n).
Demonstrat ie. Dac a n2N, atunci putem scrie n=p 1
1p 2
2:::p k
k, unde
k1, iar p12Psunt distincte.
djn)d=p 1
1p 2
2:::p k
k, unde 0  i i:
Avem∑
djn(d) =∑
0 i i
1;:::; k(p 1
1:::p k
k) =∑
i2f0;1g(p 1
1:::p k
k) =∑
Af1;2;:::;kg(1)jAj=
k∑
i=0(1)iCi
k= (11)k= 0:
Teorema 3.2.3. Teorema de inversiune a lui M obius Fief:N!C, o
funct ie aritmetic a.
De nim F:N!Cprin F(n) =∑
djnf(d).
Atunci avem identitatea:
f(n) =∑
djnF(d)(n
d)
=∑
djn(d)F(n
d)
:
Demonstrat ie. Not^ and S=∑
djn(d)F(n
d)
, atunci S=∑
djn((d)∑
djd
nf()):Dar
jn
d,djn,djd
:Deci S=∑
jn(f()∑
djn
(d)):
Cum∑
djn
(d) ={1 ,dac a =n
0 ,dac a  < n, rezult a S=f(n):
3.3 Indicatorul lui Euler
De nit ia 3.3.1. Funct ia φ:N!R, de nit a prin φ(n) =jfk2Nj1k
n;(k; n) = 1gjse nume ste funct ia sau indicatorul lui Euler. Altfel spus, φ(n)
este num arul numerelor naturale nenule mai mici dec^ at n si relativ prime cu n.
Propozit ia 3.3.2. Are loc egalitatea∑
djnφ(d) =n(suma se face dup a tot i divi-
zorii pozitivi ai lui n).
Demonstrat ie. FieA={1
n;2
n; : : : ;n
n}
, mult imea tuturor fract iilor mai mici sau
egale cu unitatea, av^ and numitorul n. Avem A=∪
djnAd, unde Adeste mult imea
fract iilor din Acare, ^ n form a ireductibil a, au numitorul d.

3.3. INDICATORUL LUI EULER 41
Ad={k
n 9l;1ld;k
n=l
d;(l; d) = 1}
:
Deoarece mult imea Adconstituie o partit ie a lui A, avem n=jAj=∑
djnAd:
CumjAdj=φ(d), deducem relat ia n=∑
djnφ(d):
Observat ia 3.3.3. Folosind propozit ia de mai sus  si aplic^ and teorema de in-
versiune a lui M obius, obt inem:
φ(d) =∑
djn(d)n
d; (3.1)
egalitate ce permite deducerea unei formule pentru φ(n), plec^ and de la descom-
punerea canonic a a lui n.
Dac a 1 < n=p 1
1:::p k
k; piprimi, atunci ^ n relat ia (3.1) suma se va face
doar dup a divizorii liberi de p atrate, deci putem scrie:
φ(d) =∑
djn(d)n
d=∑
i2f0;1g(p 1
1:::p k
k)n
p 1:::p k
k
1=
=nk∑
i=1n
pi+∑
1i<jkn
pipj=n(11
p1):::(11
pk):
Exemplu. φ(1) = 1
φ(2) = cardf1g= 1
φ(3) = cardf1;2g= 2
φ(5) = cardf1;2;3;4g= 4
φ(29) = cardf1;2;3; : : : ; 28g= 28
^In general, φ(p) =p1; p2 un num ar prim.
φ(4) = cardf1;3g= 2
φ(6) = cardf1;5g= 2(mult imea numerelor prime cu 6, mai mici dec^ at 6).
De nit ia 3.3.4. 1) O funct ie f:N!Cse nume ste funct ie multiplicativ a,
dac a oricare ar m; n2N, cu ( m; n) = 1, avem f(mn) =f(m)f(n):
2) O funct ie f:N!Cse nume ste funct ie total multiplicativ a, dac a oricare
ar m; n2N, avem f(mn) =f(m)f(n):
Funct iile φ;   sidsunt funct ii multiplicative.
Exemplu. φ(210) =?(C^ ate numere prime cu 210  si mai mici dec^ at 210 exist a?)
210 = 6 35
(6;35) = 1 )φ(210) = φ(635) = φ(6)φ(35) = A
6 = 23
35 = 5 7
(2;3) = 1
(5;7) = 1
Rezult a c a A=φ(2)φ(3)φ(5)φ(7) = 1 246 = 48 :
Propozit ia 3.3.5. Fiem; n2N si mult imile A=f(d1; d2)jd12N; d22
N; d1jm; d 2jm;(d1; d2) = 1g siB=fdjd2N; djmng. Atunci jAj=jBj:

42 CAPITOLUL 3. FUNCT II ARITMETICE
Demonstrat ie. Exist a o corespondent  a biunivoc a natural a^ ntre elementele mult imilor
A siB, anume ( d1; d2) d=d1d2, unde d1= (d; m); d2= (d; n). Egalitatea
(d; m)(d; n 0) =dasigur a faptul c a^ ntre mult imile A siBexist a o corespondent  a
biunivoc a.
Propozit ia 3.3.6. Fief:N!Co funct ie multiplicativ a. Atunci  si funct ia
F:N!C; F(n) =∑
djnf(n)este o funct ie multiplicativ a.
Demonstrat ie. Fiem; n2Ncu (m; n) = 1. Atunci F(m)F(n) = (∑
d1jmf(d1))(∑
d2jnf(d2)) =
∑
d1jm;d 2jnf(d1)f(d2) =∑
d1d2jmnf(d1d2) =F(mn):
Observat ia 3.3.7. Dac a feste o funct ie multiplicativ a, atunci feste bine
determinat a de valorile ale pe elementele mult imii fpkjp2P; k0g.

Copyright Notice

© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.

Acest articol: Lect. univ. Stelian Corneliu ANDRONESCU Absolvent: Ioan-Andrei POPESCU { 2017 { 2 Cuprins 1MULT IMEA N, LEGILE DE COMPOZIT IE, BUNA ORDONARE,… [618050] (ID: 618050)

Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.

Similar Posts