Page 40 - MATINF Nr. 11-12

40 V. P˘aun

if(a%2==0) return cmmdcStein(a/2, b);
if(b%2==0) return cmmdcStein(a, b/2);
if(a>b) return cmmdcStein(a-b, b);
return cmmdcStein(a,b-a);
}

3 Algoritmul extins al lui Euclid

a
Algoritmul extins al lui Euclid rezolv˘ urm˘atoarea problem˘a:
Fiind dat , i doi ˆıntregi a s , i b care nu sunt simultan 0, s˘a se determine cel mai mare divizor
comun al lor, d s , i doi ˆıntregi m s , i n astfel ˆıncˆat m · a + n · b = d (Identitatea lui B´ezout).

Pentru obt , inerea identit˘at , ii m · a + n · b = d, se pleac˘ de la relat , iile:
a
1 · a + 0 · b = a, (3)

0 · a + 1 · b = b, (4)

dac˘ a ≥ 0 s , i b ≥ 0.
a
a
Dac˘ a < 0, relat , ia (3) se ˆınlocuies , te cu
−1 · a + 0 · b = −a.

Dac˘ b < 0, relat , ia (4) se ˆınlocuies , te cu
a
0 · a + (−1) · b = −b.

Fie m = 1, n = 0 s , i m 1 = 0, n 1 = 1.

Obt , inem relat , iile:
m · a + n · b = a, (5)

m 1 · a + n 1 · b = b. (6)
a
a
a
Cum cel mai mare divizor comun a dou˘ numere nu se modific˘ dac˘ din num˘arul cel mai mare
a
sc˘adem num˘arul mai mic, deducem c˘ prin repetarea procesului de reducere prin sc˘adere aplicat
ˆıntre relat , iile (5) s , i (6) ajungem ˆın situat , ia ˆın care una din relat , ii are membrul drept egal cu
zero.
Cealalt˘ relat , ie ne furnizeaz˘ cel mai mare divizor comun s , i coeficient , ii m s , i n ai Identit˘t , ii
a
a
a
lui Bezout.
Dac˘ a > b, prin sc˘adere obt , inem relat , ia
a
(m − m 1 )a + (n − n 1 )b = a − b.

Adic˘ m ← m − m 1 si n ← n − n 1 s , i continu˘am cu
a
m · a + n · b = a,