Cel mai mare divizor comun
Cel mai mare divizor comun (c.m.m.d.c.) a două numere întregi este numărul care împarte exact ambele numere și pentru care nu există niciun alt număr mai mare care să împartă exact ambele numere.
Ca exemplu, să luăm numerele 24 și 32. Care este cel mai mare divizor comun al lor? Căutăm în primul rând un număr care le împarte pe amândouă.
- De exemplu, numărul 12 împarte numărul 24, dar nu împarte numărul 32, pentru că 32 : 12 este egal cu 2,666…, ceea ce nu este număr întreg. Deci numărul 12 nu poate fi cel mai mare divizor comun al numerelor 24 și 32.
- Ce zici de numărul 4? Acesta le împarte pe amândouă, 24 : 4 este egal cu 6 și 32 : 4 este egal cu 8. Numărul 4 este deci primul nostru candidat. Nu există vreun număr mai mare care să le împartă pe amândouă?
- Numărul 8 împarte și numărul 24, și numărul 32 și, în același timp, este mai mare decât 4.
- Niciun alt număr mai mare decât 8 care să le împartă pe amândouă nu există. Numărul 8 este deci cel mai mare divizor comun al numerelor 24 și 32.
Algoritmul lui Euclid pentru aflarea celui mai mare divizor comun
Există un mod destul de simplu de a găsi cel mai mare divizor comun a două numere cu algoritmul lui Euclid. Avem la început două numere x și y pentru care vrem să găsim cel mai mare divizor comun. Ca exemplu, încercăm cu numerele x = 50 și y = 35. Procedăm astfel:
- Împărțim x : y și reținem restul împărțirii. Acest rest îl notăm r. Pentru exemplul nostru avem 50 : 35, ceea ce ne dă restul r = 15.
- Acum interschimbăm variabilele: în variabila x punem valoarea lui y, iar în y punem valoarea lui r. Valoarea inițială a lui x o aruncăm. După acest pas obținem x = 35 și y = 15.
- Acum verificăm dacă y este egal cu zero. Dacă da, cel mai mare divizor comun este numărul x. Deoarece y nu este egal cu zero, continuăm și repetăm întregul procedeu de la primul punct.
- Împărțim din nou x : y, adică 35 : 15, ceea ce ne dă restul r = 5.
- Interschimbăm variabilele, deci obținem x = 15 și y = 5. Deoarece y nu este egal cu zero, continuăm.
- Împărțim x : y, adică 15 : 5. Restul este r = 0.
- Interschimbăm variabilele și obținem x = 5 și y = 0.
- În acest moment y = 0 și algoritmul nostru se oprește. Cel mai mare divizor comun este numărul x = 5.
Important este că ordinea numerelor nu contează. Dacă am inversa numerele din exemplu, am obține perechea x = 35 și y = 50. Procedeul ar fi același:
- Împărțim x : y, adică 35 : 50, ceea ce ne dă restul r = 35.
- Interschimbăm variabilele x = 50 și y = 35.
- Vedem că după acest pas doar am inversat între ele conținutul variabilelor x și y…
Calculator
Acest calculator îți calculează cel mai mare divizor comun.
