Page 38 - MATINF Nr. 11-12

38 V. P˘aun

2 Algoritmul lui Euclid

Fie a s , i b dou˘ numere naturale strict pozitive.
a
Algoritmul lui Euclid calculeaz˘a cel mai mare divizor comun al numerelor a s , i b. S˘a
presupunem c˘a a > b.

a
Se pleac˘ de la proprietatea c˘a, dac˘ d|a s , i d|b atunci d|(a − b) s , i reciproc, dac˘ d|(a − b) s , i
a
a
a
a
d|b atunci d|a. Rezult˘ c˘ mult , imea divizorilor comuni ai numerelor a s , i b coincide cu mult , imea
divizorilor comuni ai numerelor a − b s , i b, prin urmare c.m.m.d.c. (a, b) = c.m.m.d.c. (a − b, b).
Aceast˘a proprietate ne permite s˘a ˆınlocuim ˆın procesul de calculul al celui mai mare divizor
comun, num˘arul mai mare, presupus a, cu un num˘ar mai mic a − b. Repetˆand acest proces de
reducere, obt , inem numere naturale din ce in ce mai mici astfel ˆınc˘at dup˘a un num˘ar finit de
pas , i, vom ajunge ˆın situat , ia ˆın care numerele a s , i b devin egale, valoare ce reprezint˘ c.m.m.d.c.
a
(a, b).
Funct , ia C++ care implementeaz˘ acest algoritm este urm˘atoarea:
a
int cmmdc(int a,int b)
{ while(a!=b)
if(a>b)a=a-b;
else b=b-a;
return a;
}

Utilizˆand operatorul condit , ional ?: putem renunt , a la instruct , iunea if astfel:

int cmmdc(int a,int b)
{
while(a!=b) a>b?a=a-b:b=b-a;
return a;
}

a
Varianta recursiv˘ a acestei funct , ii este:
int cmmdc(int a,int b)
{
if(a==b) return a;
if(a>b) return cmmdc(a-b,b);
return cmmdc(a,b-a);
}

Algoritmul lui Euclid bazat pe sc˘aderi repetate poate fi ˆımbun˘at˘t , it dac˘ vom mics , ora, la fiecare
a
a
pas, num˘arul mai mare, presupus a, cu q ∗ b unde q este cˆatul dintre a s , i b.
Algoritmul foloses , te urm˘atoarea observat , ie:
Fie a s , i b dou˘ numere naturale astfel ˆıncˆat a = b ∗ q + r, q, r ∈ N, 0 ≤ r < b.
a
Se poate demonstra us , or c˘a
d|a, d|b ⇒ d|r (1)

s , i respectiv
d|b, d|r ⇒ d|a. (2)