Summary Divisibility in the Set of Natural Numbers. Basic Properties

6th grade

1) exposed by Manuela Prajea, Ph.D.

* Curriculum for the Olympics Page 1

Divizibilitate în mulțimea numerelor naturale

Teorema împărţirii cu rest

Fie a, b , b≠0. Atunci există q, r astfel încât a=bq+r , cu 0 r < b.

În plus, q şi r sunt unic determinate de a şi b.

Reciproc, dacă a, b , b≠0 si q, r astfel încât a=bq+r, cu 0 r < b, atunci q,r sunt câtul

respectiv restul împartirii lui a la b.

Definiţii: Fie a, b .

Spunem că a divide b dacă există c astfel încât b=ac („a divide b” se va nota ab sau b a)

Spunem că numărul natural d este cel mai mare divizor comun al lui a și b și notăm d=(a,b)

dacă: 1) da şi db 2) dacă ca şi cb, atunci cd (c )

Spunem că numărul natural m este cel mai mic multiplu comun al lui a și b și notăm m=[a,b]

dacă: 1) am şi bm 2) dacă ac şi b c atunci mc (c ).

Proprietăţi uzuale: Fie a,b,c .

1) aa (reflexivitatea)

ab şi ba a = b (antisimetria)

Summary Divisibility in the Set of Natural Numbers. Basic Properties

6th grade

1) exposed by Manuela Prajea, Ph.D.

* Curriculum for the Olympics Page 2

ab şi bc ac (tranzitivitatea)

2) 1a , a1 a=1 ; a0 , 0a a=0

3) ab şi ac a(xb±yc), () x, y

4) ab acbc ; acbc, c≠0 ab

5) ac si bd abcd

6) ab abc ; ( Gauss) abc şi (a,b)=1 ac

p|ab, p prim p|a sau p|b

7) ac și bc , (a,b)=1 abc

8) (a,b)=1, (a,c)=1 (a,bc)=1 ; (ca,cb)=c(a,b)

9) (a,b)=d () x, y astfel încât (x,y)=1 şi a=dx, b=dy;m=dxy

[a,b]=m () x, y astfel încât (x,y)=1 şi m=ax, m=by

10) [a,b](a,b) = ab

11*) dacă a=bc+r, r , atunci (a,b)=(b,r)

(v. algoritmul lui Euclid de aflare a c.m.m.d.c. a două numere naturale)

Summary Divisibility in the Set of Natural Numbers. Basic Properties

6th grade

1) exposed by Manuela Prajea, Ph.D.

* Curriculum for the Olympics Page 3

12*) (a,b)=d () x, y astfel încât d=ax+by

(a,b)=1 () x, y astfel încât 1=ax+by

13*) (a+b) n

= M a+bn

(a+b) n

= M a+bn , n , n par

(a-b) n

= M a- bn , n , n impar

14*) ca-b c (a n

– b n

), n

15*) ( Fermat) p număr prim, p nu divide a pap-1

-1

Criterii de divizibilitate

Fie a . Atunci:

a⋮2 u(a)ϵ 0,2,4,6,8

a⋮4 numărul determinat de ultimele două cifre ale lui a este divizibil cu 4 (generalizare)

a⋮5 u(a) 0,5

a⋮25 numărul determinat de ultimele două cifre ale lui a este divizibil cu 25 (generalizare)

a⋮10 u(a)=0

a⋮100 ultimele două cifre ale numărului a sunt 0 (generalizare)

a⋮3 suma cifrelor lui a este divizibila cu 3

a⋮9 suma cifrelor lui a este divizibila cu 9

a⋮11 diferența dintre suma cifrelor de rang par și suma cifrelor de rang impar este divizibilă

cu 11.

Summary Divisibility in the Set of Natural Numbers. Basic Properties

6th grade

1) exposed by Manuela Prajea, Ph.D.

* Curriculum for the Olympics Page 4

Teorema fundamentală a aritmeticii*

Dacă , 2n n , atunci n poate fi descompus în mod unic (până la o permutare a

factorilor) ca produs finit de numere prime, i.e.:

*

1 2, , ,..., kk p p p numere prime distincte, *

1 2, ,..., ka a a a.î.: 1 2

1 2 ... kaa a

kn p p p .

Numărul/ suma/ produsul divizorilor unui număr natural*

Dacă , 2n n și 1 2

1 2 ... kaa a

kn p p p este descompunerea în factori primi a lui n , atunci: n

i.e. numărul divizorilor lui n este dat de: 1 2( ) 1 1 ... 1kn a a a

n i.e. suma divizorilor lui n este dată de: 1 2 11 1

1 2

1 2

11 1( ) ...

1 1 1

kaa a

k

k

pp pn

p p p

n i.e. produsul divizorilor lui n este dat de: 1 22 1 1 ... 1ka a a

n n

.

Indicatorul lui Euler al unui număr natural*

Dacă n , vom nota cu n numărul de numere naturale mai mici ca n și prime cu n .

Numărul n s.n. indicatorul lui Euler al numărului n . Atunci:

a) 1

1, 1 ,k kp p p pp

p număr prim, *k

b) , , *, , 1ab a b a b a b

c) 1 2

1 1 11 1 ... 1

k

n np p p

, 1 2

1 2 ... kaa a

kn p p p fiind descompunerea în factori primi a lui n .