capitolul 7 - divizibilitate 09.01.2013

7/25/2019 Capitolul 7 - Divizibilitate 09.01.2013

http://slidepdf.com/reader/full/capitolul-7-divizibilitate-09012013 1/57

1

7. Relaţia de divizibilitate pe mulţimea

numerelor întregi

7.1. Relaţia de divizibilitate pe mulţimeanumerelor naturale

Definiţia 7.1. Fie a şi b două numere naturale. Spunem că

a divide pe b (sau b se divide prin a ) şi scriem |a b (sauscriem b a ), dacă există u , astfel încât b au . În caz

contrar, vom spune că a nu divide pe b şi scriem |a b .

În cele ce urmează vom folosi, mai ales, notaţia |a b . În plus, dacă scriem |a b vom spune că b este multiplu de a sau că a este un divizor al lui b .

De asemenea, pentru orice a , notăm mulţimeatuturor divizorilor lui a prin

|a n n a ,

şi mulţimea tuturor multiplilor lui a cu

|a n a n .

Dintre principalele proprietăţi ale relaţiei de divizibilitateintrodusă prin definiţia 7.1. enumerăm:

P1) , 1a a şi a a .

P2) Pentru , ,a b c , dacă a b şi a c , atunci

a b c .

P3) Pentru , , , ,a b c m n , dacă a b şi a c , atunci

a bm cn .

Demonstraţie. P1). Din definiţia 7.1. avem în mod evident căa , 1 a deoarece :u a , a.î. 1a a . De



2

asemenea, a , a a deoarece : 1u , a.î. 1a a .

În concluzie, P1) este o consecinţă imediată a definiţiei 7.1.

Vom spune că 1 şi a , numărul însuşi, se numesc divizoriiimproprii ai lui a , iar restul divizorilor acestuia, dacă există,se numesc divizorii lui proprii.

P2). Din ipoteză avem

, . .

, . .

a b u a î b au

b c v a î c bv

b c au bv au au v aw

unde : 1w u v . În mod implicit, am presupus că

b c , deci şi că 1 v P3). În aceeaşi presupunere suplimentară că , , ,b c m n

sunt astfel încât bm cn , din ipoteză se obţine

, . .

, . .

a b u a î b au

a c v a î c avbm cn au m av n a um a vn aw

unde :w um vn , deci conform definiţiei 7.1. avem

a bm cn .◆

Exemplul 7.1. 5 1,5 , 6 1,2,3,6 .

Observaţia 7.1. Mulţimea divizorilor unui număr natural

a are cardinal finit, pe când mulţimea multiplilor săieste infinită (cardinalul mulţimii este egal cu cel al mulţimiinumerelor naturale).Exemplul 7.2. Mulţimea divizorilor numărului 16 este

16 1,2,4,8,16 , 16 5card ,

Mulţimea multiplilor numărului 12

16 0,16,32,48,... , 16 0card .

Observaţia 7.2. Prin definiţia 7.1., în cazul particular când0a , avem că pentru u este adevărată egalitatea



3

0 0 u , de unde rezultă că 0 0 . Mai mult, în acest caz, avem

că orice număr natural nenul x divide pe 0 deoarece,

0u , avem 0 0 x . Cu alte cuvinte, avem0 , 0 0card .

Cum din definiţia 7.1., dacă ,a b şi a b rezultă în

mod firesc că b a şi cum 0 , x , 0 fiind primulelement al mulţimii numerelor naturale1, atunci putem spunecă 0 nu este multiplul niciunui număr natural nenul. Înschimb, din 0 x u deducem că mulţimea multiplilor săi

este 0 0 , 0 1card .

Propoziţia 7.1. Relaţia binară “|” definită pe prin definiţia7.1. este o relaţie de ordine.Demonstraţie. Demonstrăm că relaţia de divizibilitate este:reflexivă, antisimetrică şi tranzitivă:

1. Reflexivă: | ,a a a . Într-adevăr, cum1 | ,a a a a a .

2. Antisimetrică: | şi |a b b a a b . Dacă |a b şi|b a , există ,u v astfel încât b au şi a bv . Dacă

0a , atunci 0 0b av v , deci 0a b . Dacă 0a ,atunci din a auv rezultă 1 uv , de unde 1u v , decia b .

3.

Tranzitivă: | şi | |a b b c a c . Dacă |a b şi |b c ,avem b au şi c bv , cu ,u v , deci c a uv , de unde

|a c .Prin propoziţia 7.1. se obţine că relaţia de divizibilitate “|”

este o relaţie de ordine definită pe mulţimea numerelornaturale, dar nu este peste tot definită. Pentru ultima afirmaţieeste suficient să arătăm că există cel puţin două numere

1 Consecinţa faptului că mulţimea numerelor naturale este bine ordonată.



4

naturale care nu sunt în relaţie de divizibilitate. De exemplu,3 nu îl divide pe 5 . ◆ Observaţia 7.3. Proprietatea P2) se poate generaliza în mod

firesc. Astfel, dacă | ia a , cu ia , 1 i n , atunci, pentru

1,..., n x x cu proprietate că1

n

i i

i

b a x

, avem

1

|n

i i

i

a a x

. Într-adevăr, fie iu astfel încât

,1i ia au i n . Din calcul direct obţinem

1 1 1

n n n

i i i i i i

i i i

a x au x a u x

,

deci1

|n

i i

i

a a x

.

Definiţia 7.2. Un număr natural 1 p se numeşte prim dacă:| | p ab p a sau | p b .

Definiţia 7.3. Un număr natural 1 p se numeşte ireductibil

( sau indecompozabil ) dacă:| 1d p d sau d p .

Un număr natural 1a care nu este indecompozabil senumeşte decompozabil (reductibil ).Lema 7.1. Fie ,a b . Atunci următoarele afirmaţii suntadevărate:

1.

Dacă |a b şi 0b , atunci 1 a b .2. Dacă | , |d a d b şi a b c , atunci |d c .

Demonstraţie.1. Fie u astfel încât b au . Cum 0b , rezultă că0a şi 0u . Fie ,c v astfel încât c a şi v u . Cum

0 c rezultă că 1 0 1 1c c a , deci 1 a . De

asemenea b au av av a a

, deci a b

.2.

Dacă 0a , atunci 0b c , deci |d c . Dacă 0a atunci 0d . Fie ,u v astfel încât ,a du b dv . Cum



5

du dv c , avem du dv şi deci u v căci 0d . Fiew astfel încât u v w . Se deduce că b c b dw , deunde c dw , deci |d c .◆ Lema 7.2. Fie a un număr natural mai mare ca 1. Putemspune că următoarele afirmaţii sunt echivalente:

1. a este decompozabil;2. există ,b c astfel încât ,1a bc b a şi

1 c a .Demonstraţie.

1. 2. Fie b un divizor, diferit de 1 şi de a al lui a . Fiec astfel încât a bc . Cum 1 b a şi 1,b b a ,rezultă că 1 b a . Cum |c a , avem 1 c a . Dacă 1c ,atunci b a iar dacă c a , atunci 1b , ambele cazuri fiindimposibile.

Rămâne adevărat că 1 c a .2. 1. Din ipotezele lui 2. rezultă că b este un divizor

diferit de 1 şi a al lui a , deci a este decompozabil. ◆ Lema 7.3. Orice număr natural 1a admite un divizorindecompozabil.

Demonstraţie. Fie 1, |d d d a . Cum a A

rezultă că A . Fie p cel mai mic număr din şi evident1 p . Dacă p este decompozabil, atunci există b astfel

încât |b p şi 1 b p . Din |b p şi | p a rezultă că |b a ,

deci b A , de unde p b . Contradicţie. Rămâne adevărat că p este indecompozabil şi lema este demonstrată.◆ Teorema 7.1. Pentru un număr natural 1 p sunt echivalenteafirmaţiile:

1. p este prim;2. p este indecompozabil.

Demonstraţie. 1. 2. Dacă p este decompozabil există ,b c astfel

încât p bc , 1 b p , 1 c p . Din egalitatea 1 p bc



6

rezultă că | p bc şi cum p este prim, avem | p b sau | p c ,deci p b sau p c . Contradicţie.

2. 1. Dacă nu orice număr idecompozabil este prim fie

p cel mai mic dintre acestea, care nu este prim. Cum p nueste prim, atunci există ,a b , astfel încât | p ab , p nudivide a şi p nu divide b . Mai mult putem alege a şi b ,astfel încât ab să fie minim. Avem 1 a p . Într-adevăr,din 0a rezultă | p a iar din 1a rezultă | p b .Contradicţie. Aşadar 1 a . Dacă a p , există ,q r

astfel încât a pq r cu r p . Cum p nu îl divide pe a , şi0 r . Din egalitatea ab pqb rb , rezultă că | p rb . Cum0 r p rezultă că p nu divide pe r . Aşadar, perechea denumere ,a b poate fi înlocuită cu perechea ,r b . Cum rb ab este contrazisă minimalitatea produsului ab . Rămâneadevărat că 1 a p şi analog se arată că 1 b p .

Fie c

, astfel încât ab pc . Avem 1c , căci, dacă1c , atunci din ,1 ,1 p ab a p b p rezultă că p este

decompozabil. Fie 1 p un divizor indecompozabil al lui c .

Cum 2 pc ab p , deducem că c p . Presupunem că 1 | p a

şi fie 1 1,c a , astfel încât 1 1c p c şi 1 1a p a . Din ab pc

se deduce 1 1a b pc . Aşadar, 1| p a b , p nu divide pe 1a (căci

p nu divide pe a ) şi 1a b ab (căci 1a a ) ceea cecontrazice minimalitatea produsului ab . Rămâne adevărat că p este prim. ◆



7

7.2. Teorema fundamentală a aritmeticii

Acceptând şi produsele cu un singur factor, avemurmătorul rezultat cunoscut sub numele de teorema

fundamentală a aritmeticii:Teorema 7.2. Orice număr natural 1a poate fi descompusîn mod unic (până la o permutare a factorilor), ca produs finitde numere prime.Demonstraţie. Presupunem că există numere naturale 1a

care nu pot fi reprezentate ca produs finit de numere prime şifie mulţimea acestora. Evident, numerele din nu sunt prime. Fie a cel mai mic număr din . Cum 1a şi a nueste prim, rezultă că a este decompozabil, deci există

,b c astfel încâta bc , cu 1 b a şi 1 c a .Deducem că b A şi c A , deci b şi c pot fi

reprezentate ca produse finite de numere prime şi atuncia bc are aceeaşi proprietate. Contradicţie. Rămâne adevăratcă orice număr natural 1a se poate reprezenta ca produsfinit de numere prime.

Fie 1a şi fie 1 2 1 2... ...n na p p p p p p două

descompuneri în factori primi ale lui a , 1, 1n n .

Deducem că 1 p divide produsul 1 2 ... n p p p şi cum 1 p este

prim rezultă că există i , 1 i n astfel încât 1 | i p p . Uzând

eventual, de o renumerotare, putem presupune că 1 1| p p .

Cum 1 p este ireductibil şi 1 1 p , rezultă că 1 1 p p , de unde

2 2... ...def

n n p p p p b

. (7.1)

Dacă 1n , atunci 1n căci altfel din 21 ...n

p p

deducem

că 2 |1 p deci 2 1 p . Contradicţie. Demonstrăm unicitatea

prin inducţie asupra lui n . Din cele de mai sus, rezultă că



8

afirmaţia este adevărată pentru numerele 1a , care admit odescompunere în 1n factori primi. Presupunem afirmaţiaadevărată pentru numerele 1b , care admit cel puţin o

descompunere în 1n factori primi. Atunci din (1) rezultă că1 1n n , deci n n şi, mai puţin ordinea factorilor,

, 2,...,i i p p i n , aşadar afirmaţia este adevărată şi pentru

numerele 1a care admit cel puţin o descompunere în n factori primi. ◆



9

7.3. Cel mai mare divizor comun

Definiţia 7.4. Fie a şi b două numere naturale. Un numărnatural d se numeşte cel mai mare divizor comun (c.m.m.d.c)al lui a şi b dacă îndeplineşte condiţiile:

D1) |d a şi |d b ;D2) dacă |c a şi |c b , atunci |c d . Notăm cel mai mare divizor comun al numerelor a şi b

cu

,a b .

Observăm că dacă, 1d satisface, de asemenea, D1) şi D2),

atunci 1d d . Într-adevăr, cum 1 |d a şi 1 |d b rezultă 1 |d d

şi analog, se arată că 1|d d . Aşadar, există ,u v astfel

încât 1d d u şi 1d dv . Dacă 0d , atunci şi 1 0d , deci,

1d d . Dacă 0d atunci din d d uv rezultă 1 uv , deci

1u v , de unde 1d d .Lema 7.4. Fie , , ,a b q r patru numere naturale astfel încât

a bq r . Atunci ,a b există, dacă şi numai dacă ,b r

există, şi avem , ,a b b r .

Demonstraţie. Presupunem că ,a b există şi fie ,d a b .

Cum |d b , rezultă că |d bq . Din |d a şi |d bq rezultă că|d r . Aşadar |d a şi |d r . Fie acum c astfel încât |c b

şi |c r , rezultă că |c a . Din |c a şi |c b rezultă că |c d .

Aşadar ,b r există şi , ,b r d a b .

Analog se arată că dacă ,b r există, atunci există şi

,a b , iar în plus , ,a b b r .◆

Teorema 7.3. Dacă , ,a b n sunt numere întregi pozitive,atunci avem



10

, ,a b a nb b .

Demonstraţie. Notăm ,d a b şi ,c a nb b . Evident

avem că din |d a şi |d b rezultă |d a nb . Cum |d b şi|d a nb , iar ,c a nb b , se obţine d c . Pe de altă

parte, avem din |c a nb şi |c b că |c a nb nb a .

Deci ,c a b , ceea ce implică c d . Din cele două

inegalităţi se obţine d c , deci rezultatul afirmat deteoremă.◆

7.4. Algoritmul lui Euclid

Demonstraţia teoremei de împărţire cu rest din mulţimeanumerelor naturale se bazează pe axioma bine ordonării amulţimii numerelor naturale. Amintim această axiomă: orice

submulţime nevidă a mulţimii numerelor naturale areun cel mai mic element.Teorema 7.4. (teorema de împărţire cu rest). Pentruoricare două numere ,a b , cu 0b , există două numerenaturale q şi r , astfel încât

a b q r ,şi 0 r b . Mai mult, q (câtul) şi r (restul) sunt unic

determinate.Demonstraţie. Fie ,a b şi 0b , arbitrar fixate.Considerăm mulţimea

y y = a - xb, x .

Demonstrăm mai întâi că . Avem două posibilităţi:1. Dacă 0a , atunci 0 0a b a , astfel că y a bx

este nenegativ pentru 0 x .2. Dacă 0a , atunci 0a . Dar cum 0b , atunci1b . De aici se obţine



11

ab a sau, echivalent,

0a ab .

Cu alte cuvinte, y a ab este un element nenegativ pentru x a , când 0a .

De aici rezultă că şi, în plus, ea admite un cel maimic element ca submulţime a mulţimii numerelor naturale.Fie r cel mai mic element al acestei submulţimi. Atunci,există x . a.î. r = a - xb . Notăm pe = q . Cu altecuvinte, există numerele întregi r şi q , a.î.

r = a -bq sau, echivalent,

a=bq+r .Pentru r şi 0r presupunem prin absurd că r b

sau, echivalent,0r b ,

de unde

0 r b a -b q+1 .

Evident, deoarece a- b q+1 este număr nenegativ şi

există x = - q+1 avem a- b q+1 prin definiţie.

Cum b este număr pozitiv, evident avem r b r . Deci, înconcluzie, avem

r - b = a - bq - b = a - b q+1 r .

Dar r este cel mai mic element al mulţimii , deciinegalitatea anterioară este o contradicţie. De aceea, în modnecesar obţinem r b . Astfel, am obţinut dubla inecuaţie0 r b pentru restul împărţirii.

Pentru demonstraţia unicităţii câtului şi restului laîmpărţirea numerelor ,a b , cu 0b , procedăm în mod

clasic: presupunem că există 1 2 1 2, , ,q q r r , a.î. să avemsimultan

1 1a bq r şi 2 2a bq r ,



12

cu

10 r b şi 20 r b .

Prin scăderea celor două reprezentări ale numărului a seobţine

1 2 1 20 b q q r r

sau

1 2 1 2b q q r r .

Demonstrăm că în mod necesar trebuie să avem 1 2q q şi

1 2r r . Dacă 1 2r r , atunci, presupunem că 1 2r r . Cum prin

ipoteză 0b , atunci trebuie să avem în mod necesar că

2 1 0q q şi, în plus, numărul 1 2r r este multiplu de b .

Dar, din inegalităţile

1 20 r r b

rezultă

1 2 0r r ,

deci, 1 2r r . Din egalitatea resturilor, avem atunci că

1 2 0b q q şi cum 0b , se obţine că şi 1 2 0q q sau

1 2q q .

Analog, se obţine acelaşi rezultat, dacă presupunem că

1 2r r . Cu aceasta, teorema este demonstrată.◆

Teorema 7.5. Oricare ar fi ,a b , c.m.m.d.c. al lui a şi b

există.Demonstraţie. Dacă |b a , atunci ,a b există şi ,a b b .

Rămâne să verificăm cazul când b nu divide pe a . Conformteoremei împărţirii cu rest, există 0 0,q r astfel încât

0 0 0, 0a bq r r b . (7.2)

Aplicând din nou teorema împărţirii cu rest, există 1 1,q r

astfel încât



13

0 1 1 1 0,b r q r r r . (7.3)

Dacă 1 0r , fie 2 2,q r astfel încât

0 1 2 2 2 1,r r q r r r . (7.4)..............................Dacă 1 0ir , fie ,i iq r astfel încât

2 1 1,i i i i i ir r q r r r . (7.5)

etc.Să observăm că lista împărţirilor succesive de mai sus

poate fi continuată atât timp cât restul împărţirii este diferit

de zero. Afirmăm că există 0n , astfel încât şi 1 0nr , deci

2 1 1, 0n n n n n nr r q r r r , (7.6)

şi

1 1 0n n nr r q . (7.7)

Într-adevăr, fie 0i i A r r mulţimea resturilor diferite de

zero din lista de împărţiri succesive de mai sus. Cum0

0r

rezultă că A .Fie nr cel mai mic număr din . Cum 0nr , există

1 1,n nq r , astfel încât

1 1 1 1,n n n n n nr r q r r r .

Cum 1nr A rezultă că 1 0nr şi afirmaţia este

adevărată. Cum | 0nr rezultă că ,0nr există şi ,0n nr r

,rezultă succesiv existenţa pentru:

1 2 1 0, , , ,..., , , ,n n n nr r r r b r a b

şi mai mult

1 0,0 , ... , ,n n n nr r r r b r a b .

Ultima egalitate este, în acelaşi timp, şi o consecinţă ateoremei 7.3.

Lista de împărţiri cu rest din demonstraţia teoremei precedente poartă numele de algoritmul lui Euclid pentru



14

aflarea celui mai mare divizor al numerelor a şi b . Ultimulrest diferit de zero din algoritmul lui Euclid pentru a şi b este chiar c.m.m.d.c al lui a şi b , i.e. , na b r .◆

Exemplu 7.3. Să se găsească 255,45 .

255 45 5 30

45 30 1 15

30 15 2

De unde obţinem 255, 45 15.

Fie c . Înmulţind egalităţile 0 , 1 ,..., , 1n n cuc se obţine lista de împărţiri din algoritmul lui Euclid pentruca şi cb , ultimul rest diferit de zero fiind ncr .

Consecinţa 7.1. Oricare ar fi numerele naturale ,a b şi c

avem , ,ca cb c a b .

Alte proprietăţi ale c.m.m.d.c. sunt date în următoarea

teoremă.Teorema 7.6. C.m.m.d.c al numerelor naturale are proprietăţile:

1. , , , , , , ,a b c a b c a b c ;

2. , 1, , 1 , 1a b a c a bc ;

3. |a bc şi , 1 |a b a c ;

4.

| , |a c b c şi , 1 |a b ab c .Demonstraţie.

1. Fie 1 2 1 3 4 3, , , , , , ,d a b d d c d b c d a d .

Trebuie să arătăm că 2 4d d . Cum 2 1|d d şi 1 1| , |d a d b ,

rezultă că 2 |d a şi 2 |d b . De asemenea, 2 |d c . Din 2 |d b şi

2 |d c rezultă că 2 3|d d . Acum din 2 |d a şi 2 3|d d rezultă

2 4|d d . Analog se arată că 4 2|d d , deci 2 4d d .2. Din ipoteze şi din 1) rezultă că



15

1 , , , ,a b a b a c a ba bc

, , ,a ba bc a bc .

3. Avem , , , , ,a c a a b c a ac bc

, , ,a ac bc a bc a .

4. Avem

, , , , ,ab c ab a b c ab ac bc

, , , ,ab ac bc a b c bc , ,ab bc b a c ba , deci |ab c .◆



16

7.5. Cel mai mic multiplu comun

Definiţia 7.5. Două numere naturale ,a b astfel încât

, 1a b se numesc relativ prime sau prime între ele.

Proprietăţile 2.,3. şi 4. din teorema precedentă pot fireformulate, folosind această noţiune. Astfel, 3. poate fienunţat astfel: dacă a divide un produs de două numerenaturale şi este relativ prim cu unul din factori, atunci a

divide celălalt factor.Observaţia 7.4. Fie 1 2, ,..., n p p p numere prime distincte şi

1 2, ,..., ne e e numere naturale mai mari sau egale cu 0. Fie1 2

1 2 ... nee e

na p p p . Din teorema fundamentală a aritmeticii

rezultă că un număr natural c este divizor al lui a , dacă şinumai dacă 1 2

1 2 ... nuu u

nc p p p cu ,1i iu e i u . În particular

rezultă că numărul divizorilor lui a este 1

1n

i

i

e

. Pe

această bază poate fi dată o nouă demonstraţie pentruexistenţa c.m.m.d.c al două numere naturale ,a b , precum şi o

nouă metodă de calcul al lui ,a b . Într-adevăr, există

numerele prime distincte 1 2, ,..., n p p p şi numerele naturale

, ,1i ie f i n

astfel încât1 2 1 21 2 1 2... , ...n ne f e e f f

n na p p p b p p p .

Fie min , ,1i i ie f i n şi 1 21 2 ... n

nd p p p .

Evident |d a şi |d b iar dacă |c a şi |c b , atunci1 2

1 2 ... nuu u

nc p p p cu

min , ,1i i i iu e f i n , deci |c d . Aşadar, ,a b

există şi ,a b d .



17

Definiţia 7.6. Un număr natural m se numeşte cel mai mic

multiplu comun (c.m.m.m.c.) al lui a şi b şi se notează cu

,a b , dacă sunt îndeplinite următoarele proprietăţi

M1) | , |a m b m ;M2) dacă |a c şi |b c , atunci |m c .

Dacă max , ,1i i ie f i n , atunci o verificare

imediată arată că 1 21 2 ... n

nm p p p este c.m.m.m.c al lui a şi

b . Se notează cu ,a b c.m.m.m.c al lui a şi b . Cum

min , max , ,1i i i i i ie f e f e f i n ,rezultă că

1 1 1

, , i i i i

n n n

i i i

i i i

a b a b p p p

1 1 1

i i i i

n n ne f e f

i i i

i i i

p p p ab

.

Deci obţinem următoarea proprietate , , , ,a b a b ab a b . (7.8)



18

7.6. Divizibilitatea în

Divizibilitatea în , este o extindere firească a relaţiei dedivizibilitate definită în . De altfel, aceasta derivă dinmodul în care, pornindu-se de la mulţimea numerelor naturale , se construieşte inelul al numerelor întregi

..., ,..., 2, 1, 0,1, 2,..., ,...n n ,

prin completarea mulţimii numerelor naturale cu simetriceleelementelor sale faţă de adunare, ca lege de compoziţieinternă2.Definiţia 7.7. Fie ,a b . Spunem că a este mai mic sau egal ca b şi scriem a b dacă b a .

Evident, relaţia binară introdusă prin definiţia 7.7. este orelaţie de ordine peste tot definită pe mulţimea numerelorîntregi . Mai mult, această relaţie de ordine este prelungireafirească a relaţiei de ordine de pe la şi ea estecompatibilă cu structura algebrică de inel a acesteia. Deci,avem:

,a b a c b c c şi

, , 0a b ac bc c c .

Dacă a atunci notăm cu a modulul lui a , definit

prin , dacă 0

0, dacă 0

, dacă 0

a a

a a

a a

şi avem următoarele proprietăţi de compatibilitate ale relaţieide ordine cu operaţiile de adunare şi înmulţire extinse lamulţimea numerelor întregi

2 ,+ este grup abelian.



19

a b a b , ,a b (inegalitatea triunghiului),

, ,ab a b a b .

Cu aceste precizări, relaţia de divizibilitate a numerelorîntregi se poate introduce sub aceeaşi formă de produs denumere întregi, ca o extindere firească a relaţiei dedivizibilitate de pe mulţimea numerelor naturale.Definiţia 7.8. Fie ,a b . Spunem că a divide pe b , şiscriem |a b , dacă există u astfel încât b au .

Deşi relaţia de divizibilitate pe este antisimetrică,

extinderea ei la prin definiţia 7.8. nu mai păstrează această proprietate. Mai precis, dacă |a b şi |b a , unde ,a b ,atunci a b . Spunem, în acest caz, că a este asociat îndivizibilitate cu b şi scriem a b .

Acest fapt impune unele ajustări ale conceptelordivizibilităţii când se trece de la la , pe care le precizam prin definiţiile de mai jos.

Definiţia 7.9. Un număr p , 1 p , se numeşte prim,dacă din | p ab rezultă în mod necesar că | p a sau | p b .

Definiţia 7.10. Un număr p , 1 p , se numeşte

indecompozabil (ireductibil ), dacă din |d p rezultă în modnecesar că 1d sau d p .

Folosind rezultatul similar de la numere naturale, se arată

imediat că un număr întreg p este prim dacă şi numai dacăeste ireductibil. Să mai observăm că un număr întreg p este prim, dacă şi numai dacă p este prim. Din teorema dedescompunere a unui număr în mod unic ca produs finit denumere prime, rezultă imediat că orice număr întreg a ,

1a , se descompune în produs finit de numere prime, unic

determinate mai puţin ordinea şi o asociere în divizibilitate.



20

7.7. Congruenţe

Fie 0m un număr întreg. Aplicând proprietăţileadunării numerelor naturale, se deduce că oricare ar fi a ,există ,q r unic determinate, astfel încât

, 0a mq r r m .Pentru numărul r , din relaţia precedentă, vom folosi şi

notaţia moda m , care se numeşte redusul lui a modulo m .

Astfel, dacă 6m , atunci

5 17 mod 6 , 2 16 mod 6 ,

0 24 mod 6 ,

3 3 mod 6

pentru că avem respectiv17 6 2 5 ,

16 6 3 2 ,

24 6 4 0 ,3 6 0 3 .

Definiţia 7.11. Fie ,a b . Ca şi în cazul numerelornaturale, un număr întreg d se numeşte c.m.m.d.c al lui a şib dacă sunt îndeplinite următoarele proprietăţi:

D1) |d a şi |d b D2) dacă |c a şi |c b atunci |c d .Deoarece relaţia de divizibilitate pe nu este

antisimetrică, c.m.m.d.c. al lui a şi b nu mai este unicdeterminat. Mai precis, d este c.m.m.d.c al lui a şi b , dacăşi numai dacă d este c.m.m.d.c. al lui a şi b , cu condiţiaca 0d , atunci c.m.m.d.c al lui a şi b este unic determinat

şi notăm ,d a b .



21

Existenţa c.m.m.d.c al lui a şi b se deduce imediat dinrezultatul similar de la numere naturale, iar calculul său se poate face cu algoritmul lui Euclid.

Să observăm că , , , , , ,a b a b a b a b a b .

Putem da o demonstraţie directă pentru existenţac.m.m.d.c a două numere întregi. Se obţine totodată o proprietate suplimentară foarte importantă pentru cele ceurmează.Teorema 7.7. Fie ,a b . Atunci c.m.m.d.c al lui a şi b

există. Mai mult, dacă ,d a b , atunci există ,h k ,

astfel încât d ah bk .Demonstraţie. Dacă 0a b , atunci 0d şi0 0 0h k unde h şi k pot fi luaţi arbitrar din .Presupunem că 0a sau 0b . Fie B mulţimea tuturornumerelor de forma ax by cu , x y , i.e.

, B ax by x y .Evident, dacă z B , z ax by , atunci

a x b y B , şi cum ,a b B , rezultă că B

conţine numere strict pozitive. Fie 0 A z B z şi

d ah bk cel mai mic număr din . Este suficient săarătăm că d este c.m.m.d.c al lui a şi b . Evident condiţia

D2) este satisfăcută. Rămâne să mai arătăm că |d a şi |d b .Dacă d nu divide pe a atunci există ,q r astfel încât

, 0a dq r r d ,deci

0 r a dq a ah bk q

1a hq b kq A B

ceea ce contrazice alegerea lui d . Rămâne adevărat că |d a şi analog se arată că |d b .◆



22

Observaţia 7.5. C.m.m.d.c. al numerelor din are proprietăţile demonstrate pentru numere naturale. Pentru o parte dintre ele, dăm o demonstraţie nouă, bazată pe

observaţia că din egalitatea 1ah bk rezultă , 1a b .Teorema 7.8. Fie , ,a b c . Avem:

1. dacă , 1a b şi , 1a c , atunci , 1a bc ;

2. dacă , 1a b şi |a bc , atunci |a c ;

3. dacă , 1, |a b a c şi |b c , atunci |ab c .

Demonstraţie.1. Fie , , ,h k u v , astfel încât 1 ah bk , 1 au cv .atunci

1 ah bk au cv a h bku bc kv , de unde

, 1a bc .

2. Fie ,h k , astfel încât 1ah bk . Atunci

c a hc bc k . Cum |a a şi |a bc rezultă că |a c .3. Fie ,h k , astfel încât 1ah bk . Atunci

c ac h bc k . Cum |a c şi |b c , atunci |ab bc şi |ab ac ,deci |ab c .◆

Consecinţa 7.2. Fie 1 2, , ,..., na b b b . Avem:

1. dacă , 1,1ia b i n , atunci 1 2, ... 1na b b b ;

2.

dacă , 1i jb b , oricare ar fi i j şi | 1ib a i n ,atunci 1 2... |nb b b a .

Demonstraţie. Inducţie după n .◆ Definiţia 7.12. Orice ecuaţie algebrică sau nu, cu mai multevariabile independente, pentru care se caută soluţiile ei înmulţimea numerelor întregi, se numeşte ecuaţie diofantică.

De exemplu, se numeşte ecuaţie diofantică liniară oriceecuaţie polinomială de gradul întâi cu un număr de două



23

variabile ax by c , ai căror coeficienţi sunt numere întregi,, ,a b c , şi pentru care se caută soluţiile ei întregi3.

În particular, ecuaţia diofantică liniară cu douănecunoscute este strâns legată de problema divizibilităţii înmulţimea numerelor întregi. Astfel, dacă interpretămtermenul liber al ecuaţiei diofantice liniare ca fiind chiar celmai mic divizor comun al numerelor ,a b , i.e. ,d a b

şi scriem ax by d , atunci din algoritmul lui Euclid şiteorema 7.7. se obţine ca o consecinţă lema lui Bézout

cunoscută şi ca identitatea lui Bézout.Lema 7.5. (Lema lui Bézout). Fie *,a b două numere

întregi nenule. Dacă ,d a b , atunci există *, x y , astfel

încât d ax by . Mai mult, avemi) d este cel mai mic număr întreg care poate fi scris sub

forma de combinaţie liniară ax by , unde *, x y senumesc coeficienţii lui Bézout;

ii) odată ce o pereche de coeficienţi Bézout x şi y a fostdeterminată, oricare altă pereche de astfel de coeficienţi secalculează cu ajutorul următoarei formulei

, ,

, ,

kb ka x x y y k

a b a b ,

ii) oricare altă combinaţie liniară a numerelor *,a b ,

i.e. aX bY , cu *, X Y , care nu sunt coeficienţii luiBézout, este un multiplu al lui d ;Exemplul 7.4. Pentru 6a şi 21b avem următoarele:

3 Prin ecuaţie diofantică se înţelege orice tip de ecuaţie algebrică sautranscendentă cu un număr arbitrar de variabile din mulţimea numerelor întregi și pentru care se caută soluţia(iile) sale întrgi. Dintre cele mai cunoscute ecuaţiidiofantice amintim, ecuaţia lui Pell, ecuaţia Ramanujan-Nagell. Din câte secunoaşte până în prezent, matematicianul grec Diophantus din Alexandria a fost primul care a studiat astfel de ecuaţii, în secolul al III-lea (D.H.). Studiilematematice ale problemelor de tip diofantic sunt denumite analiză diofantică.



24

6 10 21 3 3

6 3 21 1 3

6 4 21 1 36 11 21 3 3

În continuare, alegem un număr întreg 0m pe care-lconsiderăm fixat şi în raport cu care vom introduce conceptulde congruenţă modulo m .

Definiţia 7.13. Dacă ,a b , atunci spunem că a estecongruent cu b modulo m , şi scriem moda b m , dacă

a b se divide prin m .Deci

mod |def

a b m m a b .

Dacă a nu este congruent cu b modulo m , atunci scriem

a modb m . Numărul m se numeşte modulul congruenţei.Să observăm că moda b m , dacă şi numai dacă a şi

b dau acelaşi rest prin împărţirea cu m .

mod mod moda b m a m b m .

Se deduce că, congruenţa modulo m este o relaţie binară pe , reflexivă, simetrică şi tranzitivă, deci

mod ,a a m a

mod moda b m b a m

moda b m şi mod modb c m a c m .

Teorema 7.9. În această teoremă descriem legătura dintrecongruenţa modulo m şi operaţiile de adunare şi înmulţire pemulţimea numerelor întregi.

1.

Dacă moda b m şi modc d m , atunci moda c b d m şi modac bd m .



25

2. Dacă modac bc m şi , 1c m , atunci

moda b m .

Demonstraţie.1. Din ipoteze rezultă că |m a b şi |m c d . Există deci

,h k astfel încât a b mh şi c d mk . Rezultă că

,a c b d m h k ac bd m hd kb mhk ,

deci moda c b d m şi modac bd m .

2. Fie q astfel încât ac bc mq . Din a b c mq

rezultă că |m a b c şi cum , 1m c , rezultă că |m a b ,

deci moda b m .◆

Consecinţa 7.3. Dacă moda b m , atunci avem

modn na b m , oricare ar fi 1n .

Exemplul 7.5. Pentru orice 22, 2 1 7 mod10t t , adică

numerele lui Fermat, 22 1t t F au în reprezentarea zecimală

cifra unităţilor egală cu 7, pentru orice 2t .Într-adevăr, cum 1 1 mod10 , este suficient să arătăm

că 22 6 mod10t , oricare ar fi 2t .

Dacă 2t , atunci 2 42 2 16t şi 16 6 mod10 , deci,

afirmaţia este adevărată pentru 2t . Presupunem că 22 6 mod10t . Din consecinţa 4.7 rezultă că

22 22 6 mod10t , deci 2 12 36 mod10t . Cum

36 6 mod10 rezultă că 2 12 6 mod10t şi afirmaţia este

astfel demonstrată prin inducţie.



26

Lema 7.6. Fie *, im a , 1,i n , cu proprietatea că m este

relativ prim cu oricare ia , i.e. , 1im a , 1,i n . Atunci

m este relativ prim şi cu produsul 1 2 11

:n

n n i

i

b a a a a a

.

Demonstraţie. Presupunem prin absurd că m este relativ prim şi cu b , deci dacă avem , 1m b . Din această

presupunere rezultă că există cel puţin un divizor propriucomun al celor două numere, deci există cel puţin un divizor

comun propriu număr prim. Fie acesta 1 p , cu | p m şi| p b . Deoarece p este număr prim şi din faptul că

1

| |n

i

i

p b p a

rezultă că există 1 k n astfel încât | k p a .

De aici, se obţine că , 1k p a p , deci contradicţie cu

, 1k p a din ipoteză. În concluzie, avem că , 1m b .◆

Lema 7.7. Fie *, im a , 1,i n , cu proprietatea că m estemultiplu pentru oricare ia , i.e. im a , 1,i n . Atunci

m este multiplu şi pentru cel mai mic multiplu comun alnumerelor ia , i.e. pentru 1 2, , , :na a a b .

Demonstraţie. Teorema împărţirii cu rest aplicată pentru m şi b : ! ,q r , a.î.

m q b r , 0 r b .Cum din ipoteză avem că pentru oricare 1,i n , |ia m şi

|ia b , rezultă din proprietăţile de divizibilitate că în mod

necesar |ia r , 1,i n . De aici se obţine că r este multiplu

comun al numerelor 1 2, , , na a a şi, în plus,

1 2, , ,

nr b a a a

. Din definiţia multiplului comun, ultimainegalitate nu se poate realiza decât dacă 0r . De aici se



27

avem că 1 2 1, , ,n nm q b q a a a a , i.e.

1 2 1, , ,n nm a a a a .◆

Lema 7.8. Fie numerele *ia , 1,i n , cu proprietatea că

sunt relativ prime oricare două câte două, i.e. , 1 j ia a ,

j i , , 1, j i n . Atunci cel mai mare multiplu comun al

numerelor 1 2, , , na a a este egal cu produsul lor, i.e.

1 2 1

1

, , ,n

n n i

i

a a a a a

. (7.9)

Demonstraţie. Folosim inducţia matematică după 2n pentru a demonstra proprietatea afirmată de lema 7.8.

Pentru 2n , (7.9) este adevărată prin (7.8)

1 2 1 2 1 2, , ,a a a a a a ,

care este proprietatea de legătură dintre c.m.m.d.c. şic.m.m.m.c. pentru două numere întregi. Deci, pentru 2n

este adevărată proprietatea: *1 2,a a , cu 1 2, 1a a ,

1 2 1 2, ,a a a a .

Presupunem că proprietatea este adevărată pentru un

2n arbitrar fixat, i.e. pentru *ia , 1,i n , cu

, 1 j ia a , i , , 1,i n , avem

1 2 11

, , , ,n

n n i

i

a a a a a

.

Trebuie să demonstrăm că (7.9) rămâne adevărată şi în

cazul a 1n numere. Fie *ia , 1, 1i n , cu , 1 j ia a ,

j i , , 1, 1 j i n . Atunci, evident, avem următoarele relaţiiadevărate din ipoteza de inducţie şi din verificarea ei:

1, 1, 1,n ia a i n



28

(PM)

1 1 1 2 11

, 1 , , , , , 1n

n i n n n

i

a a a a a a a

de unde rezultă 1 1 1 2 1 1

1 1

, , , , , ,n n

i n i n n n n

i i

a a a a a a a a a

,

iar prin lema 7.7.

1

1 2 1 11

, , , , ,n

i n n n

i

a a a a a a

1 2 1 1, , , , ,n n na a a a a

.◆

Exemplul 7.6. Cel mai mic multiplu al numerelor 6 , 25 şi7 este 6, 25,7 6 7 25 1050 .◆

Teorema 7.10. (Teorema chinezească a resturilor). Fie

numerele *im , 1,i n , cu proprietatea că sunt relativ

prime oricare două câte două, i.e. , 1 j im m , j i ,

, 1, j i n . Atunci, pentru oricare numere întregi *ia ,1,i n , sistemul de congruenţe

mod , 1,i i x a m i n ,

are o soluţie unică modulo 1 2: nm m m m .

Demonstraţie. Pentru oricare 1 k n , notăm produsul

numerelor *

i

m , 1,i n , din care omitem factorulk

m ,

prin k p , i.e.

1 1 11,

n

k i k k n

ii k

p m m m m m

.

Din lema 7.5., avem că , 1k k p m , pentru oricare

1 k n , de unde rezultă că există k s şi k t astfel încât

1k k k k s p t m ,iar în termeni de congruenţă relaţia se rescrie



29

1 modk k k s p m .

Fie numărul

1 1 1 2 2 2 n n n x a p s a p s a p s . (7.10)Cum |

k jm p , pentru j k , atunci 0 mod j j j k a p s m , de

unde se obţine

1 modk k k k k k x a p s a a m .

Din această ultimă relaţie rezultă că este o soluţie asistemului de congruenţe şi, în plus, (7.10) dă o reprezentarea acestei soluţii.

Pentru a demonstra unicitatea soluţiei sistemului decongruenţe, presupunem că acesta ar avea două soluţii. Fieacestea x şi y , i.e.

mod si mod , 1,i i i i x a m y a m i n .

Atunci, avem

0 mod , 1,i x y m i n , sau |im x y , 1,i n ,

de unde rezultă şi cel mai mic divizor comun 1, , nm m divide diferenţa soluţiilor sistemului de congruenţe, i.e.

1, , |nm m x y .

Cum , 1 j im m , j i , , 1,i n , din lema 7.8. rezultă

că

1 |nm m x y ,

ceea ce este echivalent cu

1mod n x y m m .

Cu alte cuvinte, rezultatul teoremei este că soluţiasistemului de congruenţe este unică modulo produsul

1 nm m .◆

Teorema 7.11. Fie sistemul de congruenţe

1 1

2 2

mod ,mod .

x a m

x a m



30

Atunci avem:

1. Dacă 1 2, |m m 1 2a a , atunci sistemul de congruenţe

nu are soluţii.2. Dacă 1 2 1 2, |m m a a , atunci sistemul de congruenţe

are o soluţie unică modulo 1 2,m m .

Demonstraţie. Caz particular al teoremei 7.10. ◆



31

7.8. Teorema lui Euler

Definiţia 7.14. Fie 0m . Mulţimea de numere întregi 0 1 1, ,..., ma a a se numeşte sistem complet de resturi modulo

m dacă ia modia m oricare ar fi i j . Evident, mulţimea

de numere întregi

0,1,2,..., 1m m ,

este un sistem complet de resturi modulo m .De asemenea, 24, 11,20,3,10, 43 este un sistem

complet de resturi modulo 6.

Într-adevăr, cum a mod6b , dacă şi numai dacă

mod 6 mod 6a b , este suficient să arătăm că resturile

numerelor 24 , 11 , 20, 3, 10 , 43 prin înmulţirea cu 6

sunt distincte, ceea ce este adevărat, căci 24 6 4 0, 11 6 2 1, 43 6 8 5

20 6 3 3, 3 6 0 3, 10 6 1 4.

Teorema 7.12. Fie 0 1 1, ,..., ma a a un sistem complet de

resturi modulo m . Dacă ,a b şi , 1a m , atunci

0 1 1, ,..., maa b aa b aa b este un sistem complet de

resturi modulo m .Demonstraţie. Fie i j . Atunci ia modia m . Dacă

modi jaa b aa b m , atunci | i jm a a a . Cum

, 1m a rezultă că | i jm a a , deci modi ia a m .

Contradicţie.Fie 0m şi 0,1,2,..., 1m m . Să notăm cu m

cardinalul mulţimii

/ , 1mr r m .◆



32

Definiţia 7.15. Numărul m se numeşte indicatorul lui

Euler al numărului m .

Exemplul 7.7. Dacă 9m , atunci 9 / ,9 1 1, 2, 4,5,7,8r r .

Deci 9 6 . Dacă m p , unde p este prim şi 1e ,

atunci

1 11e e e e

p p p p p

.

Într-adevăr, dacă , 1er p d , atunci | ed p , deci

,1ed p s e . Deducem că , 1er p , dacă şi numai dacă

p nu divide pe r . Cum dintre numerele , 0 er r p , sedivid prin p numerele

2 20, , 2 , ..., , ... , e p p p pp ,

care sunt în număr de

1e

p

, rezultă că 1e e e

p p p

.◆

Teorema 7.13. Fie m şi n două numere întregi pozitiveastfel încât , 1m n . Atunci mn m n .

Demonstraţie. Fie a astfel încât 0 a mn . Din proprietăţile c.m.m.d.c al numerelor naturale, punctul 2rezultă că

, 1 , 1a mn a m şi , 1a n .

Numerele a cu proprietatea 0 a mn pot fi dispuse camai jos într-un tablou cu n linii şi m coloane.

0 1 ... ... 1

1 ... ... 1

2 2 1 ... 2 ... 2 1

.... ........... .............. ......................

1 1 ... 1 .... 1 1

r m

m m m r m m

m m m r m m

n m n m n m r n m m



33

Fie r , astfel încât 0 r m . Un număr arbitrar dincoloana lui r este de forma km r cu 0 k n . Aplicândlema 1 din calculul c.m.m.d.c., avem

, , , 0km r m r m k n .

Aşadar, dacă , 1r m , atunci toată coloana lui r este

formată cu numere prime cu m . Fie funcţia liniară

f x xm r . Cum , 1m n şi 0,1,..., 1n este un

sistem complet de resturi modulo n , rezultă că

0 , 1 ,..., 1 mod , 0 f f n n k n şi fiek

q astfel

încât , 0k k f k nq r k n .

Cum

, , , 0k k n r n k n ,

şi

0 1 1, ,..., 0,1,..., 1nr r r n .

Rezultă că mulţimea 0 , 1 ,..., 1 f f f n conţine n numere prime cu n . Dar 0 , 1 ,..., 1 f f f n sunt

numerele din coloana lui r . Aşadar, în fiecare coloană sunt

n numere prime cu n . Afirmaţia din enunţul teoremei

rezultă din faptul că tabloul considerat conţine m coloane

de numere prime cu m , deci m n numere prime cu m

şi n .◆ Consecinţa 7.4. Fie 1 2, ,..., nm m m numere întregi pozitive

astfel încât , 1i jm m pentru i j . Atunci,

1 2 1 2, ,..., ...n nm m m m m m .

Demonstraţie. Inducţie după n .◆

Consecinţa 7.5. Fie m un număr întreg pozitiv şi1 2, ,..., n p p p divizorii primi distincţi ai lui m . Atunci



34

|1 2

1 1 1 11 1 ... 1 1

p mn

m m m p p p p

.

Demonstraţie. Fie 1,1ie i n astfel încât1 2

1 2 ... nee e

nm p p p . Evident , 1 ji ee

i j p p pentru i j , de unde

1 21 2 ... nee e

nm p p p

1 1 2 2 11 11 2 ... n ne ee e e e

n p p p p p p

1 2

1 2 1 2

1 1 1... 1 1 ... 1nee e

nn

p p p p p p

.

|

11

p m

m p

◆

Exemplul 7.8. Dacă 600m , atunci 3 22 3 5m , deci

1 1 1

600 600 1 1 1 1602 3 5

.



35

7.9. Teorema lui Fermat

Teorema 7.14. (Euler). Fie 0m şi a astfel încât , 1a m . Atunci 1 modm

a m .

Demonstraţie. Fie t m şi 1 2, ,..., t r r r numerele din m

prime cu m . Definim mod ,1i ir ar m i t şi fie iq

astfel încât ,1i i iar mq r i t . Din , 1a m şi , 1ir m

rezultă , 1iar m . Aşadar, 1 , , , ,1i i i iar m mq r m r m i t

de unde

1 2 1 2, ,..., , ,...,t t r r r r r r .

Dacă pentru i j avem i jr r , atunci

modi jar ar m , deci | i jm a r r şi cum , 1m a rezultă că | i jm r r . Contradicţie. Rămâne adevărat că

i jr r pentru i j , deci 1 2 1 2, ,..., , ,...,t t r r r r r r şi în

particular 1 2 1 2... ...t t r r r r r r .

Din mod ,1i iar r m i t , rezultă că

1 1... ... modt

t t a r r r r m

deci 1 2| 1 ...t

t m a r r r .Din , 1,1im r i t rezultă că 1 2, ... 1t m r r r , deci

| 1t m a .

Aşadar, 1 modt a m , deci 1 modma m

.◆

Teorema 7.15. (Fermat). Fie 0 p un număr prim şi a

astfel încât p nu divide a . Atunci 1 1 mod pa p .



36

Demonstraţie. Cum p nu divide a rezultă că , 1a p .

Avem 1 p p şi din teorema lui Euler deducem că

1 1 mod pa p .◆ Exemplul 7.9. Să se afle restul împărţirii prin 15 alnumărului 227139a .

Cum 139 15 9 4 , avem 139 4 mod15 , deci

227 227139 4 mod15 .

Dar 4,15 1 şi 1 1

15 15 1 1 83 5

şi folosind

teorema lui Euler rezultă că 84 1 mod15 .

Avem 227 8 28 3 , deci

8228 8 3 34 4 4 4 mod15 64 mod15 4 mod15 .

Aşadar, restul împărţirii prin 15 al numărului 227139 este

egal cu 4.



37

7.10. Stabilirea criteriilor de divizibilitate

Definiţia 7.16. Fie m un număr natural pozitiv. Dacă a ,atunci există ,q r astfel încât , 0ia mq r r m . Mai

putem scrie 1a m q r m . Se observă că cel puţin unul

dintre numerele r şi m r are valoarea absolută mai mică

sau egală cu2

m. Un asemenea numărul poartă numele de cel

mai mic rest în valoare absolută al lui a modulo m . Fie m un număr natural scris în baza 10

11 1 010 10 ... 10n n

n na a a a a .

Fie k r cel mai mic rest în valoarea absolută a lui 10k

modulo , 0,1,...,m k n şi

1 1 1 1 0 0...m n n n nT a r a r a r a r .

Cum 10 mod , 0,1,...,k

k r m k n rezultă că 1 0 1 1 0 010 ... 10 ... modn

n n na a a a r a r a r m

deci modma T m .

Teorema 7.16. Cu notaţiile de mai sus avem:1. Numerele a şi mT dau acelaşi rest prin împărţirea la

numărul natural m ;

2. Numărul a se divide prin m dacă şi numai dacă mT sedivide prin m .Demonstraţie. Presupunem că 3m . Avem 10 1 mod3

şi deci 10 1 mod3 , 1, 2,...k k . Aşadar, 1, 0,1,2,...k r k

deci 3 0 1 ... nT a a a .

Deducem că a se divide prin 3 dacă şi numai dacă suma

cifrelor lui a din scrierea zecimală se divide prin 3.



38

Presupunem că 9m . Cum 10 1 mod9 , 0,1, 2,...k k ,

deducem că 9 0 1 ... nT a a a . Aşadar a se divide prin 9

dacă şi numai dacă suma cifrelor lui a din scrierea zecimalăse divide prin 9.Presupunem că 11m . Cum 10 1 mod11 , rezultă că

10 1 mod11 , 0,1,2,...k k k , deci

11 0 2 4 1 3 5... ...T a a a a a a .

Dacă 8194956a , atunci

11 6 9 9 8 5 4 1 31 10 22T .Cum 22 se divide prin 11, deducem că 8194956 se divide

prin 11.Dacă 130619a , atunci

11 9 6 3 1 0 1 18 2 16T . Cum restul

împărţirii lui 16 prin 11 este 5, deducem că 130619 împărţitla 11 dă restul 5.

Presupunem că 7m . Cum 010 1 mod 7 ,

110 3 mod 7 , 210 2 mod 7 , 310 1 mod 7 ,

410 3 mod 7 , 510 2 mod 7 , 610 1 mod 7 , ...,

rezultă că

7 0 1 2 3 4 5 6 7 8 93 2 3 2 3 2 ...T a a a a a a a a a a .

Dacă 5225234a , atunci7 4 3 3 2 2 5 3 2 2 2 5 0T ,

deci a se divide cu 7. ◆ Observaţia 7.6. Fie m un număr întreg pozitiv. Dacă 2

nu divide pe m şi 5 nu divide pe m , atunci ,10 1m .

Conform teoremei lui Euler 10 1 modmm

.

Aşadar, există numere 0k astfel încât 10 1 modk

m .



39

Dacă t este cel mai mic număr întreg 0k cu proprietatea că 10 1 modk m ,

1 1 0 1010 mod , 0 , ...t

i n nr m i t a a a a a şi

0 0 1 1 0 1 1... ...m t t t t T r a r a r a r a r a ,

atunci a şi mT dau acelaşi rest prin împărţirea cu m .



40

7.11. Aplicaţii

1. Scrieţi divizorii naturali ai numerelor 18, 32 şi 90. Soluţie. 18 1,2,3,6,9,18 ,

32 1,2,4,8,16,32 ,

90 1,2,3,5,6,9,10,15,18,30,45,90 .◆

2. Care sunt divizorii numărului 96 care sunt şi multipli ainumărului 3. Soluţie. 96 1,2,3,4,6,8,12,16,24,32,48,96 , dar dinaceştia, ca multipli ai lui 3 găsim

3 3,6,12,24,48,96 ◆

3. Determinaţi mulţimile 16 18 şi 16 18

Soluţie. 16 1,2,4,8,16 ,

18 1,2,3,6,9,18

deci 16 18 1, 2 , 16 18 1,2,3,4,6,8,9,16,18 .◆

4. Enumeraţi primele cinci numere naturale care suntmultipli nenuli ai numărului 5 . Soluţie. 5 5,10,15,20,25 .◆

5. Calculaţi 4 6

Soluţie. 4 0,4,8,12,16,20,24... , 6 0,6,12,18,22,24,... , deci 4 6 12 .◆

6. Să se determine mulţimea divizorilor întregi ai lui 12. Soluţie. 12 1, 2, 3, 4, 6, 12 .◆

7. Să se determine mulţimea divizorilor proprii ai lui 36. Soluţie. 36 1,2,3,4,6,9,12,18,36 , din mulţimea

divizorilor lui 36, excludem divizorii improprii şi obţinem 36 2,3,4,6,9,12,18

proprii .◆



41

8. Care este numărul divizorilor naturali ai numărului 24? Soluţie. Descompunem numărul 24 în produse de factori primi, şi obţinem

324 2 3 ,deci

824)11()13()24( N .◆

9. Determinaţi numărul de divizori naturali ai numărului1440. Soluţie. 5 21440 2 3 5

(1440) (5 1) (2 1) (1 1) N 6 3 1 18 ◆ 10. Fiind date următoarele perechi de numere, calculaţi ,a b , ,a b iar apoi verificaţi relaţia , ,a b a b a b :

a) 192a şi 144b b) 450a şi 224b

Soluţie. a) Descompunem cele două numere în produse defactori primi

6

192 2 3

;

4 2

144 2 3

, 4192,144 2 3 48 ; 6 2192,144 2 3 576 ,

deci 48 576 27648 192 144 , de unde rezultă că relaţia demai sus, este adevărată.

b) analog punctului a). ◆ 11. Dacă , 4a b şi 192a b atunci calculaţi ,a b .

Soluţie. Folosim relaţia , ,a b a b a b , şi înlocuind cu

ceea ce ştim obţinem

192

, 4 192 , 484

a b a b .◆

12. Să se determine:a) cel mai mic număr de trei cifre divizibil cu 3 ; b) cel mai mare număr de trei cifre divizibil cu 2 şi 3 ;c) cel mai mare număr de trei cifre divizibil cu 3 şi 5 .

Soluţie.

a) 102 3 ;



42

b)996 3

996 6996 2

c) 990 3990 15990 5

◆

13. Determinaţi x , astfel încâta) 1 este divizor propriu al lui 8. b) 2 1 x este divizor impropriu al lui 27.

Soluţie. a) 8 1,2,4,8 , din această mulţime, divizori proprii

pentru 8 , sunt 8 2,4 proprii ,

deci, 1 2, 4 1,3 x x .

b) Divizorii improprii ai lui 27 sunt 27 1,27 proprii ,

deci, 2 1 1, 27 1,14 x x .◆

14. Să se arate că următoarele afirmaţii sunt adevărate pentru

orice număr natural n :c) 2 17 7 7 , 55n n n A A ;

d) 2 16 3 3 3n n n B , 5 B ;e) 1 2 215 3 5 3 5n n n n nC , C 31 ;

Soluţie. a) 2 1 27 7 7 7 7 7 7 7n n n n n n A

2

7 7 7 1 7 55 55,n n

A A n b) 2 16 3 3 3 3 54 3 1 3 50n n n n n B , de unde

rezultă 3 5 10 5,n B B n

c) 1 2 215 3 5 3 5 15 15 9 25n n n n n nC , sau

rescris 15 31 31,nC C n .◆ 15. Determinaţi numerele:

f)

de forma 53 divizibile cu 2;g) de forma 3 2 3S xx x divizibile cu 2;



43

h) de forma 3 6 divizibile cu 3;

i) de forma xyxy divizibile cu 5 şi cu suma cifrelor

egală cu 12. Soluţie.

a) 53 2 0, 2, 4,6,8 x x , de unde rezultă numerele

căutate sunt 530,532,534,536,538 .

b) 2 ultima cifră a sumei trebuie să fie parăS , dar cum3 este impar, rezultă că şi trebuie să fie impar, deci

1,3,5,7,9 x . Deci, 544,566,608,650,692S .c) 3 6 3 9 trebuie să fie multiplu de 3 x x , de unde

rezultă 0,3,6,9 x . Obţinem numerele 306,336,366,396

d) xyxy 5 0,5 y , dar cum suma cifrelor trebuie să

fie 12 , rezultă că 2( ) 12 , 1,5 ; 6,0 x y x y .

Deci, numerele astfel obţinute sunt 1515,6060

.◆

16. Enumeraţi elementele mulţimilor următoare:a) { | , 20 şi 5|(12 )} x x x x

b) { | 45 , 2} B a a x a

c) { | 45 , 3}C b b x b

d) { | 1 , 2 şi 112} D a a xy a a

Soluţie. a) 5|(12 ) 3,8,13,18, 23,28,..... x x , dar cum20 x , rezultă 3,8,13,18 A .

b) Cum 45 2 0, 2, 4,6,8a x x , deci mulţimea

450,452,454,456,458 B .

c) 45 3 3 9 0,3,6,9b x x x de unde rezultă

450,453,456,459C .



44

d) 1 2 0, 2, 4,6,8a xy y , dar 112a rezultă

0,1 x . Deci 100,102,104,106,108,110 D .◆

17. Care este probabilitatea ca înlocuind la întâmplare pe x ,numărul 3 2 să fie divizibil cu 3.

Soluţie. 3 2 3 3 5 1, 4,7 x x x , dar cifra, de unde

rezultănr. cazurilor favorabile 3

33,3%nr. cazurilor posibile 10

P .◆

18. Să se arate că oricare ar fi cifrele nenule a şi b numărul

natural 100n abbab b este divizibil cu 77 . Soluţie. Folosim scrierea numărului n în baza 10

10 000 1 000 100 10 100n a b b a b b

10 000 10 1 1 000 10010 1001a b a b

1001 10 77 13 10 77 ,a b a b n a b ◆

19. Să se demonstreze că (3 7 ) 5a b , dacă şi numai dacă

(2 3 ) 5a b , unde a şi b sunt două numere naturale. Soluţie. “ ” Dacă 5 (3 7 )a b şi 5 5 , putem scrie atunci

5 (3 7 )5 (3 7 ) (5 5 )

5 (5 5 )

a ba b a b

a b

,

de unde rezultă5 4(2 3 )

5 (2 3 ), ,

dar 5 | 4

a ba b a b

.

“ ” Dacă 5 (2 3 ) 5 4(2 3 )a b a b , şi cum 5 5 , obţinem

5 (8 12 )5 (8 12 ) (5 5 )

5 (5 5 )

a ba b a b

a b

, de unde rezultă

5 (3 7 ), ,a b a b .◆

20. Aflaţi x din ecuaţia 2 3 ... 125 31 00 x x x y ştiind că 31 00 3 y .



45

Soluţie. din relaţia 3 31 00 3 3 1 0 0 2,5 y y y ,

rezultă numerele de forma 31200 şi 31500 .

2 3 ... 125 1 2 3 ... 125125 (125 1)

78752

x x x x x

x

deci 7875 31 00 y .

Cazul I.31200

7875 312007875

x x .

Cazul II. 315007875 31500 47875

x x .◆

21. Să se arate că:a) 2 3 98 991 2 2 2 ... 2 2 X se divide cu 31. b) 2 3 1005 5 5 ... 5Y se divide cu 30.

Soluţie.

a) Căutăm o grupare convenabilă de termeni, astfel încât

suma lor să fie un multiplu de 31.Observăm că 2 3 41 2 2 2 2 31 , deci putem scrie astfel:

2 3 4 5 2 3 4

94 2 3 4

1 2 2 2 2 2 1 2 2 2 2

... 2 1 2 2 2 2

X

5 95 5 10 9531 2 31 ... 2 31 31 2 2 ... 2 X

folosind proprietatea relaţiei de divizibilitate,( dacă a b a k b ), este evident că 31 X .

b) Observăm că 25 5 5 25 30 , deci putem scrieastfel:

2 2 1 2 98 1 2

2 3 98

2 3 98

(5 5 ) 5 (5 5 ) ... 5 (5 5 )

30 30 5 30 5 ... 30 5

30 (1 5 5 ... 5 )

Y

folosind proprietatea relaţiei de divizibilitate,( dacă a b a k b ), este evident că 30Y .◆



46

22. Să se afle numărul de telefon al unui elev, ştiind că este

de forma 0720 05 5ab c se divide cu 45 , iar 2a , 0a şi b este egal cu ultima cifră plus trei. Soluţie. Cum 2, 0 1a a a , iar 5 3 8b , rezultăcă numărul va fi de forma

07201805 5 907201805 5 45

07201805 5 5

9 28 8

cc

c

c c

deci, numărul de telefon va fi 0720180585 .◆

23. Fie mulţimile:14

|1

A nn

,

2 1|

2

n B n

n

,

5 3

| 3 1

n

C n n

,Determinaţi B C . Soluţie. Determinăm elementele fiecărei mulţimi.

Dacă 14

141 14 1

1 n n

n

, de unde

rezultă 1 1, 2, 7, 14 0, 1,6,13n n . Cum n ,

obţinem mulţimea 0,1,6,13 A .

Dacă 2 1

2 2 12

nn n

n

, dar 2 2n n ,

de unde rezultă

3

2 2 12 3 2

2 2

n nn n

n n

,

deci,

2 1, 3 1, 1n n .

Cum n , obţinem mulţimea 1 B .



47

Dacă 5 3

3 1 5 33 1

nn n

n

,

dar 3 1 3 1n n , de unde rezultă

4

3 1 5 33 1 4 3 1

3 1 3 1

n nn n

n n

,

deci, 1

3 1 1, 2, 4 0, , 13

n n

.

Cum n , obţinem mulţimea 0, 1C .

Deci, obţinem 1 A B C .◆

24. Aflaţi cel mai mare divizor comun al numerelor naturale96 şi 240 . Soluţie. Descompunem în factori primi numerele

596 2 3 4240 2 3 5

4(96, 240) 2 3 48 ◆ 25. Cel mai mic multiplu comun al numerelor naturale 84 şi140 este: Soluţie. Descompunem în factori primi numerele

284 2 3 7 2140 2 5 7

2

84,140 2 3 5 7 84,140 840 ◆ 26. Aflaţi elementele mulţimii 31 4 x x .

Soluţie. Dacă 4 | 31 4 |1 2,6 2,6 x x x A ◆

27. Să se găsească cel mai mare număr de forma y x34 divizibil cu 36? Soluţie. 9436 , unde 19,4

Dacă 4 | 4 3 , 9 | 4 3 y x y şi y x34|9419,4



48

Dacă 6,23|434|4 y y y x , deci, numerele sunt

de forma 324 x şi 364 x .

Dacă 9,09|9234|9324|9 x x x x deci, numerele sunt 4032 şi 4932 .

Dacă 513|9634|9364|9 x x x x ,deci numărul este 4536 .

Cel mai mare număr dintre cele trei este 4932 .◆ 28. Numerele 273, 327 şi 359 împărţite la un acelaşi numărdau resturile 9, 15 respectiv 23. Aflaţi împărţitorul. Soluţie. Notăm numărul căutat cu a

. .

273: rest 9 273 9T I R

a x a x 273 9 264 | 264a x a x a

. .

327 : rest 15 327 15T I R

a y a y 327 15 312 | 312a y a y a

. .

359 : rest 23 359 23T I R

a z a z 359 23 336 | 336a z a z a

din

|264

| 312 (264, 312, 336)

|336

a

a a

a

.

Descompunem în factori primi cele trei numere

2432)336,312,264(

732336

1332312

1132264

3

4

3

3

şi obţinem .24a ◆ 29. Suma a două numere naturale este 135 iar . . . . .c m m d c allor este 15 . Aflaţi numerele. Soluţie. Fie a şi b cele două numere căutate.



49

Din relaţia 15

, 1515

a xa b

b y

, şi din 135a b , rezultă

15 15 135 15 135 9dar , 1

x y x y x y

x y

1 şi 8 15 şi 120

2 şi 7 30 şi 105

4 şi 5 60 şi 75

x y a b

x y a b

x y a b

.

Soluţia problemei este 15,120 ; 30,105 ; 60,75S

.◆

30. Produsul a două numere naturale este 726 iar . . . . .c m m d c al lor este 11. Aflaţi numerele. Soluţie. Fie a şi b cele două numere căutate.

Din relaţia 11

, 1111

a xa b

b y


11 11 726 121 726 6

dar , 1

x y x y x y

x y

1 şi 6 11 şi 66

2 şi 3 22 şi 33

x y a b

x y a b

.

Soluţia problemei este 11,66 ; 22,33S .◆

31. Determinaţi două numere naturale a căror sumă este 40 ,

iar . . . . .c m m d c al lor este 5 . Soluţie. Fie a şi b cele două numere căutate.

Din relaţia 5

, 55

a xa b

b y


5 5 40 5 40 8

dar , 1

x y x y x y

x y

1 şi 7 5 şi 353 şi 5 15 şi 25

x y a b

x y a b

.



50


32. Numerele 247 , 297 şi 347 împărţite la acelaşi număr

natural n dau resturile 7 , 9 şi, respectiv, 11. Determinaţi pecel mai mare şi pe cel mai mic număr natural n cu această proprietate. Soluţie. Notăm numărul necunoscut cu n .

247 : rest 7n a 297 : rest 9n b 347 : rest 11n c

Aplicăm teorema împărţirii cu rest şi obţinem:247 7; 7 240 240n a n n a n

297 9; 9 288 288n b n n b n

347 11; 11 336 336n c n n c n

din

240

288 240, 288,336

336

n

n n

n

.

Descompunem în produse de factori primi numerele240, 288 şi 336 .

Calculăm şi obţinem cel mai mare număr 42 3 48n , darobservăm că 12 3 6n , nu poate fi soluţie, de unde rezultăcă cel mai mic număr care verifică datele problemei este

22 3 12n ◆ 33. Numerele 675 , 262 şi 885 împărţite la acelaşi numărnatural dau resturile 12 , 7 respectiv 1. Aflaţi numărul la careau fost împărţite. Soluţie. Notăm numărul necunoscut cu n .

675 : rest 12n a ;262 : rest 7n b ;

885 : rest 1n c .Aplicăm teorema împărţirii cu rest şi obţinem



51

675 12; 12 663 663n a n n a n

262 7; 7 255 255n b n n b n

885 1; 1 884 884n c n n c n

din

663

255 663, 255,884

884

n

n n

n

.

Descompunem în produse de factori primi numerele

663, 255 şi 884 .Calculăm şi obţinem numărul 17n ◆ 34. Care este cel mai mic număr natural pe care dacă îlîmpărţim, pe rând, la 7,6,5 şi 4 obţinem resturile 6,5,4respectiv 3 . Soluţie. Notăm numărul cu a .

. .

: 7 rest 6 7 6T I R

a x a x . .

: 6 rest 5 6 5T I R

a y a y . .

:5 rest 4 5 4T I R

a z a z . .

: 4 rest 3 4 3T I R

a t a t 7 6 1 7 7 1 7 ( 1) 7 | 1a x a x a x a 6 5 1 6 6 1 6 ( 1) 6 | 1a y a y a y a

5 4 1 5 5 1 5 ( 1) 5 | 1a z a z a z a 4 3 1 4 4 1 4 ( 1) 4 | 1a t a t a t a

deci 1 [7,6,5, 4] 1 420a k a k Pentru 1 1 420 419k a a .◆ 35. Împărţind numerele 1880 şi 1568 la un număr natural maimare decât 300, se obţine de fiecare dată restul 8. Determinaţinumărul a . Soluţie. Notăm numărul căutat cu a



52

. .

1880 : rest 8 1880 8T I R

a x a x 1880 8 1872 |1872a x a x a

. .1568 : rest 8 1568 8

T I Ra y a y

1568 8 1560 |1560a y a y a

din|1872

(1872,1560)|1560

aa

a

.

Descompunem în factori primi numerele şi obţinem4 2

3

3

1872 2 3 13

1560 2 3 5 13

(1792,1560) 2 3 13 312

Soluţie 312.a ◆ 36. Determinaţi cel mai mic număr natural, care împărţit la 6,8, 9, dă câturi nenule şi restul 3. Soluţie. Notăm numărul cu a .

. .

: 6 rest 3 6 3 3 6 6 | 3T i R

a x a x a x a

. .

: 8 rest 3 8 3 3 8 8 | 3T i R

a y a y a y a

. .

: 9 rest 3 9 3 5 9 9 | 3T i R

a z a z a z a

din

6 | 3

8 | 3 3 [6,8,9]9 | 3

a

a a k

a

3

2

3 2

6 2 3

8 2

9 3

[6,8,9] 2 3 72

Deci 3 72 .a k Pentru 1 3 72 75.k a a ◆



53

37. Determinaţi cel mai mic număr natural mai mare decât 5 ,care, împărţit pe rând la 6,7 şi 8 , dă de fiecare dată restul 5 . Soluţie. Notăm numărul cu a .

. .

: 6 rest 5 6 5 5 6 6 | 5T i R

a x a x a x a

. .

: 7 rest 5 7 5 5 7 7 | 5T i R

a y a y a y a

. .

: 8 rest 5 8 5 5 8 8 | 5T i R

a z a z a z a

din

6 | 5

7 | 5 5 [6,7,8]

8 | 5

a

a a k

a

168732]8,7,6[

28

77

326

3

3

Deci, .1685 k a Pentru .173516816851 aak ◆ 38. Aflaţi suma a două numere, ştiind că diferenţa lor este 31şi dacă împărţim primul număr la al doilea obţinem câtul 3 şirestul 3. Soluţie. Notăm cu a şi b cele două numere căutate.

31 ba 3: ba rest 333

..

ba R I T

453423143

14

282

3133

a

b

b

bb

De, unde rezultă 45 14 59a b .◆ 39. Să se afle două numere naturale ştiind că . . . . .c m m d c al loreste 4 , iar c.m.m.m.c este 144 .



54

Soluţie. Notăm cu a şi b cele două numere căutate.Folosim relaţia , ,a b a b a b , unde vom înlocui ceea ce

ştim, şi vom obţine 4 144 576a b .Din relaţia

4, 4

4

a xa b

b y

, şi din 576a b ,

rezultă

4 4 576 16 576 36

dar , 1

x y x y x y

x y

1 şi 36 4 şi 1444 şi 9 16 şi 36

x y a b x y a b

.


40. Să se determine cel mai mic număr natural de trei cifrecare împărţit pe rând la 12, 15 şi 18 dă resturile 5, 8 şi 11. Soluţie. Notăm numărul cu a

xa 12: rest 5125

..

xa

R I T

ya 15: rest 8158

..

ya R I T

z a 18: rest 111811..

z a R I T

7|12)1(12712127 a xa xa 7|15)1(15715157 a ya ya 7|18)1(18718187 a z a z a

Deci k ak a 1807]18,15,12[7Pentru 17318071 aak .◆ 41. Un număr de trei cifre împărţit la răsturnatul său dă câtul3 şi restul 41 , iar diferenţa dintre cifra sutelor şi a unităţiloreste 5 . Să se afle numărul.

Soluţie. Fie yz numărul căutat, de unde rezultă yx

răsturnatul său.Ştim că

. . .

: 3 rest 41 3 41T I R

xyz zyx xyz zyx .



55

Calculăm diferenţa dintre număr şi răsturnatul său şiobţinem

3 41

2 41

xyz zyx zyx zyx

zyx

Cum 5 x z , efectuând din nou diferenţa obţinem

100 10 xyz zyx x y 100 10 z z y

99 99 99 99 5 495

x

x z x z

Egalând acum cele două relaţii, vom obţine

2 41 495 227 zyx zyx , deci numărul căutat va fi722 xyz .◆

42. Să se arate că numărul 10 11n N , este divizibil cu 3 ,

oricare ar fi n număr natural. Soluţie. Metoda 1.

zerouri

10 11 100...000 11 100...011n

n

N ,

deci, suma cifrelor numărului N este 3 , de unde rezultă că3 N .

Metoda 2. Îl scriem pe 210 3 3 1 1 , dar

3 31 1n

, de unde înlocuind în N , obţinem

3 31 11 1 11n

N , sau 3 312 N .◆

43. Să se afle restul împărţirii numărului 19 1717 19a la 16 .

Soluţie. Observăm că 17 1 mod16 , de unde rezultă 19 19 1917 1 mod16 17 1 mod16 deci, restul împărţirii

lui 1917 la 16 este 1.Analog pentru 17 1719 3 mod16 19 3 mod16 , dar

44 4 43 1 mod16 3 1 mod16

3 3 mod16

173 mod16 1 3 mod16 deci



56

173 mod16 3 mod16 , de unde rezultă 1719 3 mod16 ,

deci restul împărţirii lui 1719 la 16 este 3 .

Putem acum să rescriem numărul19 17

17 19a , astfel 19 1717 19 1 3 mod16 3 mod16a a , de unde vom

obţine restul împărţirii numărului a la 16 ca fiind 3.◆ 44. Să se afle restul împărţirii numărului 580222 la 73 . Soluţie. 580 580223 3 mod 73 223 3 mod 73

dar 733,73 1 3 1 mod 73 (din teorema lui Euler),

iar 7273 73 1 72 3 1 mod 73 .580 72 8 4 , de unde rezultă

872 8 576

4

3 1 mod 73 3 1 mod 73

3 8 mod 73

576 4 5803 3 1 8 mod 73 3 8 mod 73 , astfel obţinem că

580222 8 mod 73 , de rezultă că restul împărţirii numărului580222 la 73 este 8.◆

45. Să se afle restul împărţirii lui 200 2007 11a la 13 .

Soluţie. .

13 127,13 1 7 1 mod13 7 1 mod13T E

200 12 16 8 ,

deci

1612 16 192

7 1 mod13 7 1 mod13 2 87 3 mod13 7 3 mod13 , de unde rezultă

192 8 2007 7 1 3 mod13 7 3 mod13 .

Analog pentru

.

13 1211,13 1 11 1 mod13 11 1 mod13T E

deci 1612 16 192

11 1 mod13 11 1 mod13



2 811 4 mod13 11 9 mod13 , de unde rezultă

192 8 20011 11 1 9 mod13 11 9 mod13 .

Deci, acum numărul a se mai poate scrie şi 12 mod13a ,de unde rezultă că restul împărţirii este 12 .◆ 46. Să se afle suma şi numărul divizorilor numărului 180 . Soluţie. Descompunem în produse de factori primi numărul

2 2180 2 3 5 , Numărul divizorilor va fi dat de

180 2 1 2 1 1 1

3 3 2 18

N

iar suma, 2 1 2 1 1 12 1 3 1 5 1

1802 1 3 1 5 1

de unde rezultă

180 7 13 6 546 .◆

47. Să se afle toate numerele care au ca descompunere

numerele prime 3 şi 5 , şi au exact 15 divizori. Soluţie. Fie n numărul căutat. În aceste condiţii putem săscriem 3 5 x y

n .Cum 15n N , deci 1 1n x y N , de unde

rezultă

1 15 15

3 5 151 1 15

5 3 15

15 1 15

x y

Cazul I. 1 1 0 x x fals.Cazul II. 1 3 2 x x şi 1 5 4 y y , de unde

rezultă 2 43 5n Cazul III. 1 5 4 x x şi 1 3 2 y y , de unde

rezultă 4 23 5n

capitolul 7 - divizibilitate 09.01.2013

Documents