Lect. univ. Stelian- Corneliu Andronescu Absolvent a: Maria- Luciana Voican { 2016 { 2 Cuprins 1 Not iuni introductive 5 1.1 Mult imea numerelor… [608179]

UNIVERSITATEA DIN PITES TI
FACULTATEA DE MATEMATIC A-INFORMATIC A
LUCRARE DE LICENT  A
CONGRUENT E POLINOMIALE
Coordonator  stiint ic:
Lect. univ. Stelian- Corneliu Andronescu
Absolvent a:
Maria- Luciana Voican
{ 2016 {

2

Cuprins
1 Not iuni introductive 5
1.1 Mult imea numerelor naturale . . . . . . . . . . . . . . . . . . 5
1.1.1 Axiomatica Peano . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Legi de compozit ie ^ n mult imea N. . . . . . . . . . . . 6
1.1.3 Relat ia de ordine natural a pe mult imea N. . . . . . . 7
1.1.4 A doua form a a principiului induct iei . . . . . . . . . . 8
1.1.5 Propriet at i ale lui N. . . . . . . . . . . . . . . . . . . 8
1.2 Mut imea numerelor ^ ntregi Z. . . . . . . . . . . . . . . . . . 10
1.2.1 Construct ia mult imii Z. . . . . . . . . . . . . . . . . . 10
1.2.2 Unicitatea c^ atului  si a restului . . . . . . . . . . . . . . 11
1.2.3 Algoritmul lui Euclid . . . . . . . . . . . . . . . . . . . 12
2 Congruent e 15
2.1 Denit ii. Propriet at i de baz a . . . . . . . . . . . . . . . . . . . 15
2.1.1 Not iuni generale . . . . . . . . . . . . . . . . . . . . . 15
2.2 Not iuni ajut atoare . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Numere asociate . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Numere Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.5 Congruent e liniare . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Congruent e polinomiale . . . . . . . . . . . . . . . . . . . . . 28
2.7 Congruent e polinomiale ^ n mai multe variabile . . . . . . . . . 34
2.8 Simbolul lui Legendre . . . . . . . . . . . . . . . . . . . . . . . 39
2.9 Propriet at i ale simbolului lui Legendre . . . . . . . . . . . . . 41
2.10 Legea reciprocit at ii p atratice . . . . . . . . . . . . . . . . . . . 42
2.11 Ordinul unui num ar modulo n . . . . . . . . . . . . . . . . . . 44
2.12 R ad acini primitive . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Probleme referitoare la congruent e polinomiale  si observat ii 49
3.1 Exercit ii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3

4 CUPRINS

Capitolul 1
Not iuni introductive
1.1 Mult imea numerelor naturale
Mult imea numerelor naturale este obiectul fundamental de studiu pentru
aritmetic 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.
Modul intuitiv de percepere a numerelor naturale a fost nalizat ante-
rior prin intermediul numerelor cardinal. ^In urm atoarele r^ anduri vom da a
abordarea axiomatic a a mult imii numerelor naturale.
1.1.1 Axiomatica Peano
Denit ia 1.1.1. Numim sistem Peano un triplet ( N;0;), unde:
1.Neste o mult ime nevid a;
2.02N;
3.:N!Neste o aplicat ie numit a de succesiune , care veric a
urm atoarele condit ii(axiome):
(a)02Im(adic a 8n2N;0̸=(n));
(b)este o aplicat ie injectiv a;
(c)Axioma induct iei : Dac aMNsatisface propriet at ile:
i.02M;
ii.n2M)(n)2M, atunciM=N.
Vom nota(n) =n si vom spune c a nestesuccesorul lui n.
5

6 CAPITOLUL 1. NOT IUNI INTRODUCTIVE
Exemplu: 0= 1;1= 2;2= 3;::::
D^ and statut de axiome condit iilor de mai sus, matematicianul Giuseppe
Peano(1852- 1932), a reu sit s a construiasc a cu ajutorul lor ^ ntreaga teorie
a numerelor naturale. Teoria axiomatic a a lui Peano folose ste pentru nu-
mere modelul metodei logice, ^ ntrebuint at cu succes de Euclid ^ n geometrie,
^ nc a din antichitate. Conform denit iei axiomatice dat a de Peano, numerele
naturale sunt elementele unei mult imi N, ^ n care se xeaz a un element 0,
^ mpreun a cu funt ia de succesiune, astfel ^ nc^ at sunt satisf acute axiomele de
mai sus.
1.1.2 Legi de compozit ie ^ n mult imea N
1.Adunarea este o lege de compozit ie φ:NN)N, cuφ(x;y) =x+y
astfel ^ nc^ at:
(a)x+ 0 =x;8x2N;Exemplu: 1+ 0= 1
(b)x+s(y) =s(x+y);8x;y2N.
Observat ia 1.1.2. Deoarecex+ 1 =s(x);itemul b se refor-
muleaz a prin x+ (y+ 1) = (x+y) + 1;8x;y2N.
Exemplu: 2+ 1= 3
2.^Inmult irea este o lege de compozit ie :NN)N, cu (x;y) =x
y=
xyastfel ^ nc^ at:
(a)x
0 = 0;8x2N;Exemplu: 1
0 = 0:
(b)x
s(y) =xy+x;8x;y2N.
Astfel spus, x(y+ 1) =xy+x;8x;y2N. Folosind principiul
induct iei matematice se constat a c a φ si sunt denite peste tot
^ nN.
Propozit ia 1.1.3. (a) i. (N;+)este monoid comutativ cu propri-
etatea de simplicare (x+a=x+b)a=b);
ii.x+y= 0)x=y= 0;
(b) i. (N;
)este monoid comutativ;
ii.1 este element neutru;
iii.dac axy=xz six̸= 0, atunciy=z(proprietatea de simpli-
care).
(c)^Inmult irea este distributiv a fat  a de adunare: x(x+y) =xy+xz,
pentru orice x;y;z 2N.

1.1. MULT IMEA NUMERELOR NATURALE 7
1.1.3 Relat ia de ordine natural a pe mult imea N
Denit ia 1.1.4. Fiea;b2N. Spunem c a ab, dac a exist a x2N, astfel
^ nc^ ata+x=b.
Propozit ia 1.1.5. Relat ia " " este re
exiv a, antisimetric a  si tranzitiv a(deci
este o relat ie de ordine pe mult imea N).
Denit ia 1.1.6. 1.Dac aab sia̸=b, atunci vom nota a < b . De
asemenea, se poate nota ba, ^ n loc deab sib>a ^ n loc dea<b .
2.Dac aab sia+x=b, atunci not am x=ba.
Propozit ia 1.1.7. Pentru orice a;b;c 2N;abeste echivalent cu a+c
b+c, iar dac ac̸= 0;ab,acbc.
Teorema 1.1.8. (N;)este o mult ime bine ordonat a(orice submult ime nevid a
are cel mai mic element).
Corolarul 1.1.9. (N;)este o mult ime total ordonat a (oricare dou a ele-
mente sunt comparabile).
Corolarul 1.1.10. Nu exist a  siruri strict descresc atoare formate cu numere
naturale(astfel spus, un  sir descresc ator de numere naturale este stat ionar).
Observat ia 1.1.11. Prin denit ie ba^ nseamn aab.
Denit ia 1.1.12. Numim segment ^ n mult imea N si not am: 1;ndef=fx2
Nj1xng.^In particular, 1;0 =∅.
Denit ia 1.1.13. Spunem c a mult imea A este nit a  si are n elemente, dac a
exist a o biject ie f:A!1;n.
Notat ie 1. Not am jAjsau Card A clasa de echivalent  a cardinal a a mult imii
A(^ n cazul nostru, num arul de elemente ale lui A).
Observat ia 1.1.14. 1.Dac aBA si A este nit a, atunci B esre nit a
 si avemA=B, jAj=jBj.
2.Dac a A  si B sunt mult imi nite, atunci A[Beste nit a  si avem :
jAj+jBj=jA[Bj+jA\Bj.
Observat ia 1.1.15. 1. (a) O consecint  a a propriet at ii 1. de mai sus
este urm atoarea:
Dac af:A!Beste o funct ie, iar A  si B sunt mult imi nite
cujAj=jBj, atunci f este injectiv a ,f este surjectiv a ,f este
bijectiv a.

8 CAPITOLUL 1. NOT IUNI INTRODUCTIVE
(b)Proprietatea a doua admite urm atoarea generalizare(demonstrat ia
se face prin induct ie dup a n):
FieA1;A2;:::;A nmult imi nite. Atuncin∪
i=1Ajeste nit a  si avem:
jn∪
i=1Aij=n∑
i=1jAij ∑
1i<jnjAi\Ajj+∑
1i<j<k njAi\Aj\Akj+



+ (1)njn∩
i=1Aij(egalitate cunoscut a sub numele de principiul
includerii  si excluderii ).
2.Se ^ nt elege c a mult imea numerelor naturale este innit a(nu este nit a).
Mai general, o mult ime M este 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 M este
innit a dac a  si numai dac a exist a o funct ie i:M!M, i injectiv a, dar
nebijectiv a.
1.1.4 A doua form a a principiului induct iei
Propozit ia 1.1.16. Fie P o submult ime a lui N, av^ and proprietatea:
(x<n )x2P))n2P. AtunciP=N.
Teorema 1.1.17 (Teorema ^ mp art irii cu rest) .Pentru orice dou a numere
naturale a si b , cu b̸= 0;9q;r2N, unic determinate, astfel ^ nc^ at a=
b
q+r;or<b .
1.1.5 Propriet at i ale lui N
Denit ia 1.1.18 (Divizibilitate) .Se dau numerele naturale a  si b, dac a
presupunem c a a divide b dac a exist a num arul natural c astfel ^ nc^ at b=ac.
Faptul c a divide b se va nota cu ajbsaub…a, iar c a a nu divide b se va nota
cua-b.
Exemplu: 2j6, deoarece exist a 3 astfel ^ nc^ at 6 = 2
3:
Observat ia 1.1.19. Vom enumera propriet at ile relat iei divide :
1.este re
exiv a( aja);
2.este tranzitiv a(dac a ajb sibjc, atunciajc);
3.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 element, iar
0 este ultim element.

1.1. MULT IMEA NUMERELOR NATURALE 9
4.Dac aajbi;i= 1;2;:::;n atunci:ajn∑
i=1ci
bi;8ci2N.
Denit ia 1.1.20 (Numere ireductibile) .Fiep2Nnf0;1g. Spunem c a p este
ireductibil dac a dintr-o relat ie de forma p=ab)a= 1 saub= 1.
Observat ia 1.1.21. Dac a not am aN=fakjk2Ng, atunciajb)aN
bN. Pe baza acestor denit ii, putem enunt a acum urm atoarea teorem a.
Corolarul 1.1.22. Oricare ar  num arul natural n > 1, exist a numerele
ireductibile distincte (dac a s2)p1;p2;:::;p s si numerele natural nenule
1;2;:::; sastfel ^ nc^ at: n=p1
1
p2
2:::pss.
^In plus, dac a n=p1
1
p2
2:::pss=n=n=q1
1
q2
2:::qt
t, unde
q1;q2;:::;q isunt numere ireductibile distincte, iar i1, atunci avem s=
t;pi=qi;i=i, pentru orice i, 1is:
Denit ia 1.1.23. Descompunerea unui num ar natural ^ n forma 1.1.22 se
nume ste scrierea ^ n form a canonic a sau descompunerea canonic a.
Denit ia 1.1.24 (Numere prime) .Spunem c a un num ar natural p este prim
dac ap>1  si dinpjab)pjasaupjb.
Exemplu: Numerele 2;3;5;7;11;13;17;19;23;:::sunt numere prime. Sin-
gurul num ar prim par este 2, celelelate numere prime sunt toate impare. Ca  si
curiozitate, cel mai mare num ar prim descoperit p^ an a acum este 2742072811
 si a fost descoperit ^ n ianuarie 2016 de un computer de la o universitate
din Missouri. Acest num ar prim are cu 5 milioane de cifre mai mult dec^ at
precedentul num ar prim.
Teorema 1.1.25 (Euclid) .Mult imea numerelor naturale prime este innit a.
Corolarul 1.1.26. Dac ap2N, atunci p este ireductibil ,p este prim. Un
num ar ^ ntreg p̸= 0;1se nume ste num ar prim dac a p nu se poate scrie ca
produsul a dou a numere ^ ntregi diferite de 1, astfel zis, dac a p nu are dec^ at
divizorii 1;p. Un num ar ^ ntreg diferit de 0, 1 si neprim se nume ste
num ar compus.
Exemplu: 3;5;17 sunt numere prime, ^ n timp ce 24;35;90 sunt com-
puse.
Denit ia 1.1.27 (Cel mai mare divizor comun) .1.Fie a, b 2N. Spunem
c a d este cel mai mare divizor comun(c.m.m.d.c.) pentru numerele a  si
b dac a  si numai dac a sunt ^ ndeplinite condit iile:
(a)dja sidjb;

10 CAPITOLUL 1. NOT IUNI INTRODUCTIVE
(b)ja sijb)jd
Exemplu: [2;8] = 2 (cel mai mare divizor comun al numerelor 2  si 8
este 2).
2.Dac a (a;b) = 1, spunem c a numerele a  si b sunt relativ prime.
3.Spunem c a m este cel mai mic multiplu comun(c.m.m.m.c) pentru nu-
merele a  si b, dac a  si numai dac a sunt ^ ndeplinite condit iile:
(a)ajm sibjm;
(b)ajm′ sibjm′)mjm′.
Exemplu: (6;8) = 24 (cel mai mic multiplu comun al numerelor 6  si 8
este 24).
Observat ia 1.1.28. 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  si b. Not am d= (a;b)  sim= [a;b]. Desigur,
avem (a;1) = 1  si [a;1] =a, iar (a;0) =a si [a;0] = 0, pentru 8n2N.
Corolarul 1.1.29. Fie a  si b, dou a numere natural strict mai mari ca 1,
a=p1
1
p2
2




pss;b=p1
1
p2
2




pss, descompunerile canonice. Atunci
exist ad= (a;b) sim= [a;b] si avem:
d=pmin(11)
1
pmin(22)
2




pmin(ss)
s
m=pmax(11)
1
pmax(22)
2




pmax(ss)
s .
Observat ia 1.1.30. Avem md= ab(pentru c a min(ii) +max(ii) =
ii).
Observat ia 1.1.31. 1.Din corolarul anterior rezult a c a^ n mult imea part ial
ordonat a (N;j) (^ n care consider a mai mare dec^ at b dac aajb), pentru
orice a, b exist a maxa;b = (a;b)  simina;b = [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.2 Mut imea numerelor ^ ntregi Z
1.2.1 Construct ia mult imii Z
Consider am pe mult imea NNurm atoarea relat ie: ( m;n)(p;q) dac a
m+q=n+p, unde (m;n);(p;q)2NN. Aceasta este o relat ie de
echivalent  a:

1.2. MUT IMEA NUMERELOR ^INTREGI Z 11
este re
exiv a, deoarece m+n=n+mceea ce implic a ( m;n)(m;n);
este simetric a, deoarece presupun^ and ( m;n)(p;q) rezult a c a m+q=
n+p, de unde deducem p+n=q+m, deci (p;q)(m;n);
este tranzitiv a, deoarece presupun^ and ( m;n)(p;q)  si (p;q)(r;s)
rezult a c am+q=n+p sip+s=q+r, de unde deducem ( m+s) +
(p+q) = (m+q) + (p+s) = (n+p) + (q+r) = (n+r) + (p+q), deci
m+s=n+r, adic a (m;n)(r;s).
Clasa de echivalent  a a lui ( m;n) o vom nota cu:
(m;n) =f(p;q)2NN=(m;n)(p;q)g
Denit ia 1.2.1. Mult imea factorNN=f(m;n)=(m;n)2NNgse
nume ste mult imea numerelor ^ ntregi  si se noteaz a cu Z. Se nume ste
num ar ^ ntreg orice element ( m;n) al lui Z.
Denit ia 1.2.2 (Divizibilitate) .Fie;2Z. Spunem c a "divide"dac a
exist a
2Zastfel ^ nc^ at
=.Dac adividevom notaj.
Observat ia 1.2.3. 1.1j;82Z;
2.j0;82Z;
3.Relat ia " j" este re
exiv a  si tranzitiv a, dar nu este antisimetric a. Din
j sijse obt ine jj=jj(spunem c a  sisunt asociate ^ n diviz-
ibilitate).
4.Dac aj1| sij2, atuncij(b11+b22);8b1;b22Z
5.Not am cu aZ=fakjk2Zgsubgrupul lui Z, format din multiplii
num arului ^ ntreg a. Not am de asemenea aZ+bZ=fak+b1jk;12Zg
Teorema 1.2.4 (Teorema ^ mp art irii cu rest ^ n Z).Fiea;b2Z;b̸= 0.
Atunci exist a  si sunt unice numerele ^ ntregi q  si r astfel ^ nc^ at:
a=bq+r si0r<jbj.
1.2.2 Unicitatea c^ atului  si a restului
Presupunem c a avem a=bq+r sia=bq′+r′, cu 0 r<jbj si 0<r′<jbj.
Atunci am avea: b(qq′) =r′r, deci
jbj
jqq′j=jrr′j: (1)
Dac ar′< r atunci 0 rr′r <jbj, iar dac arr′, atunci 0 
r′rr′<jbjdeci ^ n ambele situat ii avem jrr′j<jbj.

12 CAPITOLUL 1. NOT IUNI INTRODUCTIVE
Dac a am avem jqq′j ̸= 0, atunci ar ^ nsemna c a jqq′j 1, iar din
relat ia 1 ar rezulta jbj  jbj
jqq′j=jrr′j<jbj, ceea ce este imposibil.
Prin urmare q′=q sir′=r.
Denit ia 1.2.5. Numerele q  si r se numesc c^ atul  si respectiv restul^ mp art irii
num arului a la b.
Denit ia 1.2.6 (Cel mai mare divizor comun) .Fiea;b2Z. Un num ar d
se nume ste cel mai mare divizor comun al numerelor a  si b dac a:
1.dja sidjb;
2.Dinja sijb)jd.
Not am cel mai mare divizor comun al numerelor a  si b cu (a, b). Se
observ a c a d este determinat de 1.  si 2. p^ an a la o asociere ^ n divizibilitate.
Convenim s a lu am ( a;b)0. Determinarea este complet 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 existent a c.m.m.d.c pentru orice
a;b2Z. O determinare ecient aa lui d este asigurat a de Algoritmul lui
Euclid .
Denit ia 1.2.7. Fie2R. 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 a. Rezult a c a:
def=[]2[0;1)  si numim parte fract ionar a a lui .
Dac aa;b2Z;b> 0  sia=b
q+r, cuq;r2Z;0r<b se constat a c a
avemq= [a
b].
Existent a, unicitatea  si un mod de calcul pentru cel mai mare divizor
comun sunt date de urm atorul rezultat ce poart a numele de Algoritmul lui
Euclid .
1.2.3 Algoritmul lui Euclid
Algoritmul lui Euclid reprezint a un mod ecient de determinare a c.m.m.d.c.
a doi ^ ntregi. Fie a;b2Z;b̸= 0. Conform teoremei ^ mp art irii cu rest, exist a
 si sunt unice numerele ^ ntregi q  si r astfel ^ nc^ at a=b
q+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 ^ mp art irii cu rest,
exist a  si sunt unice numerele ^ ntregi q1 sir1astfel ^ nc^ at b=b
r0+r1 si
0<r 1<r 0.
Dac ar1̸= 0, atunci exist a  si sunt unice numerele ^ ntregi q2 sir2astfel
^ nc^ atr=r1
q2+r2 si 0<r 2<r 1.

1.2. MUT IMEA NUMERELOR ^INTREGI Z 13
Dac ark1̸= 0, atunci exist a  si sunt unice numerele ^ ntregi qk sirkastfel
^ nc^ atrk2=rk1
qk+rk si 0rk<r k1.
Obt inem astfel numerele naturale r1> r 2>


> r k> ::: . Cum
mult imea Neste bine ordonat a, exist a un n2Nastfel ^ nc^ at rn+1= 0 (^ n caz
contrar s-ar construi inductiv un  sir strict descresc ator de numere naturale).
Teorema 1.2.8. Num arulrndeterminat de condit iile rn̸= 0  sirn+1= 0
este cel mai mare divizor comun al numerelor a  si b.
Observat ia 1.2.9. Fiea;b2Zn0. Se constat a u sor c a A= (aZ+bZ)\N̸=
∅. Dac a d= minA, atunci d= (a;b).
Observat ia 1.2.10. Fiea;b;c 2Z. Se veric a faptul c a avem (( a;b);c) =
(a;(b;c)), ceea ce permite denirea valoarii 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.d.c. al numerelor  ntregi
a1;a2;:::;a n.
Denit ia 1.2.11. Fiep2Zn f 1;0;1g.
1.Spunem c a p este ireductibil dac a din p= ab rezult a jaj= 1 sau jbj= 1
(spunem, c a p nu admite descompuneri proprii).
2.Spunem c a p este prim dac a din pjabrezult apjasaupjb.
Propozit ia 1.2.12. Dac ap2Z, atunci sunt echivalente armat iile:
1.p este ireductibil;
2.p este prim.
Denit ia 1.2.13 (Num arul divizorilor lui n) .Fied:Zn f 1;0;1g !
N;d(n) = num arul divizorilor pozitivi ai lui n.
Dac an=p1
1:::pk
k, atuncid(n) = (1+ 1):::(k+ 1).
Denit ia 1.2.14 (Suma divizorilor lui n) .Fie funct ia :Zn f 1;0;1g !
N;(n) = suma divizorilor pozitivi ai num arului n.
Dac an=p1
1:::pk
k, atunci:
(n) =pk+1
11
p11:::pk+1
k1
pk1.
Observat ia 1.2.15. Dac a (m;n) = 1, atunci, din cele dou a denit ii de mai
sus, rezult a:

14 CAPITOLUL 1. NOT IUNI INTRODUCTIVE
1.d(m
n) =d(m)
d(n);
2.(m
n) =(m)
(n).
Spunem c a d  si sunt funct ii aritmetice multiplicative.
Denit ia 1.2.16 (Indicatorul lui Euler) .Fie dat un num ar natural nenul n,
nota am cu φ(n) num arul numerelor mai mici dec^ at n  si relativ prime cu n.
Iat a  si dou a rezultate importante referitoare la funct ia φ:
Propozit ia 1.2.17. Fie n un num ar natural nenul. Atunci: n=∑
djnφ(d).
Propozit ia 1.2.18. Fien=p1
1
p2
2:::pk
kun num ar natural nenul conform
corolarului 1.1.22. Atunci are loc formula: φ(n) =n(11
p1)(11
pk).

Capitolul 2
Congruent e
2.1 Denit ii. Propriet at i de baz a
2.1.1 Not iuni generale
Denit ia 2.1.1. Fie m un num ar natural nenul  si a, b dou a numere ^ ntregi.
Spunem c a a este congruent cu b modulo m dac a mjab.^In acest caz, vom
folosi notat ia ab(mod m).
Observat ia 2.1.2. ^In caz contrar: a̸b(modn):
Exemplu: 251(mod 4)
26̸1(mod 4)
Sau cu alte cuvinte, putem spune c a a=Mn+b, undeMnreprezint a
multiplii lui n. Observ am c a ab(mod m) ,a  si b dau acela si rest prin
^ mp artt irea cu n, deci ab(mod m) ,a modn= b mod n.
Congruent ele apar foarte des ^ n viat a de zi cu zi. De exemplu, ceasul
funct ioneaz a modulo 12 sau 24 ore, calendarul modulo 12 luni sau modulo
7 pentru zile, metrul modulo 1000 mm, etc. Congruentt a cu doi este cel
mai simplu tip de congruent  a, unde numerele congruente cu 0 sunt numite
numere pare, iar cele congruente cu 1, impare.
^In cazul congruent elor, ^ n primul r^ and, se studiaz a resturile obt inute prin
^ mp art irea multiplilor unui num ar la un num ar dat, studiu care conduce
imediat la rezolvarea congruent elor de gradul ^ nt^ ai de forma axb(mod m).
Propozit ia 2.1.3. Dac a a, b 2Z, iarm2, este un num ar natural,
atunciab(mod m) dac a  si numai dac a exist a k num ar ^ ntreg pentru care
a=b+km.
Propozit ia 2.1.4. Relat ia de congruent  a este o relat ie de echivalent  a pe
mult imea numerele ^ ntregi Z.
15

16 CAPITOLUL 2. CONGRUENT E
Conform acestui rezultat, mult imea Zeste^ mp art it a^ n clase de echivalent  a
a num arului ^ ntreg a este format a din toate numerele ^ ntregi de forma a+
km;k 2Z.
Consider am dou a numere naturale prime^ ntre ele: a  si b, pentru urm atoarea
teorem a de baz a.
Consider am  sirul multiplilor succesivi ai lui a:
a;2a;3a;:::;ia::: ; (1)
^ l ^ mp art im pe ecare la m  si consider am resturile obt inute:
r1;r2;r3;:::;r i;:::; (2)
unde am notat cu rirestul ^ mp art irii lui ia la m.
Exemplul 2.1.5. m= 10, a= 9
9;18;27;36;45;54;63;72;81;90;99;108;117::: (3)
9;8;7;6;5;4;2;1;0;9;8;7;:::: (4)
Teorema 2.1.6. S irul resturilor este periodic; o perioad a are m termeni
diferit i ^ ntre ei.
Demonstrat ie. Consider am primii m multiplii ai lui a
a, 2a, 3a, . . . , ia, . . . , ma
 si resturile:
r1;r2;r3;:::;r i;:::;r m= 0.
Doi multiplii din acest  sir(nit- cu m termeni) nu pot da acela si rest ^ n
^ mp art irea prin m. ^Intr- adev ar, dac a ia  si ja(1 i < j m) ar da acela si
rest ^ n ^ mp art irea prin m, din ja= mc'+ r, ia= mc+ r ar rezulta ja- ia= mq,
(j- i)a= mq. ^Ins a, m ind prim cu a, prin ipotez a, ar rezulta c a j- i se divide
prin m, ceea ce nu se poate, pentru cu a ji<m .
Consider am acum  sirul 1 al multiplilor lui a nelimitat. Doi multiplii ale
c aror ranguri difer a print-un multiplu de m dau acela si rest ^ n ^ mp art irea
prin m; adic a multiplii ia  si (i+ mh)a dau acela si rest ^ n ^ m art irea prin m,
aceasta demonstr^ and periodicitatea  sirului 2.

Observat ia 2.1.7. Observat ii asupra form arii  sirului de resturi:

2.1. DEFINIT II. PROPRIET AT I DE BAZ A 17
1.Fiea1>m;a 1=mq+a;a<m . Avemia1(modm) c aciia1ia=
m
qi. Rezult a c a  sirul de resturi dat de multiplii lui a1este acela si cu
 sirul de resturi dat de multiplii lui a.
Deexemplu , multiplii lui 19  si multiplii lui 9, dau acela si  sir de resturi
la ^ mp art irea prin 10. Aceast a observat ie este valabil a  si pentru cazul
^ n care a nu este prim cu m. Remarc am c a dac a ( ai;m) = 1, atunci
 si (a;m) = 1  si reciproc (c aci dac a ai si m au un divizor comun, din
relat iaai=mq+arezult a c a acesta divide  si a).
2.Pentru a forma  sirul resturilor, nu este necesar s a facem ^ nmult irile care
dau multiplii succesivi  si nici ^ mp art irile lor prin m.
Exemplu . Fie a= 9  si m= 10.
:::;9
3;9
2;9
1;9
0;9
1;9
2;9
3;::: :::; 3;2;1;0;9;8;7;::: (5)
10 termeni consecutivi din  sirul 1, ai multiplilor ^ ntregi ai lui 7, dau
toate resturile posibile (0 ;1;2;:::; 9). S irul resturilor este periodic.
Consider^ and a=9;m= 10, obt inem acela si  sir de multiplii ^ ntr-o
ordine de m arime invers a:
:::;9
(3);9
(2);9
(1);9
0;9
1;9
2;9
3;::: :::; 7;8;9;0;1;2;3;:::
(6)
3.Congruent a axb(modm) ^ n cazul ( a;m) = 1. A rezolva aceast a
congruent a  a unde a;b;m sunt numere naturale  si ( a;m) = 1, ^ nseamn a
a g asi valorile (naturale) ale lui xpentru care numerele ax sibdau
acela si rest ^ n ^ mp art irea prin m. S a presupunem ^ nt^ ai b < m ; ^ n
acest caz putem enunt a problema astfel: pentru ce valori ale lui x,ax
d a restulb^ n ^ mp art irea prin m. Dac a ne ^ nchipuim c a xia valorile
1;2;3;:::;ax devinea;2a;3a;::: deci c aut am multiplii lui acare dau
restulb^ n ^ mp art irea prin m. Conform teoremei de baz a de la punctul
1), exist a ^ n  sirul primilor mmultiplii unul singur care d a restul b; e
elax0. S irul resturilor ind periodic, numai multiplii a(x0+hm) mai
dau acela si rest. A sadar exist a o solut ie a congruent ei date x0<m, iar
toate solut iile ei (numere naturale) sunt cuprinse^ n formula x=x0+hm
undehia valorile 0 ;1;1;:::;n;:::
Cazulb>m se reduce imediat la cazul b<m . Dac a se d a axb1(mod
m) cub1> m , ^ mp art im ^ nt^ ai pe b1lam; eb1=mq+b, cub < m .
A spune c a ax sib1dau acela si rest, revine la a spune c a axd a restulb,
axb(modm)  si obt inem cazul precedent.

18 CAPITOLUL 2. CONGRUENT E
Conform observat iei 1 de la punctul 2, cazul a > m este reductibil la
cazula<m:
Exemplu. S a se rezolve congruent a 19 37(mod 10) :
Num arul 37 d a restul 7 ^ n ^ mp art irea prin 10. Trebuie s a ga asim multiplii
lui 19 care dau restul 7 ^ n ^ mp art irea prin 10. S irul resturilor dat de multiplii
lui 19 este acela si cu  sirul resturilor date de multiplii lui 9. Deci avem de
rezolvat 9x= 7( mod 10). Printre primii zece multiplii ai lui 9 vom g asi unul
( si numai unul ) care d a restul 7. ^Incerc^ and, g asim x= 3. Solut ia general a
congruent ei date va  deci x= 3 + 10h(h= 0;1;2;3;:::):
Analog, vedem c a congruent a axb(modm) ^ n numere ^ ntregi admite
solut ia general x=x0+hm(h=:::;3;2;1;0;1;2;:::),x0ind o solut ie
particular a. D^ and lui x,mvalori consecutive(de exemplu 1 ;2;:::;m ) una  si
numai una din aceasta veric a congruent a.
Observat ia 2.1.8. Dac an2Z;n< 0, se dene ste ^ n mod analog relat ia de
congruent  a modulo n, care, evident, coincide cu cea modulo jnj:
Mult imea claselor de echivalent  a o vom nota Zn:
DeciZn=f^aja2Zg, iar ^a=fa+n
kjk2Zg:Num arulnse nume ste
modulul relat iei de congruent  a.
Denit ia 2.1.9. FieMZn. Spunem c a o mult ime MZeste un sistem
complet de reprezentant i pentru Mdac a ( 8)2Mexist a un unic a2M
astfel ^ nc^ at ^ a=.^In cazul unui sistem de reprezentant i pentru Znse mai
folose ste denumirea de sistem redus de resturi modulo n .
De exemplu, sistemul de reprezentant i standard pentru Znestef0;1;:::;n
1g:
Dac aneste num ar par, atunci sistemul de reprezentant i este:
{
n
2;n2
2;:::;1;0;1;:::;n2
2}
;
iar dac aneste un num ar impar, atunci un sistem de reprezentant i este:
{
n1
2;:::;1;0;1;:::;n1
2}
:
Aceste sistem de reprezentant i, pentru nnum ar par  si pentru nnum ar
impar, se mai numesc cele mai mici resturi modulo n .
Denit ia 2.1.10. Un sistem complet de resturi modulo m este o mult ime
de numere ^ ntregi astfel ^ nc^ at orice ^ ntreg este congruent modulo m cu un
singur num ar din mult ime.
Spre exemplu:

2.1. DEFINIT II. PROPRIET AT I DE BAZ A 19
1.f0;1;:::;m 1gse nume ste mult imea celor mai mici resturi pozitive
modulo m.
2.Pentru m natural impar, sistemul complet de resturi:{
m1
2;m3
2;:::;1;0;1;:::;m3
2;m1
2}
se num ste mult imea celor
mai mici resturi, ^ n valoare absolut a, modulo m.
Propozit ia 2.1.11. Fie a, b numere ^ ntregi, m num ar natural nenul, astfel
^ nc^ atab(mod m). Atunci, pentru orice ^ ntreg c, au loc relat iile:
1.a+cb+c(mod m),
2.acbc(mod m),
3.acbc(mod m).
Propozit ia 2.1.12. Fie m un num ar natural nenul  si a, b, c numere ^ ntregi
unde (c, m)= d. Dac a acbc(mod m), atunci ab(modm
d).
Demonstrat ie. Dinacbc(mod m), exist a k2Z, astfel ca c(ab) =
km. Cumd= (c;m), obt inem c=dc′;m=dm′cu (c′;m′) = 1. Rezult a
c′(ab) =km′;adic am′jab.
^In practic a, apare mai des un caz particular al acestei propozit ii,  si anume:

Corolarul 2.1.13. Fie m un num ar natural nenul  si a, b, c numere ^ ntregi
unde (c, m)= 1. Dac a acbc(mod m), atunci ab(mod m).
Propozit ia 2.1.14. Dac aab(mod m)  si cd(mod m), atunci:
1.acbd(mod m),
2.acbd(mod m).
Propozit ia 2.1.15. Dac a fr1;r2;:::;r mgeste un sitem complet de resturi
modulo m, iar a2Ncu(a;m) = 1 , atunci,
far1+b;ar 2+b;:::;ar m+bg (7)
este un sistem complet de resturi modulo, pentru orice b2Z.
Demonstrat ie. Cum mult imea este format a din m elemente, este sucient
s a ar at am c a oricare dintre acestea nu sunt congruente modulo m. Dac a
presupunem c a arj+bark+b(mod m), pentru j̸=k, atunciarjark(mod
m). Din propozit ia 2.1.11 rezult a rjrk(mod m), ceea ce este fals. 

20 CAPITOLUL 2. CONGRUENT E
Propozit ia 2.1.16. Dac aab(mod m), atunci akbk(mod m), pentru
orice num ar natural k.
Propozit ia 2.1.17. Dac aab(modm1),ab(modm2), . . . ,ab(mod
mk), atunciab(mod [m1;m2;:::;m k]).
O consecint  a imediat a a acestei propozit ii este dat a de:
Corolarul 2.1.18. Fie numerele nenule m1;m2;:::;m k, dou a c^ ate dou a rel-
ativ prime. Dac a ab(modm1),ab(modm2), . . . ,ab(modmk),
atunciab(modm1
m2




mk).
Ca o prim a aplicat ie a congruent elor, prezent amno metod a rapid a de
calcul pentru bn(mod m), unde b, n, m sunt numere naturale. Ea este nu-
mit a metoda ridic arii repetate la p atrat  si reducerii modulo m, algoritmul
presupun^ and doar ridic ari la p atrat  si ^ nmult iri repetate cu numere naturale
mai mici dec^ at modulul. Aceast a metod a, ind deosebit de ecient a pentru
valori mari ale lui n  si m, este des folosit a ^ n multe protocoale criptograce
care implic a exponent ieri modulare.
Pentru ^ nceput, se scrie ^ n baza 2. Fie n= (akak1:::a 1a0)2. Atunci:
bn=bk∑
j=02jaj= (b20)a0(b21)a1:::(b2k)ak: (8)
T  in^ and cont de aceast a relat ie, calcul am ^ nt^ ai resturile modulo m ale
luib;b2;b4;:::;b2kridic^ and succesiv la p atrat  si reduc^ and modulo m. Dup a
aceea, ^ nmult im resturile modulo m ale lui b2jcuaj= 1  si reducem modulo
m.
2.2 Not iuni ajut atoare
Pentru compunerea acestui capitol vom aminti c^ ateva teoreme din primul
capitol d^ andu-le  si demonstrat iile ce ne vor ajuta ^ n continuare.
Teorema 2.2.1 (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;s1, astfel ^ nc^ at s a avem n=p1;:::;p s.
2.Dac an>1 sin=p1;:::;p s=q1;:::;p t, unde (pi)1is;(qj)1jtsunt
numere ireductibile  si p1p2


ps;q1q2


qtatunci
s=t sipi=qi, precum orice I, 1Is.

2.2. NOT IUNI AJUT ATOARE 21
Demonstrat ie. Pentru demonstrat ia teoremei fundamentale a aritmetice vom
folosi induc ctia matematic a. Fie n= 2 =s(1) = 1 + 1. Num arul 2 este
ireductibil, deci armat iile sunt adev arate pentru acesta. Fie n > 2. Dac a
num arul n este ireductibil, atunci concluzia este adev arat a. Dac a n este
reductibil, o factorizarea a sa va avea forma n=ab;8a;b2N, unde 1<
ab<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 Nn0;1 care nu se descompune n^ n produs de
factori ireductibili. Avem n0=ab;1< ab < n 0, iar a  si b se descompun
^ n produs de factori ireductibili (ind strict mai mici ca n0). Deci  sin0se
descompune ^ n produs de factori ireductibili, ceea ce ^ ns a contravine alegerii
f acute. S a presupunem acum c a armatia 2. din enunt  este fals a. Fie
n02Nnf0;1g, cel 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=p1
p2
:::
ps;s2;p1p2:::ps;p1=po descompunere a lui
n0^ n care apare p si en0=q1
q2
:::
qt;q1q2:::qt, o descompunere
a luin0^ n factori ireductibili, difer a de prima(desigur n0este reductibil).
Dac ap1=q1, atunci se obt in dou a descompuneri pentru un num ar mai
mic dec^ atn0(1<p 2
:::
ps=q2
:::
qt)  si se contrazice minimalitatea lui n0.
^In cazulp=p1<q 1consider am num arul
n1=n0p1q2:::qt=p1p2:::psp1q2:::qt:
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 n0
rezult a c an1se 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 cumq1este
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.

Teorema 2.2.2 (Euclid) .. Mult imea numerelor naturale prime este innit a.
1.Prima demonstrat ie (Euclid). Presupunem prin absurd c a num arul nu-
merelor prime esre nit: e acestea p1;p2;:::;p n, consider am num arul

22 CAPITOLUL 2. CONGRUENT E
N=p1p2:::p n+ 1; el admite un divizor prim q. Deoarece q coincide
cu unul din numerele pi, dinpijN)pij1. Am obt inut o contradict ie.
2.A doua demonstrat ie. Este sucient s a ar at am c a pentru orice num ar
natural n exist a un num ar prim p, p > n . Pentru aceasta alegem un
divizor prim al num arului N=n! + 1 .
3.A treia demonstrat ie. Pentru orice num ar natural n, exist a un num ar
prim p, care satisface condit iile: n < p < n !. Pentru acesta se ia un
divizor prim al lui N=N!1.
4.A patra demonstrat ie(Euler). Presupunem prin absurd c a exist a numai
un num ar nit de numere prime p1;p2;:::;p k. Pentru orice i, 1i
k, avem seria geometric a nit a:
1∑
n=01
pn
j=pi
pi1. F ac^ and produsul acestor serii se obt ine:
k∏
i=1(
1 +1
pi+1
p2
i+


+1
pn
i+:::)
=∑
n1;n2;:::;n k1
pn1
1pn2
2:::pnk
k,
rezult a c a:
1∑
n=11
n=k∏
i=1pi
pi1,
adic a seria armonic a este convergent a. S-a obt inut o contradict ie.
5.A cincea demonstrat ie (G. Polya). Pentru orice num ar natural n se
formeaz a num arul lui Fermat fn= 22n+ 1. Numerele lui Fermat:
f0= 3;f1= 5;f2= 17;f3= 257;f4= 65537 sunt numere prime.
Vom demonstra acum armat ia: dac a m̸=n, atuncifm sifnnu au
niciun divizor prin ^ n comun.
^Intr- adev ar, dac a presupunem c a m=n+kare loc identitatea:
fn+k2
fn=22n+k1
22n+1=(22n)2k1
22n+1= (22n)2k1(22n)2k2+


1.^In
consecint  a, dac a pjfn sipjfn+k)pj2. Aceasta nu se poate deoarece
numerelefnsunt impare. Pentru a ^ ncheia demonstrat ia este sucient
s a observ am c a mult imea numerelor prime cont ine mult imea divizorilor
primi ai numerelor Fermat  si aceasta este innit a ca reuniune innit a
de mult imi(nite) disjuncte.
Demonstrat ia lui Euclid pentru teorema fundamental a a aritmeticii
Vom nota cu P=f2;3;5;7;11;:::gmult imea numerelor naturale prime.

2.3. NUMERE ASOCIATE 23
Teorema 2.2.3. Dac an2Zn f 1;0;1g, atunci exist a  si sunt unic deter-
minate de n numerele s1,p1;:::;p s2N si1;:::; s2Nastfel ^ nc^ at
np1
1:::pss.
Demonstrat ie. Existent a . Este sucient s a consider am n2N si s a aplic am
corolarul 1.1.22.
Unicitatea . Se demonstreaz a prin induct ie: putem presupune n2  si
n reductibil.
Fien=p1
1:::pss=q1
1:::qt
t;s;t1;q1
1:::qt
t2P;1;:::; t2N.
Dinp1jq1
1:::qt
t, deducem c a exist a un indice j2 f1;:::;t gastfel ^ n c^ at
p1jqj, de undep1=qj. Putem alege j= 1, astfel ^ nc^ at p1=q1. Fien1=n
p1.
Avemn1=p11
1:::pss=q11
1:::qt
t.
Cumn1< n  sin1>1 (deoarece n nu este prim), conform ipotezei de
induct ie avem:
11 =11;s=t;1=1, pentrui2. Teorema este demonstrat a. 
2.3 Numere asociate
Consider am un num ar prim p>3  si numerele mai mici dec^ at el: 1 ;2;3;:::;p
1. Dou a numere a  si a' din acest  sir se numesc asociate dac a aa′1(mod
p).
Exemplu . Dac a p= 10, numerele 3  si 7 sunt asociate, c aci 3
7 =M10+1.
a)Fiecare num ar a din  sirul considerat are un asociat  si unul singur. ^Intr-
adev ar , primii p- 1 multiplii ai lui a, dar prin ^ mp art ire la p toate
resturile 1;2;3;:::;p 1. Deci exist a printre ei un multiplu al lui a(unul
singur) care d a restul 1; e a'a acest multiplu, avem a′a1(mod p).
Exemplu . Dac a p= 9, pentru a g asi asociatul lui 7 form am  sirurile:
Multiplii: 7
1;7
2;7
3;7
4;7
5;7
6
Adic a: 7, 14, 21, 28, 35, 42
Resturi: 7, 5, 3, 1, 8, 6
Deci asociatul lui 7 este 4 deoarece 7
41(mod p).
b)Numerele 1  si p- 1 sunt propriile lor asociate, c aci: 1
1(modp);(p
1)
(p1)1(mod p), deoarece p22p+ 1 =Mp+ 1.
c)Dac a 1<a<p 1, asociatul s au, a', este diferit de a.
Fiea′a1(mod p). Dac a a' ar  egal cu a, am avea a21(mod p),
adic aa2=Mp+ 1;(a1)(a+ 1) =Mp, ceea ce nu se poate ^ ntruc^ at,
conform condit iei 1 <a<p 1, numerele a- 1  si a+ 1 sunt pozitive  si
inferioare lui p, deci niciunul nu are factorul p.

24 CAPITOLUL 2. CONGRUENT E
d)Rezult a c a numerele de la 2 p^ an a la p- 2 inclusiv, se grupeaz a ^ n perechi
de numere asociate, distincte ^ ntre ele, astfel ^ nc^ at ecare num ar intr a
^ ntr-o pereche  si numai ^ n una.
Exemplu . Dac a p= 11, numerele:
2;3;4;5;6;7;8;9;
=0 +0 =+
se grupeaz a ^ n 4 perechi: 2
6;3
4;5
9;7
8 ( ecare din aceste produse
ind congruent cu 1 modulo 11).
^In general, de la 2 la p2 suntp3 numere, care se grupeaz a ^ np3
2
perechi de numere asociate (p ind impar, p3 este par, iarp3
2este ^ ntreg).
2.4 Numere Mersenne
La ^ nceput, numerele de forma 2n1 erau considerate prime, pentru n num ar
prim. ^Incep^ and cu anul 1536, diver si matematicieni au ar atata c a aceast a
armat ie nu este corect a, d^ and contraexemple.
Denit ia 2.4.1. Fien2N. Un num ar de forma Mn= 2n1 se nume ste
num ar Mersenne. Dac a p este un num ar prim  si Mpeste prim, el poart a
numele de num ar prim Mersenne.
Mersenne, ^ n lucrarea sa Cogitata Physica- Mathematica , din anul 1644 a
armat, f ar a demonstrat ie, c a: Mpeste prim, pentru p2 f2;3;5;7;13;17;19;31;67;127;257g,
iar pentru celelalte valori n<257, numerele Mperau compuse.
Pentru a vedea dac a un num ar Mersenne este prim, de obicei veric am
dac a are divizori primi mici. Teorema lui Euler  si teorema lui Fermat se
folosesc ^ n aceast a privint  a.
2.5 Congruent e liniare
Denit ia 2.5.1. O congruent  a de forma:
axb(mod m ) (9)
undex2Zeste necunoscuta, poart a numele de congruet  a liniar a ^ ntr-o
variabil a.

2.5. CONGRUENT E LINIARE 25
Teorema 2.5.2 (Teorema chinez a a resturilor) .Fien2;a1;a2;:::;a n2
Zastfel ^ nc^ at pentru i̸=js a avem (ai;aj) = 1  si er1;r2;:::;r n2Z.
Atunci exist a r2Zastfel ^ nc^ at rr1(mod a 1);i= 1;:::;n ,^In plus, pentru
orice alt x astfel ^ nc^ at: xri(mod a i);i= 1;:::;n avemxr(mod a ),
undea=a1




an.
Demonstrat ie. Fiea′
1=∏
j̸=iaj. Din teorema fundamental a a matematicii,
rezult a c a avem ( a′
i;ai) = 1, iar de aici rezult a c a exist a bi;ci2Z;i1;n,
astfel ^ nc^ at bi
a′
i+ci
ai= 1;i=1;n. Denim: r=n∑
j=1rjbja′
j. Deoarece
avembia′
i1(mod a i)  sibja′
j0(mod a j) pentrui̸=j. Prin urmare,
pentru:r=n∑
j=1rjbja′
jvom avemrri(mod a i);i= 1;:::;n: ^In plus, dac a
xri(mod a i);i= 1;:::;n , atuncixr0(mod a i);i= 1;:::;n , deci x-
r se divide cu a=a1
a2




an, deoarece factorii produsului sunt relativ
primi doi c^ ate doi. 
Observat ia 2.5.3. Dac a 1< n =p1
1
:::pss;pi2 P distincte, atunci
conform teoremei chineze a resturilor, relat ia de congruent  a modulo n este
echivalent a cu ansamblul relat iilor de congruent  a modulo pi
i;i= 1;:::;s:
Pentru enunt area teoremei lui Euler vom analiza mai^ nt^ ai un caz numeric:
e m= 14. Numerele prime cu 14  si inferioare lui sunt: 1, 3, 5, 9, 11, 13(^ n
num ar de 6). Consider am unul din ele, de exemplu 5,  si aplic^ and urm atoarea
teorem a: S irul resturilor este periodic; o perioad a are m termeni diferit i ^ ntre
ei. Obt inem:
5
1;4
2;5
3;5
4;5
5;5
6;5
7;5
8;5
9;5
10;5
11;5
12;5
13,
5, 10,15, 20,25, 30, 35, 40, 45, 50,55, 60,65,
5, 10,1, 6,11, 2, 7, 12, 3, 8,13, 4,9.
Ne x am atent ia asupra multiplilor 5i, ^ n care i este prim cu 14. Observ am
c a resturile corespunz atoare sunt tot numere prime cu 14.
Aceasta are loc ^ n general. Dac a ia= mc+r  si dac a i  si a sunt prime cu
m, atunci  si r este prim cu m(pentru c a, dac a m  si r s-ar divide cu d  si ia
s-ar divide cu d; deci ia  si m nu ar  prime ^ ntre ele); reciproc, dac a r este
prim cu m  si ia este prim cu m.
Dac a alegem acum numai multiplii evident iat i vom avea: 5
1 =M14 + 5
5
3 =M14 + 1
5
5 =M14 + 11
5
9 =M14 + 3
5
11 =M14 + 13
5
13 =M14 + 9

26 CAPITOLUL 2. CONGRUENT E
^Inmult ind aceste relat ii membru cu membru obt inem:
56(1
3
5
9
11
13) =M14 + ().
^In paranteza din membrul al doilea sunt acelea si numere, cele prime cu
14, dar ^ ntr- o alt a ordine.
Deci: (1
3
5
9
11
13)(561) =M14.
Dar ^ n parantez a ind numai factori primi cu 14, rezult a c a (561) =
M14.
Este u sor de v azut c a ^ n cazul general se poate rat iona la fel. Exponentul
6 al num arului 5 a ap arut din cauz a c a exist a 6 numere prime cu 14, inferioare
lui(deci s-au scris 6 relat ii).
^In cazul unui num ar oarecare m, not am cu φ(m) num arul numerelor
inferioare lui m  si prime cu el ( φ(14) = 6).
Teorema 2.5.4 (Teorema lui Euler) .Fien2 sia2Z;(a;n) = 1 . Atunci:
aφ(n)1(mod n).
Demonstrat ie. Consider am mult imea M=fa1;a2;:::;a φ(n)g, un sistem com-
plet de reprezentant i pentru U(Zn)def=f^a2Znj(a;n) = 1g. Avema
ai̸
a
aj(modn),8a2Mpentru c aaiaj̸0(mod n)  si ( a;n) = 1. Rezult a
c a:
(a
a1)


(a
aφ(n))a1


aφ(n)(modn)
sau
aφ(n)
a1


aφ(n)a1


aφ(n)(modn):
Prin urmare
(aφ(n)1)
(a1


aφ(n))0(modn):
Deoarece (a1


aφ(n);n) = 1, rezult a
(aφ(n)1)0(modn):

Teorema 2.5.5 (Mica teorem a a lui Fermat) .Fiep2, num ar prim  si
a2Z;(a;p) = 1 . Atunciap11(mod p). Astfel spus apa(mod p),
pentru orice a2Z
Demonstrat ie. Consider am numerele ^ ntregi a;2a;:::; (p1)a. Observ am c a
p-kapentru 1 kp1. De asemenea, ja̸=ka(mod p), pentru j̸=k.
Deci, fa;2a;:::; (pa)agreprezint a un sistem complet de resturi modulo p
din care a fost exclus 0. Astfel,
2a




(p1)a1
2




(p1)( mod p). De
aici,ap1(p1)!(p1)!1( mod p). Cum (( p1)!;p) = 1)ap11( mod
p). 

2.5. CONGRUENT E LINIARE 27
Exemplu .p= 5;a= 2)241 = 15 = 5
3
O prim a aplicat ie a micii teoreme a lui Fermat const a ^ n determinarea
unor resturi modulo p pentru puteri. De exemplu, dac a dorim s a calcul am
restul lui 8110 modulo 13, folosind teorema, obt inem c a 8110 = (812)9
82
6412(mod13).
Observat ia 2.5.6. (Zn;+) este inel comutativ  si unitar cu operat iile: ^ a+^b=
^a+b;^a
^b=^a
b, induse de cele de pe Z, iar dac aU(Zn) =f^aj(a;n) = 1g,
atunciU(Zn) este grup fat  a de ^ nmult ire  si jU(Znj=φ(n).
PentruU(Znse mai folose ste  si notat ia Zx
n.
Vom da ^ n continuare  si structura grupului U(Zncare va  de folos ^ n
capitolul urm ator la calculul r ad a cinilor primitive.
Teorema 2.5.7 (Structura lui U(Zn).Fien= 2e
pa1
1
pa2
2




pak
k, unde
pisunt numere prime distincte, ai>0 sie0. Fierir a d a cini primitive
modulopai
ipentruik. Atunci are loc urm atorul izomorsm:
U(Zn)=⟨^1;^5⟩2e ⟨^r1⟩pa1
1 ⟨^r2⟩pa2
2


 ⟨ ^rk⟩pak
k
.
Se observ a c a ^ n cazul e2 f0;1ggrupul ⟨^1;^5⟩2eeste trivial, iar ^ n cazul
e= 2el coincide cu ⟨^1;⟩22.
Denit ia 2.5.8. Dac aa2Z;(a;n) = 1, denim ord a(mod n), astfel spus
ordinul lui a modulo n , ca indminfk2Njak1(modng.
Observat ia 2.5.9. 1.Este simplu de ar atat, folosind teorema de^ mp art ire
cu rest, c a ord ^ adivide orice k pentru care ak1(modn).^In partic-
ular, ord ^adivideφ(n). O consecint  a interesant a a acestui fapt este c a
pentrua2;n1 avemφ(an1)0(modn), undeφeste funct ia
lui Euler. Dac a n= p este prim  si a1̸0(modp))c a cel put in
unul dintre factorii primi q ai lui ap1+ap2+


+a+1 este congruent
cu 1(mod p).
2.Dac an1;n2sunt dou a numere ^ ntregi prime ^ ntre ele, atunci, conform
teoremei chineze a resturilor, oricare ar  dou a numere ^ ntregi r1;r2,
exist a un num ar ^ ntreg r astfel ^ nc^ at rr1(modn1)  sirr2(mod
n2)  si oricare ar  un alt x astfel ^ nc^ at xr1(modn1)  sixr2(mod
n2), avemxr(modn1
n2).

28 CAPITOLUL 2. CONGRUENT E
2.6 Congruent e polinomiale
Exercit iul 2.6.1. Fiind da un polinom f2Z[X1;:::;X m];m1  sin2,
s a se determine solut iile ^ n numere ^ ntregi ale ecuat iei
f(X1;:::;X m) = 0 (10)
 si s a se determine solut iile congruent ei
f(X1;:::;X m)0(modn): (11)
Este clar c a din orice solut ie a ecuat iei (10) se obt ine o solut ie a congruent ei
(11). O ^ ntrebare reasc a este dac a,  si ^ n ce mod, se poate parcurge drumul
invers. Aceasta ar ^ nsemna c a printr-o alegere adecvat a a unor module n,
^ n urma rezolv arii congruent elor f(X1;:::;X m)0(modn), s a c ap at am o
indicat ie despre modulul de obt inere a solut iilor pentru (10)  si eventual chiar
s a le obt inem.
Acest punct de vedere, init iat ^ n epoca modern a de P. Fermat, a fost
dezvoltat cu rezultate deosebite de Fermat ^ nsu si, Euler, Lagrange, Legendre,
Gauss  si alt i matematicieni de seam a. Ideea intuitiv a c a solut iile congruent elo
de tip (11) aproximeaz a ^ ntr-un anumit fel solut iile ecut iei (10)  si-a g asit
reprezentarea adecvat a prin aparit ia corpurilor de numere p-adice.
Denit ia 2.6.2. FieMun sistem de reprezentant i pentru Zn. Not am ∆ f=
f(x1;:::;x m)2Mnjf(x1;:::;x m)0(modn)g si numim j∆fjnum arul de
solut ii ale congruent ei (11). (Este clar c a ∆ fnu depinde de M).^In continuare
lu amMsistemul de reprezentant i canonic  si numim ∆ fsolut ia congruent ei
(11).
Propozit ia 2.6.3. 1.Dac a (a;n) = 1 , atunci congruent a a
xb(mod
n)are o solut ie unic a modn, anumex=b
aφ(n)1:
2.Dac a (a;n) =d, atunci congruent a a
xb(modn)are solut ie dac a
 si numai dac a djb. Dac a ecuat ia a
xb(modn)are solut ii, atunci
aredsolut ii.
Demonstrat ie. 1.Conform teoremei lui Euler, din ( a;n) = 1 deducem
aφ(n)1(modn), de unde a
(aφ(n)1
b)b(modn), prin urmare
x=b
aφ(n)1este o solut ie . Dac a yeste alt a solut ie atunci a
ya
x
bb0(modn)  si cum (a;n) = 1, rezult a yx0(modn):
2.Dac a congruent a a
xb(modn), are solut ia u, atunci
bau(modn);decibau0(modd):

2.6. CONGRUENT E POLINOMIALE 29
Pe de alt a parte, dac a djb, ea=da1;n=dn1;b=db1. Atunci
avema
xb(modn) dac a  si numai dac a a1xb1(modn1). Cum
(a1;b1) = 1, congruent a a1xb1(modn1) are solut ie unic a (modulo
n1).
Fiex02 f0;:::;n 11gastfel caa1x0b1(modn1). Atunciax0
b(modn):
Deci solut iile congruent ei a
xb(modn) sunt ^ ntregi, de forma u=
x0+k
n1. C^ andkparcurge f0;1;:::;d 1g;uiadvalori, oricare
dou a necongruent e modulo n. A sadar, o mult ime complet a de solut ii
a congruent ei a
xb(modn) este fx0;x0+n1;:::;x 0+ (d1)n1g:
Observat ie. Este clar c a rezolvarea congruent ei
a
xb(modn) (12)
este str^ ans legat a de rezolvarea ^ n numere ^ ntregi a ecuat iei
ax+ny=b: (13)
^In acest caz, ecuat ia (13) are solut ii ^ n Zdac a  si numai dac a congruent a
(12) are solut ii. Fie ( x0;y0) o solut ie particular a pentru (13). Atunci mult imea
cuplurilorx0+k
n1;y0k
a1, c^ andk2Z, constituie solut ia general a a
ecuat iei. O solut ie particular a se poate obt ine (dac a djn), aplic^ and algoritmul
lui Euclid numerelor a sin.
Dac a (x;y) este o alt a solut ie a ecuat iei (13), avem
a(xx0) =n(yy0);
]c si cum (a1;n1) = 1, rezult a c a exist a k;l2Zastfel ^ nc^ at xx0=ln1;y
y0=ka1. Considerat iile precedente arat a c a, ^ n cazul c^ and f(x1;:::;x m) este
de gradul unu, exist a un nastfel^ nc^ at rezolubilitatea congruent ei f(x1;:::;x m)
0(modn) o atrage pe aceea a ecuat iei (13). Un fapt similar are loc pentru
sistemele de ecuat ii liniare cu coecient i ^ ntregi. Aceasta se deduce utiliz^ and
metoda Gauss de rezolvare a sistemelor liniare. 
Denit ia 2.6.4. Numim (13) ecuat ia diofanic a asociat a polinomului f(X1;:::;X m).
Evident, dac a ecuat ia (13) are solut ii , atunci, pentru orice n, congruent a
f(x1;:::;x m)0(modn) are solut ii. Reciproca acestei armat ii nu este
^ n general adev arat a. De asemenea trebuie discutate  si condit iile ^ n care
rezolubilitatea congruent elor f(x1;:::;x m)0(modn)(8)n, precum  si a
ecuat ieif(x1;:::;x m) = 0 ^ n Ratrag rezolubilitatea ecuat iei (13) ^ n numere
rat ionale sau chiar ^ n numere ^ ntregi. Cazul particular al ecuat iei ax2+by2+
cz2= 0, precum  si a altor ecuat ii de gradul doi voi  detaliate ^ n lucrarea de
fat  a.

30 CAPITOLUL 2. CONGRUENT E
Teorema 2.6.5. (Lagrange) Fief=a0Xn+


+a1X+a02Z[X];n1.
Dac apeste prim  si an̸= 0(modp)atunci congruent a f(X)0(modp)
are cel mult nsolut ii.
Demonstrat ie. Se face prin induct ie dup a n. Pentrun= 1 unica solut ie este
0.
Fien2  six02Zo solut ie a conguent ei f(X)0(modp). Putem
scrief(x) = (xx0)
g(x) +f(x0) undef(x0)0(modp):
Atunci congruent a f(X)0( modp) este echivalent a cu ( xx0)
g(x)
0(modp):
Cumpeste prim, din ( xx0)
g(x)0(modp) deducem (pentru orice
x02Z):
(xx0)0(modp) saug(x)0(modp):
Dar gradul lui g(x) indn1 conform ipotezei induct iei, congurent a g(x)
0(modp) are cel mult n1 solut ii. Deci congruent a f(X)0(modp) are
cel multnsolut ii.
Fie acumf(X) =Xp11 = (X1)
:::
(Xp1)2Z[X]:
Folosind Mica teorem a a lui Fermat se obt ine ( f(x)0(modp) pentru
oricexdinf1;2;:::;p 1g:
Deoarece avem  si grad (f)p2, din Teorema lui Lagrange rezult a c a
f(x) are coecient i divizibili cu p. Calcul^ and termenul liber al polinomului
fse obt ine: 
Teorema 2.6.6 (Teorema lui Wilson) .Dac ap > 1este un num ar prim,
atunci (p1)! 1(mod p).
Exemplu
a)Consider am ^ nt^ ai cazul particular p= 11  si toate produsele de numere
asociate distincte.
3
4 =M11 + 1
2
6 =M11 + 1
7
8 =M11 + 1
5
9 =M11 + 1
^Inmult ind aceste relat ii membru cu membru, ^ n membrul ^ nt^ ai obt inem
produsul tuturor numerelor de la 2 p^ an a la 9(11 2), iar ^ n membrul
al doilea,
M11 + 1(c aci( M11 + 1)(M11 + 1) = M11 + 1;etc):

2.6. CONGRUENT E POLINOMIALE 31
A sadar,
2
3
4
5
6
7
8
9 =M11 + 1:
^Inmult ind ambii membrii cu cu 10,
10! =M11 + 10; 12! = M11 + 11 1 =M111
sau
10! + 1 = M11; 10! + 1 = 3628801 0(mod11):
b)S a rat ion am la fel ^ n cazul general. Numerele de la 2 p^ an a la p2 se
grupeaz a ^ n perechi de forma aa′=Mp+ 1. ^Inmult ind toate relat iile
de acest fel, obt inem:
2
3




(p2) =Mp+ 1:
^Inmult ind ambii membrii cu p1, avem:
(p1)! =Mp+p1 =Mp1;
deci,
(p1)! + 1 = Mp; (p1)! + 1 0(modp):
^In toat a expunerea s-a presupus p >3. Dac a p= 2 sau p= 3, relat ia
g asit a se veric a direct: p= 2;(p1)! + 1 = 2; p= 3;(p1)! + 1 = 3.
Reamintind teorema lui Wilson, dac a p este prim, atunci ( p1)! + 1 este
divizibil prim p.
Exemplu . 5 este prim. Vom avea: 4! + 1 = M5.^Intr-adev ar, 4! + 1 =
25 = 5
5.
Observat ia 2.6.7. Dac ap4 nu este prim  si qeste un divizor propriu a
luip, avem
(p1)!0(modp)  si (p1)! + 1 = 1(modq); (14)
ceea ce exclude
(p1)! + 1 0(modp):
Prin urmare reciproca teoremei lui Wilson este adev arat a.
Ne vom ocupa acum de rezolvarea conguent elor binome de forma xk
a(modn) undea sinsunt relativ prime. Reamintim mai ^ nt^ ai urm atoarele:
Propozit ia 2.6.8. Fien2un num ar natural  si aun num ar ^ ntreg, astfel
^ nc^ at (a;n) =d. Atunci conguent a axb(modn)are solut ii dac a  si numai
dac adjb, iar num arul solut iilor ^ n acest caz este exact d.

32 CAPITOLUL 2. CONGRUENT E
Revenind la conguent a xka(modn), vom analiza mai ^ nt^ ai cazul ^ n
carenadmite r ad acini primitive. Are loc urm atorul rezultat:
Teorema 2.6.9. Fien2un num ar natural ce admite r ad acini primitive.
Atunci congruent a xka(modn)admite solut ii dac a  si numai dac a
φ(n)=d1(modn);
unded= (k;φ(n)).^In acest caz, congruent a are exact dsolut ii.
Demonstrat ie. Fiero r ad acin a primitiv a modulo n. Atunci exist a sast-
fel ^ nc^ atars(modn). Vom pune x=rz si vom lucra cu z^ n loc de
x, iarrzkrs(modn) dac a  si numai dac a zks(modφ(n)). Conform
propozit iei 2.6.8, aceast a ultim a congruent  a are solut ie dac a  si numai dac a d
divides. Vom ar ata c a acest lucru este echivalent cu
φ(n)=d1(modn):
Not ame= (φ(n);s) iarord n(a) =ord n(rs) =φ(n)=d. Dar
φ(n)=d1(modn)
dac a  si nu mai dac a ord n(a) =φ(n)=edivideφ(n)=dcare mai departe este
echivalent cu ddividee. Cumddivideφ(n), faptul c a ddivideeeste echiva-
lent cu faptul c a ddivides. Astfel, s-a demonstrat echivalent a ^ ntre djs si
φ(n)=d1(modn) 
Tot conform propozit iei enunt ate mai sus 2.6.8, dac a congruent a are
solut ii, atunci ea are exact de solut ii, demonstrat ia ind astfel ^ ncheiat a.
Pentru cazul ^ n care n= 2e, pentrue3 putem enunt a urm atoarea
teorem a:
Teorema 2.6.10. Fiee3un num ar natural  si a un num ar ^ ntreg par.
Dac a k este impar, atunci congruent a xka(mod 2e)are solut ie unic a.
Dac a k este par, atunci congruent a xka(mod 2e)are soluc tie dac a  si
numaia1(mod 4)  si
a2e2=d1(mod 2e);
unded= (2e2;n).^In acest caz, num arul solut iilor este 2d.
O problem a propus a de N. Abel^ n 1828, prive ste existent a  si determinarea
cuplurilor ( a;p) cupprim  si 2 ap1, pentru care
ap1(modp2):

2.6. CONGRUENT E POLINOMIALE 33
Pentrup37 solut iile sunt:
p= 11;a= 3 sau 9;
p= 29;a= 14  si
p= 37;a= 18;
dup a cum a demonstrat Jacobi .
Interesul pentru aceast a problem a a crescut mult odat a cu stabilirea
urm atorului rezultat privind marea teorem a a lui Fermat:
Fiep3 un num ar prim. Dac a exist a ^ ntregii x;y;z astfel ^ nc^ at
xp+yp+zp= 0  si (p;xyz ) = 1;atunci
2p11(modp2)  si 3p11(modp2).
Este vorba despre criteriul lui A. Wieferich, demonstrat ^ n 1909 precum
 si de teorema lui Mirimanoff.
Mai recent s-a demonstrat c a avem chiar np11(modp2) pentru 2 
n47.
E. Lehmer a ar atat c a aceasta nu poate avea loc dac a p253474889:
Ar at am ^ n continuare c a pentru p= 1093 avem 2p11(modp2).
Not^ andp= 1093, avem
37= 2187 = 2 p+ 1;de unde 314= 4p+ 1(modp2);
De asemenea
214= 16384 = 15 p11(modp2);de unde 228 330p+ 121(mod p2)
32
228 2970p+ 1089  2969p4310p4(modp2):
Se obt ine:
32
228
72170p28 16p28(modp2)
de unde:
32
226
7 4p7(modp2):
Folosind formula binomului, obt inem ^ n continuare
314
2128
77(4p7)7 7
4p
7677(modp2);
de unde:
314
2128 4p1(modp2):
Dar
314= 4p+ 1;de unde

34 CAPITOLUL 2. CONGRUENT E
2128 1(modp2)  si 210921(modp2) deoarece 1092 = 182
6:
Se poate ar ata c a pentru p<1093 avem 2p1̸1(modp2):
Mai mult, singurele numere prime, p<3
109pentru care 2p11(mod
p2) sunt 1093  si 3511.
Este interesant a urm atoarea condit ie echivalent a cu 2p11(modp2):
Consider am
1 +1
2+1
3+


+1
p1
2=m
n;cum;n2N:
Atunci,
2p11(modp2),pjm:
2.7 Congruent e polinomiale^ n mai multe vari-
abile
Prin notat ie de tipul∑
x( mod p)f(x)
^ nt elegem cu a xparcurge un sistem dat de reprezentant i pentru Zp:
Vom ^ ncepe prin a examina congruent ele modulo num ar prim. Dup a cum
se  stie, clasele de resturi modulo pformeaz a un corp nit cu pelemente (care
va  notat Zp)  si orice congruent  a modulo ppoate  privit a ca o egalitate
^ n acest corp. Rezolvarea congruent elor modulo peste deci echivalent a cu
rezolvarea ecuat iilor ^ n corpul Zp. Corpul Zpreprezint a doar un exemplu
de corp nit. Toate rat ionamentele din acest paragraf se transpun ^ ntocmai
pentru cazul unui corp nit oarecare. ^In studiul problemei num arului de
solut ii ale unei congruent e modulo num ar prim, un rol important ^ l joac a
urm atorul fapt simplu:
Lema 2.7.1. Fiepun num ar prim  si n2N. Atunci avem
∑
^x2Zpxnnot∑
x( mod p)xn{
1(modp),dac ap1jn;
0(modp) ,^ n caz contrar:
Demonstrat ie. Dac ap1jn, atunci, not^ and cu n=k(p1) avem, pentru
oricexcu (x;p) = 1(conform teoremei lui Fermat)
nn=xk(p1)= (xp1)k1(modp);

2.7. CONGRUENT E POLINOMIALE ^IN MAI MULTE VARIABILE 35
deci ^ n sum a, unul din termeni este 0(modp), iar ceilalt i sunt 1(mod
p):
Prin urmare:
∑
x2Zpxn∑
x2Zp1p1(modp) 1(modp):
Dac ap1̸ jn, en=k(p1) +r;o<r<p 1:
Pentru (x;p) = 1 avem xn=xk(p1)xrxr(modp).Rezult a c a
S=∑
x( mod p)xn∑
x( mod p)xr(modp):
Dar, pentru 0 < r < p 1, exist aa2Zastfel ^ nc^ at ar1(modp)
deoarece conform teoremei lui Lagrange congruent a xr10(modp) are
cel multrsolut ii. ^Ins a c^ and ^rparcurge Zp si ^a
^xparcurge de asemenea Zp.
Deci:
S=∑
x( mod p)xn∑
x( mod p)(ax)r(modp)(arS)(modp)
de undeS(ar1)0(modp), adic aS0(modp): 
Propozit ia 2.7.2. Fief(X1;:::;X n)2Z[X1;:::;X n]de gradf=d, cu
d<n (p1). Atunci are loc relat ia:
∑
^x1;:::;^xn2Zpf(x1;:::;x n)0(modp):
Demonstrat ie. Este sucient s a demonstr am propozit ia pentru cazul c^ and f
este un monom de gradul n<n (p1):
Fief=x1
1
:::
xnn, unde1+


+nd. Atunci
S=∑
^x1;:::;^xn2Zpf(x1;:::;x n) =∑
^x1;:::;^xn2Zpf(x1
1
:::
xn
n) =(∑
^x12Zpx1
1)

:::
(∑
^xn2Zpxn
n)
:
Din relat ia d<n (p1) rezult a c aexist a un indice iastfel ^ nc^ at i<p1.
Fieiastfel ^ nc^ at 1 in si 0ip1. Dac ai= 0, atunci
∑
^xn2Zpx0
n= 1 +


+ 1|{z}
p ori0(modp):
Dac a 1 i<p1, atuncip1jn si conform Lemei 2.7.1 avem:
∑
^xn2Zpxi
n0(modp):


36 CAPITOLUL 2. CONGRUENT E
Observat ia 2.7.3. Grupul multiplicativ al corpului Zpeste un grup ciclic
de ordinulp1 (elementul s au ^ n generator este orice clas a de resturi care
cont ine o r ad acin a primitiv a modulo p). De aceea suma din Lema 2.7.1
poate  interpretat a ca suma puterilor de exponent male tuturor r ad acinilor
de ordinp1 din 1 cuprinse ^ n Zp. Dac a (p1;m) =d, o astfel de
sum a se descompune ^ n dsume, ecare dintre ele ind egal a cu suma tuturor
r ad acinilor de ordinp1
ddin 1. Enunt ul Lemei 2.7.1 este o consecint  a a
faptului c a suma tuturor r ad acinilor de ordin rdin 1 este 1 c^ and r= 1  si
este nul a c^ and r2.
Teorema 2.7.4. (Warning). Fief(X1;:::;X n)2Z[X1;:::;X n]cugradf =
d<n  sid1. Dac aNfeste num arul de solut ii ale congruent ei f(x1;:::;x n)
0( modp), atunciNf0( modp). (Dac a gradul dal polinomului f(X1;:::;X n)
cu coecient i ^ ntregi este mai mic dec^ at num arul nal variabilelor, atunci
num arul solut iilor congruent ei f(x1;:::;x n)0(modp)se divide la p).
Demonstrat ie. Consider am polinomul ( X1;:::;X n) = (f(X1;:::;X n))p1
1. Atunci ( X1;:::;X n)2Z[X1;:::;X n]  sigrad  =d(p1)< n(p1),
deci, conform propozit iei 2.7.2 avem:
∑
^x1;:::;^xn2Zp(x1;:::;x n)0(modp):
Dar din relat ia f(x1;:::;x n)0(modp) rezult a ( x1;:::;x n)1(mod
p), iar dinf(x1;:::;x n)̸0(modp), rezult a (conform micii teoreme a lui
Fermat )f(x1;:::;x n)0(modp).
Prin urmare,
∑
^x1;:::;^xn2Zp(x1;:::;x n)Nf(modp)0(modp):

Corolarul 2.7.5. Teorema lui Chevalley Dac af(X1;:::;X n)2Z[X1;:::;X n]
este un polinom omogen de grad d,0<d<n , atunci congruent a f(x1;:::;x n)
0(modp)are cel put in o solut ie nebanal a (adic a o solut ie cu (^x1;:::; ^xn)̸=
(^0;:::; ^0)).
Demonstrat ie. AvemNf1 deoarece (0 ;:::; 0) este solut ie  si Nf0(mod
p), deciNf2.
Exemplul 2.7.6. Fied= 2  sip2. Dac a
f=∑
1i;jnaijXiXj

2.7. CONGRUENT E POLINOMIALE ^IN MAI MULTE VARIABILE 37
este o form a p atratic a cu aij2Z sin3, atunci congruent a f(x1;:::;x n)
0(modp) are cel put in o solut ie nebanal a.
Fie acumn= 2;f(X;Y ) =aX2+bXY +cY2. Este sucient s a se
examineze polinoamele de tipul f(X;Y ) =aX2+bY2, adic a congruent ele
ax2+by20(modp).

Urm atorul rezultat se deduce direct din teorema lui Chevalley.
Teorema 2.7.7. Fief(x1;:::;x n)o form a p atratic a cu coecient i ^ ntregi.
Dac an3, atunci congruent a
f(x1;:::;x n)0(modp)
admite  si o solut ie nenul a.
Cazul formelor p atratice de o nedeterminat a nu prezint a interes(dac a a̸
0(modp)atunci congruent a ax20(modp)are numai solut ia nul a).
S a examin am acum cazul formelor p atratice binare.
Vom considera c a p̸= 2(pentrun= 2;p= 2 se pot trece ^ n revist a u sor
toate formele p atratice respective). ^In acest caz forma poate  scris a astfel:
f(x;y) =ax2+ 2bxy+cy2:
Determinantul acesteia acb2^ l vom nota cu d.
Teorema 2.7.8. Congruent a
f(x;y)0(modp) (p̸= 2) (15)
are o solut ie nebanal a, dac a  si numai dac a determinantul s au deste di-
vizibil cupsau este rest p atratic modulo p.
Demonstrat ie. Este evident c a pentru dou a forme f sif1, echivalente peste
corpul Zp, congruent ele 15 admit sau nu , simultan, o solut ie nenul a. Mai
mult, indc a prin trecerea de la o form a echivalent a determinantul se^ nmult e ste
cu p atratul unui element nenul al corpului Zp, ^ n demonstrat ia teoremi se
poate ^ nlocui forma fcu orice form a echivalent a. Orice form a este echiva-
lent a cu o form a diagonal a. Se poate astfel considera c a
f=ax2+cy2; d =ac:
Dac aa0 sauc0(modp), teorema este evident a. Dac a^ ns a ac̸
0( modp)  si congruent a 15 admite solut ia nenul a ( x0;y0), atunci din congruent a
ax2
0+cy2
00(modp)

38 CAPITOLUL 2. CONGRUENT E
se obt ine
ac(cy0
x0)2(modp)
(fract iaw=u
v( modp) reprezint a rezultatul^ mp art irii^ n corpul Zp, adic a
solut ia congruent ei vwu(modp)). Altfel, (d
p= 1):
Reciproc, dac a, (d
p) = 1  si acu2(modp), se poate lua ( x0;y0) =
(u;a): 
Denit ia 2.7.9. Dac apeste un num ar prim, iar a2Z;(a;p) = 1, spunem
c aaeste rest p atratic modulo pdac a congruent a x2a(modp) are solut ii.
Observat ii:
1)Fiea;b2Z;(a;b) = 1. Atunci congruent a
ax2+by20(modp)
are o solut ie nebanal a dac a  si numai dac a abeste rest p atratic modulo
p.
^Intr-adev ar, dac a x2
0+ab0(modp), atunciax2
0+a2b0(modp):
Reciproc, e ax2
0+by2
00(modp);(x0;y0) solut ie nebanal a. Atunci
(p;x 0y0) = 1, deci exist a y1astfel ^ nc^ at y0y11(modp). Rezult a c a
0a2x2
0y2
1+ab(y0y1)2(ax0y1)2+ab(modp):
2)Evident, orice aimpar este rest p atratic modulo 2.
Denit ia 2.7.10. Un polinom F(X1;:::;X n)2Z[X1;:::;X n] se nume ste
absolut ireductibil dac a este ireductibil chiar ^ n C[X1;:::;X n]:
Un rezultat important este acela c a pentru Fabsolut ireductibil exist a
o constant a M(F) astfel ^ nc^ at din p > M (F) rezult a c a F(X1;:::;X n)
0(modp) este rezolubil a.
^Intr-o formulare mai precis a avem:
Teorema 2.7.11. Exist a o constant a C(F), depinz^ and de Fiar nu dep,
astfel ^ nc^ at s a avem jN(F;p)pn1j<C(F)
pn1frac12, undeN(F;p)este
num arul solut iilor congruent ei F(x1;:::;x n)0(modp):
Evident, pentru psucient de mare, aceast a relat ie implic a N(F;p)̸= 0:
Acest rezultat a fost obt inut de Andre Weil ^ n 1948. O demonstrat ie mai
elementar a , bazat a pe lucr arile lui A. Stepanov, se g ase ste ^ n cartea lui W.
Schmidt, Ecuations over nite elds (Lecture Notes in Math. Vol. 536,
1976).
^In cazul c^ and n=p, prim  sid=p1, un exemplu simplu este F=
Xp1
1+


+Xp1
n.^Intr-adev ar, pentru x0(modp), avemxp11(mod
p), de unde se obt ine F(x1;:::;x n)̸0( modp), dac a ( ^x1;:::; ^nn)̸= (^0;:::; ^0):

2.8. SIMBOLUL LUI LEGENDRE 39
Observat ia 2.7.12. O consecint  a interesant a a teoremei de mai sus este
aceea c a un polinom neconstant f2Z[X1;:::;X n] nu poate lua valori exclu-
siv ^ n mult imea Pa numerelor prime. ^Intr-adev ar, dac a p siqsunt numere
prime sucient de mari , atunci, folosind  si teorema chinez a a resturilor,
congruent a f(x1;:::;f n)0(modpq) este rezolvabil a.
2.8 Simbolul lui Legendre
Denit ia 2.8.1. Dac a p este un num ar prim, p3, iara2Z;(a;p) = 1,
atunci simbolul lui Legendre (a
p) se dene ste astfel:
(a
p) ={
1;dac a congruent a x2a(modp)are solut ii
1;dac a congruent a x2a(modp)nu are solut ii
Observat ia 2.8.2. 1.Dac a congruent a x2a( modp);p3, are solut ii,
atunci ea are exact dou a solut ii.
(2a(modp),()2a(modp))
2.Simbolula
pse poate extinde pe Zprina
p= 0, dac apja.
3.Dac aab(modp),(a
p) = (b
p):
Denit ia 2.8.3. Fie p un num ar natural  si a un ^ ntreg, relativ prim cu p, a
se num ste rest p atratic modulo p dac a congruent a x2a( modp) are solut ii,
^ n caz contrar, spunem c a a nu este rest p atratic modulo p.
Exemplu . Din congruent ele:
121021(mod 11)
22924(mod 11)
32829(mod 11)
42725(mod 11)
52623(mod 11)
rezult a c a 1 ;3;4;5;9 sunt resturi p atratice modulo 11, iar 2 ;6;7;8;10 nu sunt.
Propozit ia 2.8.4. Dca a p este un num ar prim impar, atunci, ^ ntr-un sistem
de resturi nenule modulo p exist a:p1
2resturi p atratice  sip1
2resturi p atratice
modulo p.

40 CAPITOLUL 2. CONGRUENT E
Demonstrat ie. S a observ am c a numerele 12;22;:::;p1
2sunt prime cu p  si
necongruente ^ ntre ele modulo p. Din relat ia i2j2(modp), cu 1 i <
jp1
2,pj(j+i)(ji), de undepj(j+i) saupj(ji), ceea ce nu se poate
deoarecej+ip1  sijip1.
Fie n un rest p atratic modulo p. Atunci exist a i2 f1;2;3;:::;p 1gastfel
cai2n(modp). Dac ap
2<i<p 1, atunci  si pisatisface congruent a
x2n(modp), iar 1< pi <p
2. Astfel un rest p atratic modulo p este
congruent modulo p cu unul din numerele 12;22;:::; (p1
2)2.
Prin urmare, ^ ntr-un sistem redus de resturi modulo p exist a exactp1
2
resturi p atratice, celelaltep1
2resturi modulo p neind resuri p atratice, mod-
ulo p. 
Observat ia 2.8.5. Dac a p este un num ar prim, iar a2Z;(a;p) = 1,
atunci din congruent a ap110(modp))ap1
21(modp) sauap1
2
1(modp).
Teorema 2.8.6 (Criteriul lui Euler ).Dac a p este num ar prim, p3, iar
a2Z;(a;p) = 1 , atunci avem (a
p)ap1
21(modp):
Demonstrat ie. Fie (a
p) = 1. Atunci exist a 2Z, astfel ca2a(modp).
Cum (;p) = 1, conform teoremei lui Fermat avem p11(modp) deci
ap1
21(modp).
Astfel congruent a yp1
210( modp) are ca solt ii toate resturile p atratice
modulo p care, conform propozit iei anterioare sunt ^ n num arp1
2.
Pe de alt a parte, congruent a yp1
210( modp) are cel multp1
2solut ii
(conform teoremei Lui Lagrange). Prin urmare, orice solut ie a congruent ei
yp1
20(modp) este un rest p atratic modulo p. 
Aplicat ie 1. Dac ap3 este prim, atunci avem:
(1
p) ={
1;dac ap1(mod 4)
1;dac a congruent a p3(mod 4)
Conform criteriului lui Euler avem:
(1
p)(1)p1
2(modp);
iar pe de alt a parte:
(1
p) ={
1;dac ap1
2= 2
k
1;dac ap1
2= 2
k+ 1

2.9. PROPRIET AT I ALE SIMBOLULUI LUI LEGENDRE 41
2.9 Propriet at i ale simbolului lui Legendre
Propozit ia 2.9.1. Simbolul lui Legendre este o funct ie (a
p) :Z! f1;0;1g
total multiplicativ a.
Demonstrat ie. Putem presupune c a ( p;ab) = 1  si folosind criteriul lui Euler
avem:
(ab
p) = (ab)p1
2=ap1
2bp1
2= (a
p)(b
p)(modp:)
Deoarece termenii sunt ^ n f1;1g sip3, din congruent a mod p rezult a
egalitatea. 
Observat ia 2.9.2. Reamintim c a pentru p3, elementele mult imii:
S={
p1
2;p1
3;:::;1;1;:::;p1
2}
se numesc cele mai mici resturi modulo p . Mult imea S constituie un sistem
complet de reprezentant i pentru Z
p;82S) jj p1
2<p
2.
Fiea2Z;(a;p) = 1  sil2 f1;2;:::;p1
2g S. Atunci exist a un unic
al2Sastfel ^ nc^ at a
lal(modp). Fie:

adef=jflj1lp1
2 sial<0gj:
Lema 2.9.3 (Lema lui Gauss ).Are loc relat ia (a
p) = (1)
a.
Demonstrat ie. Dac a 1 i < j p1
2, atuncia
i̸ a
j(modp).^Intr-
adev ar avem 0 <i+jp1<p si 0<ji<p1
2, decip-a
(i+j)  si
p-a
(ji)).
a
1 a1(modp);
a
2 a1(modp);
…
a
p1
2 ap1
2(modp);
undeaS2 f1;2;:::;p1
2gsunt distincte, iar
aeste num arul termenilor neg-
ativi din partea dreapt a a congruent elor de mai sus. ^In acest fel s-a denit o
funct ie:
f1;2;:::;p1
2gF ! f1;2;:::;p1
2g;F(s) =as;

42 CAPITOLUL 2. CONGRUENT E
undeaseste determinat de relat iile: as2 f1;2;:::;p1
2g sia
s as(mod
p). Dar, dac a s̸=s′, atuncia
s̸a
s′(modp), decias̸=a′
s. Aceasta ^ n
seamn a c a funct ia F este injectiv a. Cum domeniul de denit ie coincide cu
codomeniul, rezult a c a F este o funct ie bijectiv a. Astfel:
a1
a2




ap1
2= (p1
2)!;
de unde :
(a
1)
(a
2)




(a
p1
2) = (a1)
(a2)




(ap1
2)!(modp):
De aici deducem:
ap1
2
(p1
2)!(1)
a
(p1
2)!(modp);
de undeap1
2(1)
a(modp).^Ins a, conform criteriului lui Euler avem:
ap1
2(a
p)(modp), ceea ce arat a c a (a
p) = (1)
a: 
2.10 Legea reciprocit at ii p atratice
Teorema 2.10.1 (Legea reciprocit at ii p atratice a lui Gauss, 1796 ).
Fie p un num ar prim, p3. Atunci:
1.(1
p) = (1)p1
2
2.(2
p) = (1)p21
8
3.Dac a q este un num ar prim, q3 siq̸=p, atunci:
(p
q)(q
p) = (1)p1
2
q1
2:
Demonstrat ie. 1.S-a demonstrat deja.
2.S a observ am c a dac a p= 8k1, atuncip21 = (8k1)21
0(mod 16), iar dac a p= 8k3;atuncip21 = (8k3)21
0(mod 8), deci:
p21
8este par dac a p1(mod 8) sau p7(mod 8)  si
p21
8este impar dac a p3(mod 8) sau p5(mod 8):
Prin urmare, enunt ul dat este echivalent cu urm atorul:

2.10. LEGEA RECIPROCIT AT II P ATRATICE 43
2
p={
1;dac ap1(mod 8) sau p7(mod 8);
1;dac ap3(mod 8) sau p5(mod 8)
Aplic^ and teorema lui Gauss pentru a= 2, avem:

2=jfl2 f1;2;:::;p1
2gj2
l>p1
2gj;
iar din relat iile 2
l>p1
2 sil>p1
4)
2=p1
2[p1
4].
Examin am succesiv cele 4 cazuri:
-dac ap= 8k+ 1, atunci [p1
4] = 2k, iarp1
2= 4k;
20(mod 2), de
unde rezult a (2
p) = 1.
-pentrup= 8k+ 7, avem [p1
4] = 2k+ 3,p1
2= 4k+ 3;
2= 2k+ 2  si
(2
p) = 1.
-dac ap= 8k+ 3, atunci [p1
4] = 2k, iarp1
2= 4k+ 1;
21(mod 2),
de unde rezult a (2
p) =1.
-dac ap= 8k+ 5, atunci [p1
4] = 2k+ 1, iarp1
2= 4k+ 2;
2
1(mod 2), de unde rezult a (2
p) =1.
3.Conform Lemei lui Gauss avem (q
p) = (1), unde:
=j{
x2 f1;:::;p1
2gj9y2Zastfel ca p
2<qxpy< 0}
j:
Mai mult, din relat iile x2 f1;:::;p1
2g siqxpy < 0 rezult ay > 0
 sipy <qx +p
2>q
p
2+p
2= (q+ 1)
p
2, deciy <q+1
2, de unde rezult a
1yq1
2.
Prin urmare, dac a p
2<qxpy< 0, atunci qx este congruent modulo p
cu un num ar negativ bine denit din mult imea S={
p1
2;p3
2;:::;1;1;:::;p1
2}
.
Observ am c a y este bine determinat de x, deoarece 1 yq1
2 si clasa
sa modulo q este determinat a. Deci,
=j{
(x;y)j1xp1
2;1yq1
2 sip
2<qxpy< 0}
j:
Schimb^ and rolurile numerelor p  si q, avem (p
q) = (1)′, unde:
′=j{
(x;y)j1xp1
2;1yq1
2 siq
2<pyqx< 0}
j:

44 CAPITOLUL 2. CONGRUENT E
Obt inem (p
q)
(q
p) = (1)+′

Mult imile al c aror cardinal ne dau  si′sunt disjuncte, a sa c a +′
reprezint a cardinalul reuniunii celor dou a mult imi. Prin urmare:
+′=j{
(x;y)j1xp1
2;1yq1
2 sip
2<pyqx<q
2}
j:
2.11 Ordinul unui num ar modulo n
Fie n un num ar natural nenul  si a2Z, prim cu n. Din teorema lui Euler  stim
c aaφ(n)1(modn). Mult imea numerelor naturale ind bine ordonat a, va
exista un cel mai mic num ar natural nenul kcare s a verice relat ia ak
1(modn).
Denit ia 2.11.1. Fie n un num ar natural  si a2Z, prim cu n. Cel mai mic
num ar natural nenul k pentru care ak1(modn) se nume ste ordinul lui a
modulo n  si ^ l vom nota ord na.
De exemplu, din 422(mod 7);431(mod 7) )ord74 = 3:
Vom prezenta c^ ateva propriet at i de baz a ale ordinului unui ^ ntreg.
Propozit ia 2.11.2. Dac a a  si n sunt relativ prime, cu n>0, atuncik2N
este solut ie a congruent ei ak1(modn)dac a  si numai dac a ord najk. De
aici obt inem un rezultat important care u sureaz a determinarea lui ord na.
Corolarul 2.11.3. Dac a n este num ar natural nenul  si a este un ^ ntreg,
prim cu n, atunci ord najϕ(n).
Astfel, dac a dorim s a determin am ord73, cumϕ(7) = 6 , calcul am doar
3kpentruk2 f1;2;3;6g. Astfel:
313(mod 7)
322(mod 7)
336(mod 7)
361(mod 7)
Un rezultat des folosit ^ n continuare este dat de urm atoarea propozit ie.
Propozit ia 2.11.4. Fie n num ar natural nenul  si a2Z;(a;n) = 1 . Atunci,
ai=aj(modn)dac a  si numai dac a ij(modord na).

2.12. R ADACINI PRIMITIVE 45
2.12 R ad acini primitive
Denit ia 2.12.1. Dac a (r;n) = 1;n > 0  siord nr=φ(n), atunci r se
nume ste r a d a cin a primitiv a modulo n.
Spre exemplu, am ar atat c a 3 este r a d acin a primitiv a modulo 7. Dar
trebuie s a remarc am c a nu pentru toate numerele n exist a r ad acini primitive,
de exemplu, pentru n= 8, obt inem 3252721(mod 8). Astfel,
ord83 =ord85 =ord87 = 2 ̸= 4.
Propozit ia 2.12.2. Dac a r este r ad a cin a primitiv a modulo n, atunci r;r2;:::;rφ(n)
formeaza un sistem redus de resturi modulo n.
Presupunem c a un num ar natural nenul n are o r ad a cin a primitiv a. Pen-
tru a stabili num arul total al acestora, avem nevoie de urm atoarea propozit ie.
Propozit ia 2.12.3. Dac aord na=k sil>0este un num ar natural, atunci,
ord nal=k
(k;l):
Corolarul 2.12.4. Fie r o r ad a cin a primitiv a modulo n. Atunci rkeste
r ad a cin a primitiv a modulo n dac a si numai dac a (k;φ(n)) = 1 .
Teorema 2.12.5. Dac a n are o r ad a cin a primitiv a, atunci are exact φ(φ(n))
r ad a cini primitive.
Demonstrat ie. Fie r o r ad a cin a primitiv a modulo n. Din propozit ia 2.12.2,
r;r2;:::;rφ(n)este sistem redus de resturi modulo n. Conform corolarului
2.12.4,rkeste r ad a cin a primitiv a modulo n dac a  si numai dac a ( k;φ(n)) = 1.
Atunci, exist a φ(φ(n)) astfel de numere, deci tot at^ atea r ad acini primitive
module n. 
Denit ia 2.12.6. Fief2Z[X], un polinom de grad1. Spunem c a xeste
o r ad acin a a lui fmodulon, dac af(x)0(modn).
De exemplu, f=X2+ 2 are dou a r ad acini necngruente modulo 3, pe
x1(mod 3)  si x2(mod 3):
Teorema 2.12.7. Fiepun num ar prim  si djp1. Atunci,Xd1are exact
dr ad acini necongruente modulo p.
Demonstrat ie. Fiep1 =de. Atunci,
Xp11 = (Xd1)(xd(e1)+Xd(e2)+


+Xd+ 1)
(Xd1)g(X):

46 CAPITOLUL 2. CONGRUENT E
Din mica teorem a a lui Fermat, Xp11 arep1 r ad acini necongruente
modulop si orice astfel de r ad acin a este r ad acin a pentru Xd1 sau pentru
g. Conform teoremei Lagrange, gare cel mult d(e1) =pd1 r ad acini
necongruente modulo p. Astfel,Xd1 are cel put in ( p1)(pd1) =d
r ad acini necongruente modulo p. Dac a aplic am ^ nc a o dat a teorema 2.6.5
pentru polinomul Xd1, obt inem c a el are cel mult dsolut ii necongruente
modulop. Astefel,Xd1 are exact dsolut ii necongruente modulo p.
Folosind acest rezultat, putem determina c^ ate numere naturale necongru-
ente au un ordin dat modulo p. 
Teorema 2.12.8. Fiepun num ar prim  si djp1. Atunci, num arul nu-
merelor naturale de ordin dmodulopeste egal cu ϕ(d).
Demonstrat ie. Pentrudjp1, not am cu F(d) num arul numerelor naturale
de ordindmodulop, mai mici dec^ at p.
Cum ordinul modulo pal unui num ar care nu este multiplu de pdivide
p1, obt inem p1 =∑
djp1F(d) =∑
djp1ϕ(d):
Dac a ar at am c a F(d)ϕ(d), din∑
djp1ϕ(d) =∑
djp1F(d), va rezulta egal-
itateaF(d) =ϕ(d), pentrudjp1.
Pentru aceasta, e djp1. Dac aF(d) = 0, atunci F(d)ϕ(d).Presupunem
c a exist aacuord pa=d. Atunci,a;a2;:::;adnu sunt congruent e modulo p.
Din (ak)dakd1(modp), pentru 1 kd, rezult a c a acestea
sunt r ad acini modulo pale polinomului Xd1. Folosind propozit ia 2.12.3,
ord pak=ddac a  si numai dac a ( k;d) = 1.
Deci, dac a exist a r ad acini de ordin dmodulop, ele sunt exact ^ n num ar
deϕ(d). AstfelF(d)ϕ(d). 
Corolarul 2.12.9. Orice num ar prim are r ad acini primitive.
Demonstrat ie. Fiepnum ar prim. Din teorema anterioar a, exist a ϕ(p1)
numere necongruente modulo p, de ordin p1. Cum ecare dintre aces-
tea este o r ad acin a primitiv a modulo p, obt inem c a pareϕ(p1) r ad acin
primitive. 
Teorema 2.12.10. Dac apeste un num ar prim impar cu r ad acina primitiv a
r, atuncirsaur+peste r ad acin a primitiv a modulo p2.
Demonstrat ie. ord pr=ϕ(p) =p1. Not am ord p2r=m. Dinrm
1(modp2), rezult arm1(modp), adic a
p1jm: (16)

2.12. R ADACINI PRIMITIVE 47
Din corolarul 2.12.9, avem
mjϕ(p2) =p(p1): (17)
Astfel, din 16  si 17, rezult a m=p1 saum=p(p1):
Dac am=p(p1),reste r ad acin a primitiv a modulo p2.
Pentrum=p1 ar at am c a t=r+peste r ad acin a primitiv a modulo p2.
Pentru aceasta, abserv am mai ^ nt^ ai c a teste  si ea r ad acin a primitiv a
modulop, cumtr(modp). Din calculele f acute anterior, rezult a c a
ord p2t=p1 sauord p2t=p(p1). Pentru a ^ ncheia demonstrat ia ar at am
c aord p2t̸=p1.
tp1= (r+p)p1=rp1+p2∑
j=1Cj
p1rpj1pj+pp1rp1+(p1)p
rp2
1 +p(p1)rp21p
rp2(modp2):
Dac atp11(modp2), atuncip
rp10(modp2), de unde rp2
0(modp), ceea ce este fals( p̸ jr).
De exemplu, pentru p= 7,  stim c a 3 este r ad acin a primitiv a. Cum
3643̸= 1(mod 49), 3 este r ad acin a primitiv a modulo 49.
Dac a consider am acum p= 487, o r ad acin a primitiv a este 10. Din 10486
1(mod 4872), rezult a c a 10 + 487 = 497 este r ad acin a primitiv a modulo
4872. 
Teorema 2.12.11. Fiepun num ar prim impar. Atunci, exist a r ad acini
primitive modulo pk, pentru orice knum ar natural.
Mai mult, dac a reste o r ad acin a primitiv a modulo p2,reste r ad acin a
primitiv a modulo pk, pentru orice k2.
Demonstrat ie. Fiero r ad acin a primitiv a modulo p, care este  si r ad acin a
primitiv a modulo p2. Atunci, din teorema 2.12.10, rp1̸= 1(modp2).
Ar at am, prin induct ie matematic a, c a, pentru orice k2:
rpk2(p1)̸= 1(modpk):
Pentruk= 2, relat ia se veric a. Presupunem c a ea este adev arat a pentru
k>2  si ar at am c a ea r am^ ane adev arat a pentru K+ 1.
Aplic^ and teorema lui Euler, rϕ(pk1)=rpk2(p1)1(modpk1):
Exist a astfel d, num ar natural pentru care:
rpk2(p1)= 1 +d
pk1: (18)
Din, ipoteza de induct ie, rpk2(p1)̸= 1( modpk). De aici, rezult a c a p̸ jd.
Ridic am la puterea p^ n relat ia (18)  si obt inem
rpk1(p1)= (1 +d
pk1)p1 +d
pk(modpk1):

48 CAPITOLUL 2. CONGRUENT E
Cump̸ jd, rezult arpp1̸= 1(modpk+1):
Deci, pentru orice k2;rpk2(p1)̸= 1(modpk):
Not amm=ord pkr. Atunci,mjϕ(pk) =pk1(p1). Dinrm1(mod
pk), rezult arm1(modp). Deci,p1jm. Obt inem astfel m=pt(p1),
unde 0 tk1. Dac atk2, atuncirpk2(p1)(rpt(p1))pk2t=
1(modpk). Deci,t=k1, de unde m=ϕ(pk).
Ca exemplu, 3 este r ad acin a primitiv a modulo 7k, cuk1.
S a vedem ce putem preciza despre puterile lui 2. Se observ a imediat c a
1 este r ad acin a primitiv a modulo 2, iar 3 este r ad acin a primitiv a pentru 4.


Capitolul 3
Probleme referitoare la
congruent e polinomiale  si
observat ii
3.1 Exercit ii
Exercit iul 3.1.1. ^In progresia aritmetic a f8k+ 7jk2Ngse a
 a o innitate
de numere prime.
Demonstrat ie. S a presupunem c a mult imea P \f 8k+ 7jk2Ngeste innit a.
FieP \ f 8k+ 7jk2Ng=f7;p1;p2;:::;p ng, iatM= [2(7
p2
p3





pn)]22:FieM= 2
q1




qsdescompunerea canonic a a num arului M.
Dac a 8i;qi1(mod 8), atunci M2(mod 8), ceea ce contrazice faptul c a
M 2(mod 8). Pe de alt a parte avem 2 [4(7
p2
p3




pn)]2)](mod
qi);8i;1′s. Deci, (2
q1) = 1, de unde rezult a qi= 1;7(mod 8). Deci
exist ai02 f1;:::;s gastfel ^ nc^ at qi0
equiv 7(mod 8);qi0=2 f7;p2;p3;:::;p ng. Aceasta contravine presupunerii de
nitudine. 
Exercit iul 3.1.2. Fie p un num ar prim, p3 astfel ^ nc^ at q= 2p+ 1 este
prim  sip3(mod 4). Atunci num arul Mp= 2p1 nu este prim(avem
qj2p1).
Demonstrat ie. Din relat ia p= 4k+ 3 de ducem q= 8k+ 7, deci (2
p) =
1, adic a(t in^ and seama de criteriul lui Euler)2q1
2equiv 1(modq) sau 2p
10(modq). Spre exemplu, pentru p= 23, num arul lui Mersenne M23
se divide cu 47. Vom vedea ^ n continuare c a este adev arat a  si armat ia
reciproc a. Prin urmare:
p= 4k+3 prim  si 2 p+1 divideMp= 2p1 implic a 2p+1 prim(criteriu dat de Euler ^ n 1732)
49

50CAPITOLUL 3. PROBLEME REFERITOARE LA CONGRUENT E POLINOMIALE S I OBSERVAT II

Propozit ia 3.1.3. Fiep>2u num ar prim, h<p;n =hp+1saun=hp2+1
 si2h̸1(modn), dar 2n11(modn). Atunci n este num ar prim.
Demonstrat ie. Not amn=hpb+ 1, undeb2 f1;2g si cud=ord2(modn).
Atuncidjn1;d-h si cumn1 =hpb)pjd. Dard=ord2(modn) divide
φ(n), decipjφ(n) =p11
1
:::pk1
k
(p11)
(pk1), dac an=p1
1
:::pk
k.
Deoarecep-n, se obt ine c a p divide ( p11)




(pk1), prin urmare n are
un factor prim P1(modp), adic an=Pm. Deoarece n1P(modp)
avemm1(modp). Dac am< 1, avemn= (up+ 1)(vp+ 1);1uv si
hpb1=uvp+v+u.
Dac ab= 1, se obt ine hp=uvp+v+u;de undepuvp < h < p , o
contradict ie.
Dac ab= 2, se obt ine hp=uvp+v+u;pju+v;u+vp, de unde
2vu+vp;v >1
2p,  siuv < h < p;uv p2;up2
v<2(p2)
p<2.
Prin urmare u= 1, dac avp1;up1, de asemenea o contradict ie.
Rezult a c a m= 1  sin=Peste prim.
S a presupunem c a num arul Mersenne Mpse divide cu q= 2p+ 1. Lu am
h= 2  sin2p+ 1 ^ n enunt ul propozit ie anterioare. Avem ^ n mod evident
h<p  si 2h̸1(modn), dar  si 2n1= 22p1(modn), conform ipotezei ca
2p+ 1jMp. Prin urmare 2 p+ 1 este prim. 
Observat ia 3.1.4. Lucas a dat urm atorul criteriu de primalitate: Mk= 2k
1 este prim dac a  si numai dac a MkjLk1, undeLneste denit de recurent a:
L1= 4;Ln+1=L2
n2
. Aplicat ia urm atoare ofer a un criteriu pentru ca num arul lui Fermat Fk=
22k+ 1 s a e prim.
Prezent am mai ^ nt^ ai urm atorul criteriu mai general.
Propozit ia 3.1.5. Fiem2un num ar prim, h<2m sin=h2m+1nerest
p atratic modulo p pentru un prim p3. Atunci n este un num ar prim dac a
 si numai dac a pn1
2 1(modn).
Demonstrat ie. S a presupunem c a avem n1(mod 4), avem (p
n) = (n
p) =
1, de unde pn1
2 1(modn) conform criteriului lui Euler. Reciproc, s a
presupunem c a avem pn1
2 1(modn). Fie P un factor prim al lui n  si e
d ordinul lui p(modP). Sunt adev arate urm atoarele congruent e:
pn1
2 1(modP);pn11(modP);pP11(modP):

3.1. EXERCIT II 51
Utiliz^ and propriet at ile lui d=ord p (modP), se obt ine:
d-n1
2;djn1  sidjP1;adic a 2 -2m1h;dj2mh;djP1;de unde 2mjd si 2mjP1:
DeciP= 2mx+ 1. Deoarece n1P(mod 2m), avemn
P= 1(mod 2m),
decin= (2mx+ 1)(2my+ 1);x1;y1. Se obt ine 2mxy< 2mxy+x+y=
h<2m, de undey= 0  sin=Peste prim. Demonstrat ia este ^ ncheiat a. 
S a lu am acum ^ n enunt ul propozit iei, h= 1;m= 2k, decin=Fk.
DeoareceFk2( mod 3);Fknu este rest p atratic (mod 3). Se obt ine urm atorul
corolar.
Corolarul 3.1.6. Fkeste prim dac a  si numai dac a Fkj(3Fk1
2+ 1) (criteriul
dat de Lucas ^ n 1981).
Observat ia 3.1.7. FieFn= 22n+ 1;n2  si ek2. Se poate ar ata c a
urm atoarele condit ii sunt echivalente:
i)Fneste prim  si (k
Fn) =1;
ii)kFn1
2=1(modFn).
Acest rezultat este cunoscut sub numele de testul lui Pepin .
Propozit ia 3.1.8. Fie p un num ar prim, p3( mod 8)  si astfel ^ nc^ atp1
2=
qeste prim. Atunci ⟨^2⟩=Z
p(spunem c a 2 este r ad acin a primitiv a modulo
p).
Demonstrat ie. Avem jZ
pj=p1 = 2q, deciord(^2)2 f2;q;2qg. Deoarece p-
221 = 3 este sucient s a ar at am 2q̸1(modp) sau 2p1
2̸1(modp),
(2
p) =1. Dar 2 nu este rest p atratic modulo p, deoarece p3(mod 8),
deciord(^2) = 2q=p1;⟨^2⟩=Z
p. Spre exemplu, dac a p= 63, atunci q= 31
 si^2 genereaz a Z
63. 
Observat ia 3.1.9. S tim c a polinoamele de forma x2n+ 1(polinoamele ciclo-
tomice de ordinul n+ 1) sunt ireductibile ^ n Z[X] (^ nlocuim X cu X+ 1  si
aplic am criteriul lui Einstein).
Dac a p este prim, atunci pentru orice n2, polinoamele  2n+1(X) =
X2n+ 12Z[X] sunt reductibile modulo p.

52CAPITOLUL 3. PROBLEME REFERITOARE LA CONGRUENT E POLINOMIALE S I OBSERVAT II
Demonstrat ie. Este sucient s a demonstr am armat ia pentru polinomul:  8(X) =
X22+ 1 =X4+ 1, deoarece pentru n2 avem:X2n+ 1 = (X2n2)4+ 1  si
not^ and cuY=X2n2avemX2n+ 1 =Y4+ 1.
Fie p un num ar prim, dac a p= 2, atunci  8(X) = (X4+^1)2^ nZ2[X],
deci armat ia se veric a ^ n acest caz.
S a presupunem c a p3. Dac a (1
p) = 1, ea2Zastfel ^ nc^ at a2
1(modp). Atunci ^ n Zp[X] avem:
X4+^1 =X4^a2= (X2^a)(X2+ ^a):
Dac ai
p=1, atunci: (2
p) = (1
p)(2
p) =1
(2
p)  si avem (2
p) = 1 sau
(2
p) = 1.
Fie (2
p) = 1  sia22(modp);a2Z. Avem:
X4+^1 = (X4+^1)22X2
de unde:
X4+^1 = (X4+^1)2^a2X2= (X2+ ^aX+^1)(X2^aX+^1):
Fie (2
p) = 1  sia2 2(modp);a2Z. Avem:
X4+^1 = (X4+^1)2+ 2X2
de unde:
X4+^1 = (X4+^1)2+^a2X2= (X2+ ^aX^1)(X2^aX^1):
AstfelX4+ 1 se descompune ^ n produs de polinoame de gradul doi ^ n
Zp[X], oricare ar  num arul prim p. 
3.2 Probleme
Vom prezenta mai^ nt^ ai c^ ateva concluzii la partea teoretic a necesare rezolv arii
de probleme specice congruent elor.
Denit ia 1. Dou a numere ^ ntregi a c si b se numesc congruente modulo
n, unde n este num ar ^ ntreg, dac a njab. Se scrieab(bmodn)  si se
cite ste: a congruent cu b modulo n.
Denit ia 2. Dou a numere ^ ntregi a  si b se numesc congruente modulo n,
unde n este un ^ ntreg nenul, dac a prin ^ mp art irea la m dau acela si rest, iar
pentrun= 0 dac a sunt egale.
C^ ateva propriet at i:

3.2. PROBLEME 53
1.Relat ia de congruent  a este o relat ie de echivalent  a, adic a este re
exiv a,
simetric a  si tranzitiv a.
2.Dou a relat ii de congruent  a se pot aduna, sc a dea sau ^ nmult i membru
cu membru.
3.Ambii membrii ai unei relat ii de congruent  a pot  ridicat i la aceea si
putere ^ ntreag a pozitiv a.
4.Ambii membrii ai unei relat ii de congruent  a pot  ^ nmult it i cu orice
num ar ^ ntreg pozitiv, ^ nmult ind sau nu ^ n acela si timp  si modulul.
5.Orice relat ie de congruent  a ^ n raport cu un modul dat este o relat ie de
congruent  a ^ n raport cu un modul care este divizor al modulului dat.
6.Ambii membrii ai unei relat ii de congruent  a pot  simplicat i cu orice
factor prim cu modulul.
Relat ia de congruent  a, ind o relat ie de echivalent  a pe mult imea nu-
merelor ^ ntregi, determin a pe aceasta o partit ie, adic a o ^ mp art ire ^ n clase
nevide, disjuncte  si a c aror reuniune acoper a mult imea. Aceste clase, numite
clase de resturi modulo m se pot organiza ca un inel comutativ cu element
unitate, numit inelul claselor de resturi modulo m, sau ca un corp, dac a m
este num ar prim.
Teoremele lui Fermat, Euler, Wilson
Teorema lui Fermat. Pentru orice ^ ntreg a nedivizibil cu un num ar prim
p are loc congruent a:
ap11(modp):
Teorema lui Euler. Pentru orice num ar ^ ntreg a prim cu num ar ^ ntreg are
loc congurent a:
Aφ(n)1(modn):
undeφ(n) este funct ia lui Euler.
Teorema lui Wilson. Dac a p este un num ar prim, atunci
(p1)! + 1 0(modp):
Reciproca teoremei lui Wilson. Dac an>1  si (n1)!+1 10( modn),
atunci n este num ar prim.
Problema 1. S a se demonstreze c a nu exist a patru numere naturale consec-
utive, astfel ca ecare dintre ele s a e o putere ^ ntreg a a unui num ar ^ ntreg
cu exponent ^ ntreg >1.

54CAPITOLUL 3. PROBLEME REFERITOARE LA CONGRUENT E POLINOMIALE S I OBSERVAT II
Solut ie.
Din patru numere consecutive, unul trebuie s a e de forma: 4 k+ 2 cu
m0, ^ ntreg. A. Makowski a demonstrat c a proprietatea este adev arat a
 si pentru trei numere. Pentru dou a numere nu mai este adev arat a, indc a
avem, de exemplu: 23= 8  si 32= 9.
Problema 2. S a se demonstreze c a:201020101
20112N.
Solut ie.
Num arul fract iei ne aminte ste de mica teorem a a lui Fermat , anume:
Dac aa2Z, p num ar natural prim, iar a nu este divizibil cu p, atunci
ap11(modp), 9k2Z, astfel ^ nc^ at ap1=k
p+ 1. Fie, deci, a= 2010
 si p= 2011; se veric a u sor condit iile cerute de mica teorem a a lui Fermat ,
prin urmare exist a k2Z, astfel ^ nc^ at:
201020101
2011=2010201011
2011=k
2011
2011=k2Z:
Observat ii.
1.Av^ and^ n vedere datele exercit iului, este evident c a num arul k este chiar
natural.
2.ap11(modp) (ap1este congruent cu 1 modulo p), deci, ^ap1=
^1,^ap1=^1, ^ nZp.
Problema 3. S a se demonstreze c a dac a un num ar par este suma a dou a
p atrate perfecte, atunci  si jum atatea num arului este suma a dou a p atrate
perfecte.
Solut ie. Dac aa=b2+c2, atunci
1
2a= (b+c
2)2+ (bc
2)2
 si indc a a este par, b  si c au aceea si paritate, decib+c
2 sibc
2sunt ^ ntregi.
Problema 4. Dac aab(modm), demonstrat i c a nanb(modm), pen-
tru orice num ar natural n.
Solut ie
Din relat ia ab(modm),mdivideab)nanb)na
nb(modm).
Problema 5. S a se arate c a pentru orice k2N;37j(1000k1).
Solut ie
Observ am c a 1000 = 37
27 + 1, deci 1000 1(mod 37) )1000k
1(mod 37).

3.2. PROBLEME 55
Problema 6. Ce rest d a num arul N= 3636+ 2121la ^ mp art irea cu 5?
Solut ie
Avem 36 1(mod 5) )36361(mod 5);211(mod 5) )2121
1(mod 5), adun^ and cele dou a relat ii )3636+ 21212(mod 5), deci N d a
restul 2 la ^ mp art irea cu 5.
Problema 7. Dac aab(modm)  sicd(modm), demonstrat i c a ac
bd(modm).
Solut ie
Fie a, b, c, d cele patru numere ab(modm),acbc(modm)  si
bcbd(modm))din proprietatea de tranzitivitate c a acbd(modm).
Problema 8. S a se determine restul ^ mp art iri num arului 1437prin 17.
Solut ie
Orice num ar natural nenul se scrie ca sum a de puteri ale lui 2 )37 =
25+ 22+ 20)1437= 1432
144
14. Pe de alt a parte 1429( mod 17);144
13(mod 17) ;14816(mod 17) ;14161(mod 17);14321(mod 17) )
1437= 1432
144
141
13
14( mod 17) 12( mod 17), deci restul^ mp art irii
num arului 1437prin 17 este 12.
Problema 9. Care este ultima cifr a num arului N= 2222+ 3333+ 4444?
Solut ie
Trebuie s a stabilim restul la ^ mp art irea cu 10 a lui N.
246(mod 10), prin ridicare la puterea 55, obt inem 22206556(mod
10))22226
22(mod 10) )22224(mod 10).
Apoi, 341(mod 10), apoi prin ridicare la puterea 83, obt inem 3332
1831(mod 10) )33333(mod 10).
Avem, 426(mod 10)  si prin ridicare la puterea 222 obt inem 44446222
6(mod 10).
Prin adunarea congruent elor obt inem c a 2222+ 3333+ 4444= 4 + 3 + 6 
13(mod 10), deci ultima cifr a a num arului N este 3.
Problema 10. S a se arate c a num arul 2004 + 20042+ 20043+


+ 20042003
se divide cu 2003. (Vaslui, etapa judet ean a)
Solut ie 2004 1(mod 2003), atunci 2004k1(mod 2003), adun^ and
termenii, obt inem S0(mod 2003).
Problema 11. Fiea1;a2;a3;:::;a 7 sapte numere p atrate perfecte. S a se
arate c a exist a dou a dintre ele a c aror diferent  a este multiplu de 20. (Galat i,
etapa local a)

56CAPITOLUL 3. PROBLEME REFERITOARE LA CONGRUENT E POLINOMIALE S I OBSERVAT II
Solut ie
Ultima cifr a unui p atrat perfect poate  0 ;1;4;5;9.
Conform principiului cutiei exist a am>a ncare au aceeas si ultim a cifr a.
Fieam=q2 sian=p2)10(q2p2))q  si p au aceea si paritate
)aman= 4t, de unde rezult a concluzia.
Problema 12. Fiep3 un num ar prim. S a se arate c a(
1
p)
={
1; p 1(mod 4)
1; p3(mod 4):
Solut ie:
Folosim Criteriul lui Euler 🙁
1
p)
(1)(modp):
(1)p1
2={
1; dac ap1
2= 2k
1;dac ap1
2= 2k+ 1;k2Z
(1
p)
={
1; p 1(mod 4)
1; p3(mod 4)
p1
2= 2k;rezult a c ap1 = 4k;rezult a c ap= 4k+1;rezult a c ap1( mod 4)
p1
2= 2k+1;rezult a c ap1 = 4k+2;rezult a c ap= 4k+3;rezult a c ap3( mod 4)
Problema 13. S a se rezolve congruent ele:
1.13x2(mod 10)
2.21x26(mod 8)
Solut ie:
1.
13x2(mod 10)
3x2(mod 10) j7
7
3
x7
2(mod 10)
21x14(mod 10)
1x4(mod 10)
x= 10
k+ 4

3.2. PROBLEME 57
2.
21x26(mod 8)
5x2(mod 8)
5
x
55
2(mod 8)
25x2(mod 8)
1x2(mod 8)
x= 8
k+ 2
Problema 14. Fiep3 num ar prim. S a se determine:(
3p+1
p)
.(Simbolul
lui Legendre )
Solut ie:
Folosim Mica teorem a a lui Fermat :
p prim;a2Z;(a;p) = 1
ap11(modp)
3p11(modp))3p3(modp)
3p+ 14(modp)
ab(modp))(a
p)
=(b
p)
(ab
p)
=(a
p)(b
p)
(3p+ 1
p)
=(4
p)
(4
p)
=(2
p)(2
p)
= (1)p21
8
(1)p21
8= 1
Problema 15. Fie p prim, p1(mod 4). S a se arate c a dac a a;bsunt
^ ntregi, 1 a;b(p1), astfel ^ nc^ at a+b=p, atunci ele sunt simultan
resturi sau neresturi p atratice modulo p.
Solut ie:
a+b=p)a b( modp))(a
p)
=(b
p)
=((1)
b
p)
=(1
p)(b
p)
= (1)p1
2
(b
p)
(1)

58CAPITOLUL 3. PROBLEME REFERITOARE LA CONGRUENT E POLINOMIALE S I OBSERVAT II
p1( mod 4) )p= 4k+1)p1
2=4k+ 11
2= 2k)(1)p1
2= (1)2k= 1
(2)
Din 1  si 2 rezult a c a:(a
p)
=(b
p)
:
Problema 16. Dac a 3a75(mod 11), s a se arate c a a3(mod 11):
Solut ie:
3a75(mod 11)=
4
12a720(mod 11)
a79(mod 11) )(a;11) = 1
a7
a7
a79
9
9(mod 11)
a21729(mod 11)
a213(mod 11)
a101(mod 11)
a201(mod 11)
a21=a20
a3(mod 11)
Problema 17. S a se arate c a 167 -2n+ 3m, oricare dintre numere n  si m
apart in^ and mult imii numerelor naturale.
Solut ie:
Presupunem c a exist a m sinastfel ^ nc^ at 167 j2n+ 3m.
(2
167)
= 1
(3
167)
=(167
3)
=2
3= 1
2n+ 3m0(mod 167) )3n(2m)(mod 167)
1 =(3
167)m
=(3m
167)
=(2n
167)
=(1
2n
167)
=(1
167)

(2n
167)
=(1
167)

(2
167)n
=1
Problema 18. S a se determine a2Z, pentru care n2j(n+a)na, oricare
ar  num arul natural nenul n.

3.2. PROBLEME 59
Solut ie:
n2j(n+a)na,(n+a)na0(modn2)
(n+a)n=C0
nnna0+C1
nnn1a+C2
nnn2a2+


+Cn1
nnan1+Cn
nan
(n+a)nan(modn2)
(n+a)na(modn2),ana0(modn2)
Cazul I: jaj= 1
Dac aa=1, rezult a c a ( 1)n(1)0(modn2):
Pentrun= 2)(1)2+10( mod 4) )20( mod 4):Contradict ie!!!
Pentrua= 1)1n10(modn2):
Cazul II: jaj 2
Pentrun=jaj )ajaja(moda2))a0(moda2)
a2ja, contradict ie!!!
Deci,a= 1.