Algoritmul lui Euclid: pași, pseudocod și exemple

Algoritmul lui Euclid calculează cel mai mare divizor comun al două numere naturale prin împărțiri cu rest. Înlocuiești perechea de numere cu al doilea număr și restul împărțirii, până când restul devine zero. Ultimul rest nenul este CMMDC. Metoda este utilă atât la matematică, pentru simplificarea fracțiilor, cât și la informatică, unde exersezi variabile, operatorul modulo și structuri repetitive.

În acest ghid construim algoritmul pas cu pas, justificăm regula și urmărim valorile variabilelor. Nu ai nevoie de un limbaj anume: pseudocodul poate fi transpus în limbajul folosit la clasă după ce ai înțeles ordinea operațiilor.

Pe scurt: care sunt pașii algoritmului?

1. Pornești de la două numere naturale a și b.

2. Cât timp b este diferit de zero, calculezi r = a mod b.

3. Înlocuiești a cu b, apoi b cu r.

4. Când b ajunge la zero, rezultatul este valoarea lui a.

Operatorul mod oferă restul împărțirii întregi. De exemplu, 29 mod 6 = 5, pentru că 29 = 6 × 4 + 5. Nu confundăm restul cu rezultatul împărțirii reale și nici cu câtul întreg. În acest exemplu, câtul este 4, iar restul este 5.

De ce funcționează înlocuirea cu restul?

Dacă a = b × q + r, atunci a și b au exact aceiași divizori comuni ca b și r. Un număr care divide atât a, cât și b divide și diferența a − b × q, adică r. Invers, dacă divide b și r, divide și suma b × q + r, adică a.

Prin urmare, CMMDC(a, b) = CMMDC(b, r). Perechea se schimbă, dar răspunsul căutat rămâne același. Aceasta este proprietatea care se păstrează după fiecare pas, numită invariant. Nu trebuie să memorezi termenul pentru a calcula, însă explicația te ajută să reconstruiești algoritmul când uiți forma lui.

Restul unei împărțiri la un număr pozitiv este mai mic decât împărțitorul. Valorile pozitive care apar ca al doilea element al perechii scad strict. Nu poți avea o succesiune infinită de numere naturale strict descrescătoare, deci procesul se oprește.

Exemplu complet: CMMDC pentru 252 și 105

• 252 = 105 × 2 + 42. Noua pereche este 105 și 42.

• 105 = 42 × 2 + 21. Noua pereche este 42 și 21.

• 42 = 21 × 2 + 0. Noua pereche este 21 și 0.

Al doilea număr este acum zero, deci ne oprim. Răspunsul este 21. Verificarea directă arată că 252 : 21 = 12 și 105 : 21 = 5. Ambele împărțiri sunt exacte. Pentru a vedea de ce nu există un divizor comun mai mare, folosim proprietatea demonstrată: perechea finală 21 și 0 are cel mai mare divizor comun 21.

Cum scrii algoritmul în pseudocod?

citește a, b
cât timp b ≠ 0 execută
    r ← a mod b
    a ← b
    b ← r
scrie a

Variabila r păstrează restul înainte să modifici numerele. Dacă scrii mai întâi a ← b și abia apoi calculezi a mod b, ai pierdut valoarea inițială a lui a. Ai calcula b mod b, care este zero, și ai opri greșit algoritmul după prima iterație.

La o cerință de urmărire, notează valorile de la începutul iterației și restul calculat. Nu amesteca valorile vechi cu cele noi în aceeași coloană. O urmă clară pentru exemplul anterior este: (252, 105, 42), apoi (105, 42, 21), apoi (42, 21, 0).

Ce se întâmplă dacă primul număr este mai mic?

Algoritmul funcționează fără să sortezi numerele. Pentru a = 18 și b = 48, prima operație este 18 mod 48 = 18. Noua pereche devine 48 și 18, iar calculul continuă: 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0. Rezultatul este 6.

Acest exemplu este un test bun pentru un program. Dacă soluția ta presupune fără justificare că primul număr este cel mai mare, poate funcționa pe unele intrări și eșua pe altele. Verifică întotdeauna restricțiile din enunț înainte să introduci presupuneri.

Patru situații speciale pe care să le verifici

• Numere egale: pentru 35 și 35, restul primei împărțiri este zero, iar rezultatul este 35.

• Numere prime între ele: pentru 35 și 12, resturile sunt 11, 1, 0. Rezultatul este 1. Numerele nu trebuie să fie fiecare prime.

• Un număr este zero: CMMDC(27, 0) = 27. Dacă intrarea este 0 și 27, prima iterație conduce tot la 27 și 0.

• Ambele numere sunt zero: definiția elementară a celui mai mare divizor comun nu produce un maxim pozitiv. Unele convenții informatice folosesc rezultatul 0; urmează explicit cerința problemei.

Pentru numere întregi negative, o implementare uzuală lucrează cu valorile absolute, dar verifică domeniul acceptat și limitele tipului numeric. În exercițiile de început este mai simplu să precizezi că intrările sunt naturale și nu sunt ambele zero.

Aplicație: simplificarea unei fracții

Pentru fracția 252/105, CMMDC este 21. Împărțim numărătorul și numitorul la 21 și obținem 12/5. Fracția rezultată este ireductibilă, deoarece 12 și 5 sunt prime între ele. Algoritmul nu schimbă valoarea fracției: elimină același factor din ambele componente.

Dacă problema cere și CMMMC pentru două numere strict pozitive, poți folosi relația CMMMC(a, b) = (a / CMMDC(a, b)) × b. Într-un program cu tipuri numerice limitate, împărțirea înaintea înmulțirii poate reduce riscul de depășire, dar nu garantează că rezultatul încape în tipul ales.

Exerciții pentru verificarea înțelegerii

1. Calculează CMMDC(84, 30) și scrie toate resturile.

2. Urmărește algoritmul pentru perechea 14 și 49.

3. Găsește două numere compuse care sunt prime între ele.

4. Simplifică fracția 96/144 folosind algoritmul.

5. Explică de ce varianta „cât timp a ≠ 0” nu poate înlocui direct condiția din pseudocodul de mai sus.

Răspunsuri: la primul exercițiu resturile sunt 24, 6, 0, deci rezultatul este 6. La al doilea sunt 14, 7, 0, deci rezultatul este 7. Pentru al treilea poți alege 8 și 9. La al patrulea, CMMDC este 48, deci fracția devine 2/3. La ultimul, condiția trebuie să protejeze împărțirea la b: dacă b este zero și a nu este zero, operația modulo nu este definită.

Întrebări frecvente despre algoritmul lui Euclid

Trebuie să fac descompunerea în factori primi?

Nu. Avantajul metodei este că folosește direct împărțiri cu rest. Descompunerea în factori primi rămâne o altă metodă de calcul și o verificare posibilă pentru numere mici.

Care este rezultatul: ultimul rest sau ultimul rest nenul?

Ultimul rest calculat este zero. Rezultatul este ultimul rest nenul, păstrat în variabila a după ultima actualizare. Dacă prima împărțire este exactă, acesta este chiar împărțitorul inițial.

Cum exersez fără să memorez mecanic?

Alege o pereche, explică proprietatea divizorilor comuni și urmărește variabilele pe hârtie. Apoi verifică rezultatul prin împărțirea ambelor numere. Poți căuta un profesor de informatică pentru feedback pe rezolvări. Dacă pregătești examenul, vezi opțiunile de pregătire pentru BAC și cum funcționează Hola25.