Page 37 - MATINF Nr. 11-12

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Algoritmul extins al lui Euclid

Viorel P˘aun 1

1 Cel mai mare divizor comun, cel mai mic multiplu comun

Cel mai mare divizor comun (prescurtat c.m.m.d.c.) a dou˘a sau mai multe numere
ˆıntregi, care nu sunt toate zero, este cel mai mare num˘ar ˆıntreg pozitiv, care ˆımparte fiecare
dintre numerele date.
Cel mai mic multiplu comun (prescurtat c.m.m.m.c.) pentru dou˘a sau mai multe
numere naturale nenule este cel mai mic num˘ar natural care se divide cu toate numerele date.

ˆ
In matematic˘a, cel mai mare divizor comun a dou˘a numere ˆıntregi a s , i b se mai noteaz˘a s , i
cu (a, b) iar cel mai mic multiplu comun se noteaz˘a cu [a, b]. Dac˘a unul dintre a s , i b este zero,
cel mai mare divizor comun al lor este egal cu valoarea absolut˘a a num˘arului diferit de zero:
(0, a) = |a|, (a, 0) = |a|.
Fie a s , i b dou˘ numere naturale strict pozitive.
a
Dac˘ consider˘am divizorii primi d 1 , d 2 , . . . , d n ai numerelor a s , i b, putem scrie:
a
p 1
p 2
p n
a = d · d · . . . · d ,
n
2
1
q 2
q 1
b = d · d · . . . · d , unde p i ≥ 0, q i ≥ 0, ∀i ∈ {1, 2, . . . , n}.
q n
1 2 n
Atunci:
min(p 1 ,q 1 ) min(p 2 ,q 2 ) min(p n,q n)
(a, b) = d · d · . . . · d ,
1 2 n
[a, b] = d max(p 1 ,q 1 ) · d max(p 2 ,q 2 ) · . . . · d max(p n,q n) .
2
n
1
a
De unde rezult˘ c˘a (a, b) · [a, b] = a · b.
Exercit , iu
Ar˘atat , i c˘a:
1. (a, b, c) = ((a, b), c);
2. (a, [b, c]) = [(a, b), (a, c)];
3. [a, (b, c)] = ([a, b], [a, c]).
1
a
Lect.univ.dr., Universitatea Nat , ional˘ de S , tiint , ˘ s , i Tehnologie POLITEHNICA Bucures , ti, Centrul Universitar
a
Pites , ti, viop23@yahoo.com
37