Divizibilitate n N siZ [631551]

Note de curs
Divizibilitate ^ n N siZ
1 Relat ia de divizibilitate ^ n N
Denit ie 1.1. Fiea, bnumere naturale. Spunen c a adivide b si scriem
a|bdac a exist a un num ar natural uastfel ^ nc^ at b=au.^In acest caz, mai
spunem c a aeste un divizor al lui bsaubeste multiplu al lui asaubse
divide cu a.
Observat ie 1.2. Din Teorema de ^ mp art ire cu rest ^ n Nrezult a c a dac a
a̸= 0,atunci a|bdac a  si numai dac a restul ^ mp art irii lui blaaeste nul.
Exercit iu 1.3. Relat ia de divizibilitate pe Neste o relat ie de ordine part ial a.
Identicat i cel mai mic  si cel mai mare element al lui Nrelativ la aceast a
relat ie de ordine.
Exercit iu 1.4. Dac a a|aipentru 1 ≤i≤n, atunci a|∑n
i=1xiaipentru orice
numere naturale x1, . . . , x n.
Exercit iu 1.5. (1)Dac a a|b sib̸= 0,atunci 1 ≤a≤b.
(2)Dac a d|a, d|b sia=b+c,atunci d|c.
Denit ie 1.6. Un num ar natural p >1se nume ste prim dac a pentru orice
a, b∈N, p|ab⇒p|asaup|b.
Un num ar natural q >1se nume ste indecompozabil (sau ireductibil) dac a
pentru orice d∈N, d|q⇒d= 1 saud=q,adic a qnu are alt i divizori ^ n
afara lui 1 si a lui ^ nsu si. Un num ar natural a >1se nume ste decompozabil
dac a nu este indecompozabil.
Exercit iu 1.7. Negat i denit ia num arului prim  si a celui indecompozabil.
Lema 1.8. Fiea > 1un num ar natural. Urm atoarele armat ii sunt echi-
valente:
(1)aeste decompozabil;
(2)exist a b, c∈Nastfel ^ nc^ at a=bc si1< b < a, 1< c < a.
Matematic a Didactic a Anul I
1

Viviana Ene
Demonstrat ia este evident a  si o l as am ca exercit iu.
Lema 1.9. Orice num ar natural a >1admite un divizor indecompozabil.
Demonstrat ie. Fiea∈N, a > 1  siA={d∈N:d > 1, d|a}.Cum a∈A,
rezult a c a mult imea Aeste nevid a. Fie q= min A.Atunci q > 1.Dac a
qeste decompozabil, din Lema 1.8 rezult a c a qare un divizor 1 < d < q.
Evident, d∈A.Dar acest lucru contrazice alegerea lui q,prin urmare, qeste
indecompozabil.
Teorema 1.10. Fiep > 1un num ar natural. Atunci peste prim dac a  si
numai dac a este indecompozabil.
Demonstrat ie. Fiepprim. Dac a peste decompozabil, din Lema 1.8, exist a
b, c∈Nastfel ^ nc^ at p=bc si 1< b < p, 1< c < p. Cum peste prim, obt inem
p|bsaup|c,deci p≤bsaup≤c,contradict ie.
Reciproc, s a presupunem c a exist a numere naturale indecompozabile care
nu sunt prime. Fie pcel mai mic asemenea num ar. Cum pnu este prim,
exist a b, c∈Nastfel ^ nc^ at p|bc sip̸ |b, p̸ |c.Putem alege b, castfel ^ nc^ at
produsul bcs a e minim. Evident, b̸= 0 (altfel p|b)  sib̸= 1 (altfel p|c). Deci
b >1.Dac a b≥p,aplic am Teorema de ^ mp art ire cu rest ^ n N si obt inem
b=pq+rcuq, r∈N sir < p. Nu putem avea r= 0 deoarece p̸|b.
Rezult a bc=pqc+rc,deci p|rc < bc, contradict ie cu alegerea produslui bc.
In concluzie, obt inem 1 < b < p. Analog deducem  si 1 < c < p.
Dinp|bcrezult a c a exist a u∈Nastfel ^ nc^ at bc=pu.Avem u >1 (altfel
p=bc,decipeste decompozabil, contradict ie cu ipoteza). Fie p1un divizor
indecompozabil al lui u. Existent a acestuia este asigurat a de Lema 1.9.
Din pu=bc < p2rezult a c a u < p, deci p1≤u < p. Din alegerea lui
p, p 1este num ar prim. Cum p1|bc,avem p1|bsaup1|c.S a presupunem c a
p1|b.Fieu=p1u1 sib=p1b1.Cum bc=pu,reult a p1b1c=pp1u1,adic a
b1c=pu1.Darp̸ |b1pentru c a p̸ |b sip̸ |c.Darb1c < bc , ceea ce contrazice
alegerea produsului bc.Prin urmare, presupunerea f acut a este fals a, deci
orice indecompozabil este prim.
2 Teorema fundamental a a aritmeticii
Teorema 2.1 (Teorema fundamental a a aritmeticii) .Orice num ar natural
a >1se descompune ^ n mod unic (p^ ana la ordinea factorilor) ^ n produs nit
de numere prime.
Demonstrat ie. Existent a descompunerii. S a presupunem c a exist a numere
naturale a > 1 care nu au proprietatea din enunt . Fie Amult imea acestor
Matematic a Didactic a Anul I
2

Note de curs
numere. Avem A̸=∅,deci exist a b= min A.Cum b >1  sibnu este prim, re-
zult a c a beste decompozabil, deci b=xycux, y∈N si 1< x < b, 1< y < b.
Atunci x, y̸∈A,deci x, yse pot scrie ca produse nite de numere naturale
prime. Dar atunci  si bse poate scrie ca un produs nit de numere naturale
prime, contradict ie.
Unicitatea descompunerii. Fie a > 1  sia=p1···pn=q1···qmdou a
descompuneri ale lui a^ n produs nit de numere naturale prime. Cum
p1|q1···qmrezult a c a exist a jastfel ^ nc^ at p1|qj.Renumerot^ and eventual fac-
torii din al doilea produs, putem presupune c a p1|q1.Cum q1este indecom-
pozabil  si p1̸= 1,obt inem p1=q1.Dac a n= 1,obt inem p1=p1q2···qm,
deci m= 1.Dac a n > 1,aplic am induct ie dup a n: presupunem unicitatea
adev arat a pentru toate numerele naturale b >1 care au n−1 factori ^ n des-
compunere. Cum p2···pn=q2···qm=b,din ipoteza de induct ie, rezult a
m−1 =n−1  sipj=qjpentru orice jdup a o eventual a renumerotare a
factorilor din al doilea produs.
Observat ie 2.2. Fiea >1 un num ar natural. Grup^ and factorii primi egali
^ n descompunerea lui a,rezult a c a ase poate scrie ^ n mod unic sub forma
a=pα1
1···pαmm, unde p1, . . . , p msunt numere prime distincte  si exponent ii
α1, . . . , α msunt numere naturale nenule. In plus, se poate demonstra u sor
folosind Teorema fundamaental a a aritmeticii, c a dac a d∈N,atunci d|a
dac a  si numai dac a pβ1
1···pβmmcu 0≤βi≤αipentru orice 1 ≤i≤m.
Presupunem cunoscute denit iile pentru cel mai mare divizor comun  si
cel mai mic multiplu comun, gcd( a, b),lcm(a, b),pentru numerele naturale
a, b. Folosind descompunerea din observat ia anterioar a deducem c a dac a a, b
au descompunerile a=pα1
1···pαmm, b=pβ1
1···pβmmcuα1, . . . , α m, β1, . . . , β m≥
0,atunci
gcd(a, b) =pmin{α1,β1}
1 ···pmin{αm,βm}
m ,lcm(a, b) =pmax{α1,β1}
1 ···pmax{αm,βm}
m .
3 Teorema de ^ mp art ire cu rest ^ n Z
Teorema 3.1. Fien, d∈Zcud̸= 0.Atunci exist a  si sunt unice numerele
^ ntregi q, rastfel ^ nc^ at n=dq+r si0≤r <|d|.
Numerele q sirse numesc c^ atul  si restul ^ mp art irii lui nlad.
Demonstrat ie. Existent a. Dac a n= 0,lu am q=r= 0.Dac a n, d > 0,
aplic am Teorema de ^ mp art ire cu rest ^ n N.
Fied >0  sin <0.G asim q′, r′numere naturale astfel ^ nc^ at −n=q′d+r′
cu 0≤r′< d. Dac a r′= 0,atunci n= (−q′)d si lu am q=−q′ sir= 0.
Matematic a Didactic a Anul I
3

Viviana Ene
Dac a r′>0,scriem n=−q′d−r′=−(q′+1)d+d−r′.Atunci q=−(q′+1)
 sir=d−r′.Evident, 0 < r < d.
Dac a d < 0,din demonstrat ia anterioar a, g asim q′, r′cu 0≤r′<−d
astfel ^ nc^ at n=−dq′+r′.In acest caz, r=r′ siq=−q′.Unicitatea se
demonstreaz a ca la numere naturale.
4 Divizibilitate ^ n Z
Denit ie 4.1. Fied, n numere ^ ntregi. Spunen c a ddivide n si scriem
d|ndac a exist a un num ar ^ ntreg uastfel ^ nc^ at n=du.^In acest caz, ca  si
la numere naturale, mai spunem c a deste un divizor al lui nsauneste
multiplu al lui dsaunse divide cu d.
Observat ie 4.2. Din Teorema de ^ mp art ire cu rest ^ n Zrezult a c a dac a
d̸= 0,atunci d|ndac a  si numai dac a restul ^ mp art irii lui nladeste nul.
Observat ie 4.3. Divizibilitatea pe Zeste re
exiv a  si tranzitiv a, dar, evi-
dent, nu este antisimetric a, deci nu este o relat ie de ordine pe Z.
Denit ie 4.4. Numerele ^ ntregi a, bse numesc asociate ^ n divizibilitate dac a
a|b sib|a.
Exercit iu 4.5. Demonstrat i c a asocierea ^ n divizibilitate este o relat ie de
echivalent  a pe Z si ar atat i c a mult imea factor este ^ n biject ie cu N.
Presupunem cunoscute not iunile de cel mai mare divizor comun  si cel mai
mic multiplu comun pentru dou a numere ^ ntregi. Pentru a, b∈Z,not am
cu gcd( a, b)  si lcm( a, b) numerele naturale care sunt cel mai mare divizor
comun  si cel mai mic multiplu comun al numerelor a, b.
Algoritmul lui Euclid de determinare a celui mai mare divizor comun
pentru doi ^ ntregi a, bse bazeaz a pe urm atoarea
Teorema 4.6. (a)Dac a a∈Z,gcd(a,0) =|a|.
(b)Dac a b > 0 sia≥0,atunci gcd(a, b) = gcd( b, r),unde reste restul
^ mp art irii lui alab.
Demonstrat ie. Pentru ( b) se aplic a Teorema ^ mp art irii cu rest ^ n Z.
Algoritmul este urm atorul:
Input: a, b∈Z;
Output: d= gcd( a, b);
Matematic a Didactic a Anul I
4

Note de curs
1.a:=|a|, b:=|b|;
2. Dac a b= 0 atunci d:=aaltfel
d:=amod b;
a:=b;
b:=d;
3. Mergi la pasul 2.
Teorema 4.7. Algoritmul lui Euclid calculeaz a gcd(a, b)pentru a, b∈Z.
Demonstrat ie. Fier0=|a| sir1=|b|.Pentru k≥1  sirk̸= 0,denim
rk+1ca ind restul ^ mp art irii lui rk−1lark.Algoritmul de mai sus calculeaz a
 sirul de resturi rk, k≥1.Datorit a egalit at ilor gcd( rk−1, rk) = gcd( rk, rk+1),
pentru k≥1, si a faptului c a exist a un kastfel ^ nc^ at rk+1= 0,(avem un  sir
strict descresc ator de numere naturale), rezult a c a d= gcd( a, b) este ultimul
rest nenul din algoritmul lui Euclid.
Exemplu 4.8.
gcd(100 ,35) = gcd(35 ,100 mod 35) = gcd(35 ,30) = gcd(30 ,5) = 5 .
Teorema 4.9. Fiea, b∈Z sid= gcd( a, b).Atunci exist a u, v∈Zastfel
^ nc^ at d=au+bv.
Demonstrat ie. Dac a a= 0,atunci gcd( a, b) =|b| si putem alege u= 0  si
v= 1 sau v=−1,^ n funct ie de semnul lui b.
Fiea, b̸= 0  si S={xa+yb:x, y∈Z}.Cum a, b̸= 0, Scont ine  si
numere ^ ntregi nenule. In plus, dac a xa+yb∈S,atunci −xa−yb∈S,deci
Scont ine numere ^ ntregi strict pozitive. Fie d=au+bvcel mai mic num ar
^ ntreg strict pozitiv din S.Vom demonstra c a d= gcd( a, b).In primul r^ and
trebuie s a demonstr am c a d|a sid|b.
Din Teorema de ^ mp art ire cu rest avem a=dq+rcu 0≤r < d. Dac a
r̸= 0,atunci r=a−dq=a−(au+bv) =a(1−u)+b(−v)∈S,contradict ie
cu alegerea lui d.Prin urmare, d|a.Analog se demonstraez a c a d|b.
Fied′|a sid′|b.Atunci d′|d= (au+bv).
5 Congruent e ^ n Z
Reamintim relat ia de congruent  a modulo npeZ,unde n∈N: pentru
x, y∈Z,avem x≡ymod ndac a n|(x−y).Am v azut c a ^ n cazurile n= 0,1
se obt in relat iile de egalitate  si relat ia grosier a pe Z.De aceea, in cele ce
urmeaz a, vom considera n≥2.
Observat ie 5.1. Avem x≡ymod ndac a  si numai dac a x, y dau acela si
rest la ^ mp art irea cu n.
Matematic a Didactic a Anul I
5

Viviana Ene
Mult imea factor Z/≡mod nse noteaz a Zn.Un sistem complet de
reprezentant i pentru congruent a modulo neste mult imea {0,1, . . . , n −1},
deciZn={^0,^1, . . . , ^n−1},unde ^ aeste clasa de echivalent  a a lui a.
Propozit ie 5.2. Fiet∈Zcugcd(t, n) = 1 .Atunci exist a o unic a clas a
^u∈Znastfel ^ nc^ at ^u^t=^1.
Demonstrat ie. Existent a. Din ipotez a, rezult a c a exist a u, v∈Zastfel ^ nc^ at
ut+vn= 1,deci ^ u^t=^1.
Unicitatea. Fie ^u′∈Znastfel ^ nc^ at ^u′^t=^1.Prin urmare, n|u′t−1,de
unde n|u′ut−u=u′(1−vn)−u.Rezult a n|u′−u−vu′n,ceea ce implic a
n|u′−u,adic a ^u′= ^u.
Clasa ^ use nume ste inversa clasei ^t^ nZn.
Teorema 5.3. Fiea, b∈Z si congruent a
ax≡bmod n. (1)
(i)Dac a gcd(a, n) = 1  siueste inversul lui amodulo n,atunci solut ia
congruent ei (1) este x≡ubmod n.
(ii) Dac a d= gcd( a, n)>1 sid̸ |b,congruent a (1) nu are nicio solut ie.
(iii) Dac a d= gcd( a, n)>1 sid|b,atunci congruent a (1) este echivalent a
cu congruent a a1x≡b1mod munde n=dm, a =da1 sib=db1.
Demonstrat ie. (i).Cum ua≡1 mod n,congruent a (1) este echivalent a cu
x≡ubmod n.
(ii).Presupunem c a congruent a (1) are solut ia x∈Z.Atunci n|(ax−b).
Rezult a c a d|(ax−b).Cum d|a,obt inem  si d|b,contradict ie.
(iii).Avem: n|ax−b⇔m|a1x−b1.
Exercit iu 5.4. Rezolvat i congruent ele:
(1)5x≡7 mod 12 .
(2)3x≡6 mod 101 .
(3)2x≡7 mod 10 .
(4)2x≡8 mod 10 .
Teorema 5.5 (Teorema chinez a a resturilor) .Fien, m≥2numere naturale
cugcd(n, m) = 1  sia, b∈Z.Atunci sistemul de congruent e
x≡amod m, x≡bmod n
are o unic a solut ie modulo mn.
Matematic a Didactic a Anul I
6

Note de curs
Demonstrat ie. Cum gcd( n, m) = 1 exist a u, v∈Zastfel ^ nc^ at um+vn= 1.
Fiex=umb +vna. Atunci x−a=umb + (vn−1)a=um(b−1),adic a
x≡amod m.Analog se demonstraez a c a x≡bmod n.Deci sistemul are
solut ii.
Unicitatea modulo mn. Fiex, ysolut ii ale sistemului de congruent e din
enunt . Atunci x≡ymod m six≡ymod n.Cum gcd( m, n) = 1 ,obt inem
x≡ymod mn.
Exercit iu 5.6. Rezolvat i sistemul de congruent e
3x≡1 mod 4 ,5x≡2 mod 7 .
6 Indicatorul lui Euler
Dac a n∈N, n≥2, φ(n) este num arul de numere naturale cuprinse ^ ntre 1
 sincare sunt relativ prime cu n.Cu alte cuvinte,
φ(n) =|{a∈N: 1≤a≤n,gcd(a, n) = 1}|.
Funct ia n7→φ(n) se nume ste indicatorul lui Euler .
Teorema 6.1. Dac a n=pa1
1···parr, unde p1, . . . p rsunt numere prime dis-
tincte  si a1, . . . , a rsunt ^ ntregi strict pozitivi, atunci
φ(n) =n(
1−1
p1)
···(
1−1
pr)
.
Demonstrat ie. FieA={a∈N: 1≤a≤n,gcd(a, n) = 1}.Atunci φ(n) =
|A|.Evident, A= [n]\B,unde [ n] ={1,2, . . . , n } siB={a∈N: 1≤
a≤n,gcd(a, n)>1}.Evident, gcd( a, n)>1 dac a  si numai dac a exist a
1≤i≤rastfel ^ nc^ at pi|a.Rezult a c a putem scrie B=B1∪ ··· ∪ Br,unde
Bi={a∈N: 1≤a≤n, p i|a}pentru orice 1 ≤i≤r.Deducem u sor c a
|Bi|=n/p ipentru orice 1 ≤i≤r.In plus, dac a 1 ≤i1<···< i k≤r,
a∈Bi1∩ ··· ∩ Bikdac a  si numai dac a pi1···pik|a,deci|Bi1∩ ··· ∩ Bik|=
n/p i1···pik.Atunci, conform Principiului includerii  si excluderii, deducem
|B|=r∑
i=1n
pi−∑
1≤i<j≤rn
pipj+···+(−1)k−1∑
1≤i1<···<ik≤rn
pi1···pik+···+(−1)r−1n
p1···pr:
Obt inem
φ(n) =n(
1−∑
1≤i<j≤r1
pipj+···+ (−1)r−11
p1···pr)
,
ceea ce conduce la formula din enunt .
Corolar 6.2. Indicatorul lui Euler este funct ie multiplicativ a, adic a, pentru
orice m, n∈N, m, n ≥2,dac a gcd(m, n) = 1 ,atunci φ(mn) =φ(m)φ(n).
Matematic a Didactic a Anul I
7

Viviana Ene
7 Mica teorem a a lui Fermat
Urm atoarea teorem a, cunoscut a sub numele de Mica teorem a a lui Fermat
pentru a o distinge de o alt a celebr a teorem a datorat a lui Fermat, a fost
enunt at a ^ n anul 1640.
Teorema 7.1. Dac a peste un num ar natural prim  si a∈Nnu se divide cu
p,atunci ap−1≡1 mod p.
Aceast a teorem a se obt ine ca un corolar al teoremei urm atoare.
Teorema 7.2. Dac a a, n∈N sigcd(a, n) = 1 ,atunci aφ(n)≡1 mod n.
Demonstrat ie. FieP={a1, . . . , a φ(n)}mult imea numerelor naturale mai
mici dec^ at n si prime cu n.Cum aeste prim cu n,obt inem
aP={aa1mod n, . . . , aa φ(n)mod n}=P.
Rezult a c a
φ(n)∏
i=1aai≡φ(n)∏
i=1aimod n,
deci
aφ(n)φ(n)∏
i=1ai≡φ(n)∏
i=1aimod n.
Cum∏φ(n)
i=1aieste prim cu ndeoarece aieste prim cu npentru orice 1 ≤
i≤φ(n),rezult a c a aφ(n)≡1 mod n.
Exercit iu 7.3. Deducet i Teorema 7.1 din Teorema 7.2.
8 Teorema lui Wilson
Teorema 8.1. Un num ar natural p≥2este prim dac a  si numai dac a
(p−1)!≡ −1 mod p.
Demonstrat ie. Fiep≥2 num ar prim. Atunci, pentru a∈ {1, . . . , p −1},
ecuat ia ax≡1 mod pare o unic a solut ie a′∈ {1, . . . , p −1}.Dac a a=a′,
atunci a2≡1 mod p,deci a≡ ± 1 mod p.Rezult a c a, pentru orice a∈
{2,3, . . . , p −2},avem a′̸=a.^In acest caz, grup^ and ^ n perechi a si inversul
s aua′,obt inem 2 ·3···(p−2)≡1 mod p.Prin urmare, ( p−1)!≡ −1 mod p.
Pentru implicat ia reciproc a, se demonstreaz a c a dac a n > 4 este decompo-
zabil, atunci ( n−1)!≡0 mod n.Pentru n= 4,avem 3! ≡2 mod 4 .
Matematic a Didactic a Anul I
8