Algoritmul lui Euclid pentru numere mari, metodă de calcul pentru CMMDC și CMMMC

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. Vom explica și de ce funcționează acest algoritm.

Acest algoritm implică operația de împărțire și calcularea resturilor.
'a' și 'b' sunt cele două numere întregi pozitive, 'a' >= 'b'.
Împarte 'a' la 'b' și obține restul, 'r'.
Dacă 'r' = 0, STOP. 'b' = CMMDC al 'a' și 'b'.
Altfel: Înlocuiește ('a' cu 'b') și ('b' cu 'r'). Revino la pasul împărțirii, de mai sus.

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.

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.

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.

Notă: 'a' : 'b' = 'q' + 'r' este echivalent cu ecuația: 'a' = 'q' × 'b' + 'r', unde 'q' este câtul operației.
Când valoarea finală a lui 'r' = 0, valoarea finală a lui 'b' este un divizor al valorii finale a lui 'a', deoarece 'a' = 'q' × 'b' + 0.
Mergi înapoi prin pașii anteriori și analizează fiecare ecuație, 'a' = 'q' × 'b' + 'r', și observă că la fiecare pas, valoarea finală a lui 'b' este un divizor al fiecărei valori a lui 'r' și a fiecărei valori a lui 'b' și, prin urmare, este un divizor al fiecărei valori a lui 'a'. Deci ultima valoare a lui 'b', care este ultimul rest diferit de zero, este un divizor al valorilor inițiale ale 'a' și 'b'.

Ne uităm la toate ecuațiile: 'a' = 'q' × 'b' + 'r'. După cum am văzut mai sus, valoarea finală a lui 'b' este un divizor al tuturor valorilor 'a', 'b' și 'r'.
Prin urmare, valoarea finală a lui 'b' trebuie să fie, de asemenea, un divizor al ultimei valori a lui 'r', cea care e diferită de zero. Iar valoarea finală a 'b' nu poate fi mai mare decât această ultima valoare a lui 'r'. Însă valoarea finală a lui 'b' e egală cu acea ultimă valoare a lui 'r', prin urmare valoarea finală a lui 'b' e cel mai mare divizor al valorilor inițiale ale lui ('a' și 'b'). Și prin definiție se numește cel mai mare divizor comun al numerelor.

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.

Î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.

Cel mai mic multiplu comun, formulă: cmmmc (a; b) = ^{(a × b)} / _{cmmdc (a; b);}
Să presupunem că descompunerile în factori primi ale lui 'a' și 'b' sunt:
a = m × n × p, unde m, n, p - pot fi orice număr prim
b = m × q × t, unde m, q, t - pot fi orice număr prim
=> cmmmc (a; b) = m × n × p × q × t;
=> cmmdc (a; b) = m;