Găsește cel mai mare divizor comun (cmmdc) pentru numere mari
Pentru numere mari, descompunerea în factori primi este dificilă. Dacă vrem să stabilim cel mai mare divizor comun (cmmdc) al unor astfel de numere mari, atunci se va folosi o metodă care nu folosește descompunerea în factori primi, ci algoritmul lui Euclid... a se vedea exemplul de mai jos.
Calculăm cel mai mare divizor comun (cmmdc) al numerelor 53.667 și 25.527 folosind algoritmul lui Euclid:
- 1) 53.667 = 25.527 × 2 + 2.613 (împarte numărul mai mare la numărul mai mic)
- 2) 25.527 = 2.613 × 9 + 2.010 (împarte numărul mai mic la restul operației de mai sus)
- 3) 2.613 = 2.010 × 1 + 603 (împarte restul de la a prima operație la restul de la a doua operație)
- 4) 2.010 = 603 × 3 + 201 (împarte restul de la a doua operație la restul de la a treia operație)
- 5) 603 = 201 × 3 + 0 (împarte restul de la a treia operație la restul de la a patra operație); în acest moment, nemaiexistând rest, ne oprim, 201 e numărul căutat.
Cel mai mare divizor comun al celor două numere este ultimul rest diferit de zero.
Dacă acest ultim rest este egal cu unu, atunci cele două numere sunt prime între ele.
Pentru operațiile de mai sus, 201 este cel mai mare divizor comun (cmmdc) al numerelor 53.667 și 25.527.
Putem demonstra cu ajutorul algoritmului lui Euclid și faptul că două numere sunt prime între ele.
Folosind algoritmul lui Euclid să calculăm cmmdc (87; 41):
- 1) 87 = 41 × 2 + 5 (împarte numărul mai mare la numărul mai mic)
- 2) 41 = 5 × 8 + 1 (împarte numărul mai mic la restul operației de mai sus)
- 3) 5 = 5 × 1 + 0 (împarte restul de la a prima operație la restul de la a doua operație, care este însă unu, operația nu va mai avea rest)
Ultimul rest diferit de zero al operațiilor de mai sus este egal cu 1.
cmmdc (87; 41) = 1, deci numerele sunt prime între ele.
Aplicarea algoritmului lui Euclid pentru mai mult de două numere:
Algoritmul lui Euclid se poate folosi și pentru aflarea celui mai mare divizor comun (cmmdc) al mai multor numere, de exemplu a, b și c. Se va proceda în etape. Întâi vom gasi cmmdc(a; b) = d apoi vom afla cmmdc(c; d) = e.
Algoritmul lui Euclid pentru găsirea celui mai mic multiplu comun (cmmmc) pt. numere mari
În cazul numerelor mari devine incomod de calculat cel mai mic multiplu comun (cmmmc), deoarece descompunerea în factori primi cere mult timp.
Cu ajutorul algoritmului lui Euclid se poate găsi cel mai mare divizor comun (cmmdc) - vezi mai sus, dar și cel mai mic multiplu comun (cmmmc), după regula:
cmmmc (a; b) = (a × b) / cmmdc (a; b)
Această metodă nu se poate extinde la mai mult de două numere.