PROGRAMUL DE STUDII DE LICENT A: MATEMATIC A [628953]

UNIVERSITATEA DE VEST DIN TIMIS OARA
FACULTATEA DE MATEMATIC A S I INFORMATIC A
PROGRAMUL DE STUDII DE LICENT  A: MATEMATIC A
– INFORMATIC A
LUCRARE DE LICENT  A
COORDONATOR: ABSOLVENT: [anonimizat].Dr. Dorel Mihet  Silaghi Paul-Adrian
TIMIS OARA
2017

UNIVERSITATEA DE VEST DIN TIMIS OARA
FACULTATEA DE MATEMATIC A S I INFORMATIC A
PROGRAMUL DE STUDII DE LICENT  A: MATEMATIC A
– INFORMATIC A
TEOREMA FUNDAMENTAL A A
ARITMETICII
COORDONATOR: ABSOLVENT: [anonimizat].Dr. Dorel Mihet  Silaghi Paul-Adrian
TIMIS OARA
2017

Abstract
abstractul in limba engleza
3

Cuprins
Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1 Divizibilitate 6
1.1 Divizibilitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Cel mai mic multiplu comun 9
2.1 Cel mai mic multiplu comun . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Teorema fundamental a a aritmeticii 10
3.1 Nott iuni elementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Exemple de inele semifactoriale . . . . . . . . . . . . . . . . . . . . . . 10
4 Teorema fundamental a a aritmeticii ^ n aplicat ii 11
5 Congruent e 12
5.1 Congruent e de gradul I . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Congruent e de gradul II . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4

Introducere
Dezvoltarea istoric a a matematicii cuprinde, ^ n linii mari, trei perioade.
Perioada ^ nt^ ai dureaz a p^ an a ^ n secolul al XVII-lea; ea cuprinde ^ n esent   a geo-
metria, aritmetica  si algebra elementar a. La ^ nceput oamenii foloseau matematica
^ n probleme practice ind legat a de ocupat iile acestora.Cu timpul pe m asur a ce ne-
cesitatea de a studia mai ad^ anc  si mai sitematic determin a o trecere treptat a spre
abstractizare, aritmetica se distinge de geometrie  si de zic a, devenind o disciplin a cu
oarecare independent  a.
Perioada a doua cuprinde secolul XVII, XVIII  si XIX.Aceast a perioad a are ^ n centru
studiul mi sc arii, m arimile variabile, interdependent a ^ ntre marimi(funct iile)  si trans-
form arile geometrice.Pentru aprofundarea not iuniunilor de vitez a  si tangent a se intro-
duce derivata funct iei.
Perioada a treia o constituie matematica modern a.Matematica modern a se caracte-
rizeaz a printr-un grad ^ nalt de abstractizare  si generalitate; la baza ei st a not iunea de
element nedenit, cu ajutorul c aruia se creaz a o baz a riguroas a a matematicii clasice
 si ^ n acela si timp o generalizare a ei.
^In trecut aritmetica se mai numea  si "Regina Matematicii", dar ^ n prezent nu i se
mai recunoa ste aceast a calitate ^ n t ara noastr a. ^Intr-adev ar, ^ n afara unor not iuni
relative la numere prime  si divizibilitate, care se predau ^ n gimnaziu , ^ n liceu exist a
un singur capitol relativ la aritmetica numerelor ^ ntregi, al c arui cont inut nici nu se
cere la examenele de admitere ^ n facultate,  si c^ ateva referiri la aritmetica polinoamelor,
care sunt de fapt de natur a algebric a.
Acesta e motivul pentru care am introdus ^ n lucrare capitolul 1 cu exercit ii cu grad
mediu de dicultate, care se pot utiliza oric^ and ^ n activitatea de predare la clas a at^ at
in gimnaziu c^ at  si ^ n liceu.Exercit iile respective nu sunt originale; ele vor numai s a
demonstreze c a problemele de aritmetic a sunt necesare pentru o ^ nsu sire complet a a
metematicii ^ n gimnaziu  si ^ n liceu.
^In capitolul 2 generaliz am ceea ce ^ n aritmetica numerelor ^ ntregi se nume ste "teo-
rema fundamental a a aritmeticii" scopul s au ind de a pune ^ n evident  a  si alte domenii
de integritate(^ n afar a de domeniul Zal numerelor ^ ntregi) ^ n care funct ioneaz a o ast-
fel de teorem a. De asemenea, sunt generalizate  si discutate ^ ntreaga gam a a not iunilor
uzuale ale aritmeticii.
^In capitolul 3, teorema fundamental a a aritmeticii este aplicat a pentru a obt ine di-
verse teoreme celebre de aritmetic a.Teorema fundamental a a aritmeticii se folose ste
mai mult ^ n cazul clasic al domeniului Zal numerelor ^ ntregi dar  si ^ n alte domenii:
Z[i];Z[!]
!=1 +ip
3
2
;Z[ip
2];Z1 +ip
7
2
^In capitolul 4 reg asim generalit at i despre congruent e, legea reciprocit at ii p atratice("teorema
de aur a aritmeticii").De asemenea capitolul prezint a mai multe demonstrat ii  si aplicat ii
importante ale ei.
^In capitolul 5 avem generalit at i despre caractere, sume Gauss  si sume Jacobi care
se aplic a pentru a demonstra legea reciprocit at ii cubice.Tot aici reg asim alte aplicat ii
interesante ale sumelor Gauss si sumelor Jacobi.
5

Capitolul 1
Divizibilitate
1.1 Divizibilitate
Prin numere naturale ^ ntelegem 1 ;2; : : : ; iar prin numere ^ ntregi ne referim la numerele
naturale, num arul zero  si numerele negative 1;2;3; : : :
Denit ia 1.1.1. Spunem c a un num ar intreg aeste divizibil cu un num ar ^ ntreg b
dac a  si numai dac a exist a un num ar ^ ntreg castfel ^ nc^ at a=b
c si not am bja.
Numim bdivizor a lui a si a multiplu lui b.
Scriem b-adaca bnu divide a.
Pentru orice num ar ^ ntreg b avem 0 = 0
b, orice num ar ^ ntreg este divizor al lui
zero. Pentru orice num ar ^ ntreg aavem a=a
1, observ am c a 1 este divizor pentru
orice num ar ^ ntreg.
Presupunem c a x; y; z; sunt numere ^ ntregi astfel ^ nc^ at
xjy si yjz
.Atunci exist a t; u2Zastfel ^ nc^ at y=x
t siz=y
u. Num arul v=t
ueste num ar
^ ntreg (ca produs a dou a numere ^ ntregi). Atunci , z=x
v, obt inem xjz. Asta
demonstreaz a c a relat ia de mai sus implic a relat ia xjzcare ^ nseamn a c a divizorul
unui divizor al unui num ar ^ ntreg este divizorul acelui num ar ^ ntreg.
De aici rezult a c a relat ia de divizibilitate a numerelor ^ ntregi este tranzitiv a. Asta
^ nseamn a c a dac a xjy, atunci xjk
ypentru orice num ar ^ ntreg k.
Este u sor s a demonstr am c a divizorul a dou a numere ^ ntregi date este divizorul su-
mei  si diferent ei sale. ^In plus, dac a dja sidjb, atunci , dja
x+b
y,8x; y2Z.
De fapt, relat iile dja sidjbimplic a faptul c a exist a numerele ^ ntregi k silastfel
^ nc^ at a=k
d,b=l
d, de unde a
x+b
y= (k
x+l
y)
d si prin urmare, deoarece
k
x+l
yeste un num ar ^ ntreg, dja
x+b
y.
Oricare doua din formulele a=b
c,a=b
(c),a= (b)
(c),a= (b)
c
sunt echivalente. De asemenea oricare dou a din formulele
bja; bja;bja;bja
sunt echivalente.
6

Rezult a din denit ia relat iei bjaasta dac a 0ja, atunci a= 0. Dac a a6= 0, atunci
ecare divizor ba num arului ^ ntreg aeste diferit de 0  si , ^ n consecint  a, beste de
asemenea divizor pentru a. Prin urmare pentru un num ar ^ ntreg a,a6= 0 , divizorul
b a lui a poate  aranjat ^ n perechi ( b;b). A sadar pentru a gasi toti divizorii unui
num ar ^ ntreg, este sucient sa gasim num arul natural  si s a se adauge la ecare dintre
ei divizorul negativ a aceleia si valori absolute.
La prima vedere not iunile de divizor  si multiplu sunt intr-un fel duble. Est mult
mai usor s a g asim multiplii unui num ar ^ ntreg dec at divizorii s ai. Defapt, multii unui
num ar ^ ntreg asunt , evident, tot i ^ ntregii formei ka, unde keste un ^ ntreg arbitrat.
^In consecint  a, multiplii lui aformeaz a urm atorul  sir
: : : ;2a;a;0; a;2a; : : : ;
care tinde la innit ^ n ambele direct ii. Pe de alt a parte, pentru a g asii divizorii lui a
nu este asa simplu. Asta poate p area ciudat, dar setul de divizori este nit, iar setul
de multiplii este innit.
Dac a ajdcua; d2N, atunci da. A sadar pentru a gasi tot i divizorii pozitivi a
unui num ar ^ ntreg a, este sucient s- a dividem pe acu numerele naturale 1 ;2; : : : ; a
pe r^ and  si s a select am numerele cu coecient i ^ ntregi . Pentru ecare num ar natural a
num arul coecient ilor este nit, exist a o metod a , teoretic a m acar, pentru a g asi tot i
divizorii unui num ar ^ ntreg dat. Problema este de natur a practic a ,  si ^ ntr-adev ar
pentru unele numere naturale nu putem g asi tot i divizorii. De exemplu, nu putem
face asta pentru num arul a= 21011, care are 31 de cifre. Asta complic a prea mult
problema chiar  si pentru un program software.
Problema 1. S a se demonstreze c a pentru orice num ar natural n:
9n+18n9
se divide cu 64.
Rezolvare: FieE(n) = 9n+18n9.Avem E(0) = 0, deci 64jE(0).Presupunem
acum c a 64jE(0); n0. Atunci: E(n+ 1) = 9n+28(n+ 1)9 = 9
9n+18n17 =
9(E(n) + 8n+ 9)8n17 = 9 E(n) + 64( n1).Relat ia obi snuit a  si ipoteza 64 jE(n)
implic a deci 64jE(n+ 1).Rezult a 64jE(n), pentru orice n0, conform principiului
induct iei matematice.
Problema 2. S a se determine numerele naturale n pentru care 6 divide pe
1n+ 2n+ 3n.
7

Rezolvare: Avem 221( mod 3).Rezult a c a dac a n este par avem 2n1( mod 3)
 si 1n+ 2n+ 3n1 + 1 = 2( mod 3). Astfel ^ n acest caz 3 nu divide pe 1n+ 2n+ 3n.
Presupunem c a n este impar. Atunci n= 2k+ 1, deci 2n= (22)k
22( mod 3).
Astfel ^ n acest caz 1n+ 2n+ 3n1 + 2 = 0( mod 3)  si deci 3 divide pe 1n+ 2n+ 3n.
Este clar c a 1n+ 2n+ 3neste impar (1n si 3nsunt impare  si 2neste par), deci 2 se
divide pe 1n+ 2n+ 3n.
Rezult a, ^ n acest caz c a 2  si 3 divid pe 1n+2n+3n, deci 6 = 2
3 divide pe 1n+2n+3n.
Deci numerele naturale n care satisfac condit ia din enunt  sunt exact numerele naturale
impare.
Problema 3. S a se rezolve ^ n numere ^ ntregi ecuat ia: x33y= 2.
Rezolvare: Ecuat ia se poate scrie x33y2( mod 3). Deoarece, conform teore-
mei lui Fermat, x3x( mod 3), rezult a x2( mod 3).Astfel x= 3k+ 2, unde k
este num ar ^ ntreg. Atunci:
y=x32
3=(3k+ 2)32
3=27k3+ 56k2+ 18k+ 82
3= 9k3+ 18k2+ 6k+ 2
Astfel solut iile ecuat iei sunt:8
<
:x= 3k+ 2
y= 9k3+ 18k2+ 6k+ 2,k2Z.
Problema 4. S a se determine numerele ^ ntregi n astfel ^ nc^ at 5 n2 divide pe 7 n+8.
Rezolvare: Deoarece 5 n2  si 5 sunt prime ^ ntre ele condit ia 5 n2j7n+ 8 este
echivalent a cu 5 n2j5(7n+ 8) = 35 n+ 40. Avem35n+ 40
5n2=35n14
5n2= 7 +54
5n2
astfel condit ia noastr a este echivalent a cu 5 n2j54. Avem 54 = 3
33.Putem a sa
imediat tot i divizorii ^ ntregi ai lui 42 :
5n22f 54;27;18;9;6;3;2;1;1;1;2;3;6;9;18;27;54g
. sau
5n2f 52;25;16;7;4;1;0;1;3;5;8;11;20;29;26g
. Evident ret inem numai 5 n2f 25;0;5;20g.Deci solut iile sunt n2f 5;0;1;4g
8

Capitolul 2
Cel mai mic multiplu comun
2.1 Cel mai mic multiplu comun
9

Capitolul 3
Teorema fundamental a a aritmeticii
3.1 Nott iuni elementare
3.2 Exemple de inele semifactoriale
10

Capitolul 4
Teorema fundamental a a aritmeticii
^ n aplicat ii
11

Capitolul 5
Congruent e
5.1 Congruent e de gradul I
Fief2Z[X1; X 2; :::; X n] un polinom ^ n nnedeterminate cu coecient i ^ ntregi  si m
un num ar ^ ntreg cu , m2.
Pentru a rezolva congruent a
f(X1; X 2; : : : ; X n)0( mod m)
determin am toate sistemele ordonate ( a1; a2; : : : ; a n) dennumere ^ ntregi astfel ^ nc^ at
f(a1; a2; : : : ; a n)( mod m).Consider am inelul Zmal claselor de resturi mod m
 si not am cu fpolinomul din Zm[X1; X 2; : : : ; X n] care rezult a din fprin ^ nlocuirea
coecient ilor lui fcu clasele lor de resturi mod m, atunci rezolvarea congruent ei de
mai sus se face prin rezolvarea ecuat iei
f(x1; x2; : : : ; x n) = 0
^ nZmadic a , determin am toate sistemele ordonate ( a1;a2; : : : ; an) denelemente din
Zmpentru care f(a1;a2; : : : ; an) = 0.
E evident c a
f(a1; a2; : : : ; a n)0( mod m)() f(a1;a2; : : : ; an) = 0 :
Dac a ( a1; a2; : : : ; a n) este o solut ie a congruent ei date  si ( b1; b2; : : : ; b n) este un alt sistem
dennumere ^ ntregi astfel ^ nc^ at biai( mod m) ,8i2f1;2; : : : ; ng, atunci , ^ n Zm
avem bi= ai,8i2f1;2; : : : ; ng si deci ( b1; b2; : : : ; b n) este tot o solut ie a congruent ei
date. Solut iile ( a1; a2; : : : ; a n)  si (b1; b2; : : : ; b n) de mai sus sunt echivalente.Rezult a c a
12

num arul de solut ii ale congruent ei este defapt num arul de solut ii ale ecuat iei.
f(x1; x2; : : : ; x m)0( mod m)() f(x1; x2; : : : ; x m) = 0 :
^ nZm
Congruent a de gradul I este cea mai simpl a congruent  a.
ax+b0( mod m);
unde a; b2Z:
Propozit ia 5.1.1. Fiea; b2Z; a6= 0  sid > 0; d= (a; m)(cel mai mare divizor
comun a lui a si m ^ n Z).Atunci
a) Congruent a ax+b0( mod m)are cel put in o solut ie dac a  si numai dac a djb.
b) Dac a, bjd, congruent a ax+b0( mod m)are exact dsolut ii diferite.
Teorema 5.1.2. (Teorema chinezeasc a a resturilor) : Fie m1; m 2; : : : ; m nnu-
mere ^ ntregi pozitive astfel ^ nc^ at pentru orice i6=js a avem (mi; mj) = 1 .Atunci,
pentru orice numere ^ ntregi a1; a2; : : : ; a m, congruent ele
xa1( mod m1); xa2( mod m2); : : : ; xan( mod mn)
au o solut ie comun a. ^In plus, orice dou a asemenea solut ii sunt congruente mod m1; m 2; : : : ; m n:
Demonstrat ie. Fiem=m1m2: : : m n,8i2f1;2; : : : ; ng, eni=m
ni, astfel ^ nc^ at
ni2Z. Deoarece prin ipotez a  m1; : : : ; mi1;mi+1; : : : ; mnsunt unit at i ^ n Zm, produsul
lor nieste tot o unitate ^ n Zm, astfel ^ nc^ at ( ni; mi) = 1  si ^ n particular, exist a numere
^ ntregi ri,siastfel ^ nc^ at rimi+sini= 1.Lu am ei=sini. Atunci ei0( mod mj),8
j6=i siei1( mod mi)(deoarece ei= 1rimi).Lu am
x0=nX
i=1aiei=a1e1+a2e2+: : :+anen:
Atunci8i2f1;2; : : : ; ngavem x0aieia( mod mi), deci x0este o solut ie comun a
a congruent elor din enunt .
Presupunem acum c a x1este o alt a solut ie comun a a acetor congruent e.
Atunci x1x00( mod mi), deci mijx1x0,8i2f1;2; : : : ; ng, ceea ce implic a
m=m1m2: : : m njx1x0:Q.E.D.
13

Exemplul 5.1.1 .: Cerem s a se determine toate numerele^ ntregi xcare satisfac simultan
condit iile: x2( mod 3) ; x3( mod 5) ; x5( mod 7) :
Cu notat iile din demonstrat ia teoremei 3.1.2 avem
m1= 3; m 2= 5; m 3= 7; m=m1m2m3= 105 ; n 1= 35; n 2= 21; n 3= 15:
Deoarece
12
3 + (1)
35 = 1 ;(4)
5 + 1
21 = 1 ;(2)
7 + 1
15 = 1 ;
avem
e1=35; e2= 21; e3= 15:
Rezult a
x0=a1e1+a2e2+a3e3=70 + 63 + 75 = 68 :
Deci numerele ^ ntregi xcare satisfac condit iile cerute sunt exact cele care sunt 68(
mod 105), adic a, sunt exact toate numerele ^ ntregi de forma 68 + 105 k; k2Z.
Putem interpreta teorema 3.1.2.  si din punct de vedere algebric.
Denit ia 5.1.1. FieR1; R 2; : : : ; R ninele comutative. Atunci produsul cartezian
R1R2: : : R n^ mpreun a cu operat iile de adunare  si ^ nmult ire denite prin:
(x1; x2; : : : ; x n) + (y1; y2; : : : ; y n) = (x1+y2; x2+y2; : : : ; x n+yn);
(x1; x2; : : : ; x n)(y1; y2; : : : ; y n) = (x1y1; x2y2; : : : ; x nyn)
este evident tot un inel comutativ care se nume ste produsul direct al inelelor R1; R2; : : : ; R n.
^In mod analog, dac a G1; G2; : : : ; G nsunt grupuri, produsul cartezian G1G2: : :Gn
^ mpreun a cu operat ia
(x1; x2; : : : ; x n)(y1; y2; : : : ; y n) = (x1y1; x2y2; : : : ; x nyn)
este de asemenea un grup numit produsul direct al grupurilor G1; G2; : : : ; G n.
Remarc am c a ^ n ambele situat ii elementul unitate (elementul neutru relativ la
^ nmult ire) este
1 = (1 ;1; : : : ; 1)
(unde simbolul 1 de pe componenta i^ nseamn a elementul unitate al lui Ri,respectiv
Gi).
Lema 5.1.3. FieR siSinele comutative  si f:R!Sun morsm de inele.
Atunci, dac a u2U(R)avem f(u)2U(S) si funct ia f:U(R)!U(S)denit a prin
14

f(u) =f(u); u2U(R)este un morsm de grupuri. ^In plus, dac a feste izomorsm
de inele, atunci feste izomorsm de grupuri.
Demonstrat ie. Dac a u2U(R),9v2Ra.^ uv= 1. Atunci f(u)f(v) =f(uv) =
f(1) = 1, deci f(u)2U(R). Q.E.D.
Propozit ia 5.1.4. Fiem1; m 2; : : : ; m nnumere ^ ntregi pozitive astfel ^ nc^ at 8i6=js a
avem (mi; mj) = 1 . Atunci exist a un izomorsm de inele
Zm=Zm1Zm2: : :U(Zmn)
 si un izomorsm de grupuri
U(Zm)=U(Zm1)U(Zm2): : :U(Zmn)
unde m=m1m2: : : m n.
Demonstrat ie. Pentru ecare num ar ^ ntreg x, not am cu  xclasa de resturi a lui x
mod m;x2Zm. Clasele de resturi ale lui xmod mile not am cu fi(x) (deci fi(x)
2Zmi),8i2f1;2; : : : ; ng. Deoarece pentru x; y2Zavem xy( mod m) dac a  si
numai dac a xy( mod mi),8i2f1;2; : : : ; ng,putem deni o aplicat ie
f:Zm!Zm1Zm2: : :Zmn
prin
f(x) =
f1(x); f2(x); : : : ; f n(x)

 si, aceast a aplicat ie este injectiv a. Deoarece mult imile Zm siZm1Zm2: : :Zmnau
acela si num ar de elemente, aplicat ia injectiv a feste  si surjectiv a, deci este bijectiv a.
Clar feste un izomorsm de inele. Al doilea izomorsm rezult a din partea a doua a
lemei 3.1.5  si din observat ia evident a c a
U(R1R2: : :Rn) =U(R1)U(R2): : :U(Rn)
oricare ar  inelele comutative R1; R2; : : : ; R n. Q.E.D.
5.2 Congruent e de gradul II
O congruent  a de gradul II este de forma
ax2+bx+c0( mod m)
15

unde a; b; c sunt numere ^ ntregi  si m-a, sau , altfel spus, polinomul
aX2+bX+ c2Zm[X]
este de gradul II. Singura metod a de a rezolva aceast a congruent  a este a sarea tuturor
elementelor din Zm si ^ nlocuirea nedeterminatei Xcu aceste elemente ^ n polinomul de
mai sus. Se poate de asemenea face o discut ie complet a a congruent ei  si se poate
determina num arul de solut ii.
Congruent a ax2+bx+c0( mod m) este echivalent a cu
4ax2+ 4bx+ 4c0( mod 4 m)
deci  si cu
(2ax+b)2b24ac( mod 4 m)
Subliniem faptul c a, ^ n cazul ^ n care meste un num ar ^ ntreg impar, congruent a este
echivalent a chiar  si cu
4ax2+ 4bx+ 4c0( mod m):
^Inlocuind 4 m=m0; k=b24ac si f ac^ and substitut ia y= 2ax+b, rezult a c a,
congruent a dat a este echivalent a cu sitemul
8
<
:y2k( mod m0);
2ax+by( mod m0)
(unde, putem lua m0=mdac a meste impar). Deoarece congruent a de gradul I a fost
deja studiat a, r am^ ane s a studiem congruent ele de forma
y2k( mod m):
Pentru aceasta consider am hcel mai mare divizor comun al lui k sim^ nZ.
Atunci k=k0h sim=m1hunde ( k0; m 1) = 1. Num arul ^ ntreg hse poate pune sub
forma
h=e2r;
unde reste un num ar ^ ntreg liber de p a trate.
Diny2k( mod m) rezult a m1hjy2k0h,deci e2r=hjy2. Pentru orice num ar
prim p, vom avea
2vp(e) +vp(r) =vp(e2r)vp(y2) = 2 vp(y);
16

deoarece e2rjy2 sivp(r)2f0;1g, deoarece reste liber de p a trate. Dac a vp(r) = 1
rezult a c a 2( vp(y)vp(e))1; vp(y)vp(e)1  si ^ n nal vp(er) =vp(e) + 1vp(y):
Dac a vp(r) = 0)vp(e)vp(y) sivp(er) =vp(e)vp(y):
Am ar atat astfel c a erjydeci, ^ n congruent a dat a putem face substitut ia y=
erz.Congruent a devine
e2r2z2k0e2r( mod m1e2r)
 si este echivalent a cu
rz2k0( mod m1):
Acum e scel mai mare divizor comun al lui r sim1^ nZ. Din rz2k0( mod m1)
rezult a sjk0. Dar, deoarece ( k0; m 1) = 1, rezult a c a s= 1. Astfel ( r; m 1) = 1, deci , r
este unitate in Zm1. Aceasta implic a faptul c a exist a un d2Zcudr=1 ^ nZm1, deci
dr1( mod m1). Astfel, congruent a rz2k0( mod m1) este echivalent a cu
drz2dk0( mod m1); deci z2dk0( mod m1):
Not am dk0=k1 si observ am c a, deoarece d sik0sunt prime cu m1,  sik1este prim cu
m1. Astfel congruent a y2k( mod m) este echivalent a cu
z2k1( mod m1); unde (k1; m 1) = 1
Denit ia 5.2.1. Fiem siknumere ^ ntregi, m2. Num arul kse nume ste rest
p atratic mod mdac a:
a)(k; m) = 1
b)9z2Za.^ z2k( mod m):
Dac a not am cu "  " clasele de resturi ( mod m), denit ia se poate reformula astfel:
a)0k2U(Zm);
b)09z2Zma.^  z2=k:
Altfel spus, keste rest p atratic mod mdaca keste unitate ^ n Zm si este  si p atratul
unui element din Zm.
Observat ie: Problema congruent elor de gradul II se reduce la problema determin arii
resturilor p atratice.
Denit ia 5.2.2. Fie numerele ^ ntregi m; n2. Un num ar ^ ntreg kse nume ste rest
n-putere mod mdac a:
a)(k; m) = 1
17

b)9z2Za.^ znk( mod m):
sau, echivalent
a)0k2U(Zm);
b)09z2Zma.^  zn=k:
18

Bibliograe
[1] Autori, Titlu carte, Editura, An aparit ie.
[2] Autori, Titlu articol, Nume jurnal Num ar (An aparit ie), pag. start – pag. nal.
[3] Descriere resurs a online, URL: https://www.google.com
19