Algoritmul lui Euclid pentru numere mari, o metodă de calcul a celui mai mare divizor comun, cmmdc și a celui mai mic multiplu comun, cmmmc; cmmmc (a; b) = (a × b) / cmmdc (a; b) - teorie, exemple și explicații

O metodă de calcul pentru găsirea celui mai mare divizor comun (cmmdc) al numerelor mari

  • Pentru numere mari, procesul de descompunere în factori primi este lung și dificil. Dacă ar fi nevoie să calculăm cel mai mare divizor comun (cmmdc) al unor numere foarte mari, atunci o metodă care nu se bazează pe descompunerea în factori primi a numerelor ar fi mai mult decât binevenită. Algoritmul lui Euclid este o astfel de metodă pentru calcularea cmmdc.
  • Haideți să vedem exemplul de mai jos. De asemenea, vom explica și de ce funcționează.
  • Acest algoritm începe prin împărțirea numerelor și înregistrarea restului operației.
  • Dacă 'a' și 'b' sunt cele două numere întregi pozitive, 'a' >= 'b'.
  • Împărțiți 'a' la 'b' și obțineți restul, 'r'.
  • Dacă 'r' = 0, STOP. 'b' este cmmdc pentru 'a' și 'b'.
  • Altfel: înlocuiți ('a' cu 'b') și ('b' cu 'r'). Reveniți la pasul anterior.

Să vedem care este cel mai mare divisor comun (cmmdc) al numerelor 53.667 și 25.527:

  • [1] Începeți prin a împărți numărul mai mare la cel mai mic:
  • 53.667 : 25.527 = 2 și Restul = 2.613 => 53.667 = 25.527 × 2 + 2.613
  • [2] Apoi împărțiți numărul mai mic la restul de la operația de mai sus:
  • 25.527 : 2.613 = 9 și Restul = 2.010 => 25.527 = 2.613 × 9 + 2.010
  • [3] Împărțiți restul primei operații la restul celei de-a doua operații:
  • 2.613 : 2.010 = 1 și Restul = 603 => 2.613 = 2.010 × 1 + 603
  • [4] Împărțiți restul celei de-a doua operații la restul celei de-a treia operații:
  • 2.010 : 603 = 3 și Restul = 201 => 2.010 = 603 × 3 + 201
  • [5] Împărțiți restul celei de-a treia operații la restul celei de-a patra operații:
  • 603 : 201 = 3 și Restul = 0 => 603 = 201 × 3
  • La acest pas, restul este zero, așa că ne oprim: 201 este numărul căutat.
  • În încheiere:
  • 201 este ultimul rest diferit de zero. Acesta este cel mai mare divizor comun, cmmdc, al numerelor.

Cel mai mare divizor comun al celor două numere este ultimul rest diferit de zero.

  • Dacă acest ultim rest este egal cu 1, atunci cele două numere sunt prime între ele (sau numite și relativ prime, coprime).
  • Pentru operațiile de mai sus, ultimul rest diferit de zero, 201, este cel mai mare divizor comun (cmmdc) al numerelor 53.667 și 25.527.
  • Folosind algoritmul lui Euclid putem demonstra că două numere sunt relativ prime, vezi exemplul de mai jos.

Calculați cmmdc (87, 41):

  • [1] Începeți prin a împărți numărul mai mare la cel mai mic:
  • 87 : 41 = 2 și Restul = 5 => 87 = 41 × 2 + 5
  • [2] Apoi împărțiți numărul mai mic la restul din operația de mai sus:
  • 41 : 5 = 8 și Restul = 1 => 41 = 5 × 8 + 1
  • [3] Împărțiți restul primei operații la restul celei de-a doua operații:
  • 5 : 1 = 5 și Restul = 0 => 5 = 1 × 5 + 0
  • Ultimul rest diferit de zero din operațiunile de mai sus este egal cu 1.
  • cmmdc (87, 41) = 1, deci numerele sunt relativ prime, prime între ele, coprime.

Dar de ce numărul astfel obținut este un divizor al valorilor inițiale 'a' și 'b'?

  • Notă: Împărțirea 'a' : 'b' = 'q' + 'r' corespunde ecuaţiei: 'a' = 'b' × 'q' + 'r', unde 'q' este câtul împărțirii.
  • Dacă ultima valoare a lui 'r' = 0, atunci ultima valoare a lui 'b' este un divizor al ultimei valori a lui 'a' deoarece 'a' = 'b' '.$multiply .' 'q' + 0.
  • Să calculăm cmmdc (a, b):
  • 1. Pas: 'a' = 'b' × 'q1' + 'r1', 'r1' diferit de zero.
  • 2. Pas: 'b' = 'r1' × 'q2' + 'r2', 'r2' diferit de zero.
  • 3. Pas: 'r1' = 'r2' × 'q3' + 'r3', 'r3' diferit de zero.
  • ...
  • (n-3). Pas: 'r(n-5)' = 'r(n-4)' × 'q(n-3)' + 'r(n-3)', 'r(n-3)' diferit de zero.
  • (n-2). Pas: 'r(n-4)' = 'r(n-3)' × 'q(n-2)' + 'r(n-2)', 'r(n-2)' diferit de zero.
  • (n-1). Pas: 'r(n-3)' = 'r(n-2)' × 'q(n-1)' + 'r(n-1)', 'r(n-1)' diferit de zero.
  • n. Pas: 'r(n-2)' = 'r(n-1)' × 'qn' + 'rn', 'rn' = zero.
  • Restul este zero, așa că ne oprim.
  • Dacă 'rn' = 0 => conform pasului cu numărul n: 'r(n-1)' este un divizor al lui 'r(n-2)'.
  • 'r(n-1)' este, de asemenea, ultimul rest diferit de zero.
  • Conform pasului cu numărul (n-1): 'r(n-1)' este un divizor al lui 'r(n-1)' (numărul propriu-zis) și al lui 'r(n-2)', așadar e un rest și al lui 'r(n-3)'.
  • Conform pasului cu numărul (n-2): 'r(n-1)' este un divizor al lui 'r(n-2)' și al lui 'r(n-3)', așadar e un rest și al lui 'r(n-4)'.
  • Conform pasului cu numărul (n-3): 'r(n-1)' este un divizor al lui 'r(n-3)' și al lui 'r(n-4)', așadar e un rest și al lui 'r(n-5)'.
  • ...
  • Conform pasului cu numărul 3: 'r(n-1)' este un divizor al lui 'r3' și al lui 'r2', așadar e un rest și al lui 'r1'.
  • Conform pasului cu numărul 2: 'r(n-1)' este un divizor al lui 'r2' și al lui 'r1', așadar e un rest și al lui 'b'.
  • Conform pasului cu numărul 1: 'r(n-1)' este un divizor al lui 'r1' și al lui 'b', așadar e un rest și al lui 'a'.
  • Deci, tocmai am arătat că ultimul rest diferit de zero, r(n-1), este un divizor atât al lui 'a' cât și al lui 'b'.

De ce numărul obținut în acest fel este întotdeauna egal cu cel mai mare divizor comun, cmmdc?

  • După cum am văzut mai sus, restul final diferit de zero împarte atât 'a' cât și 'b' fără rest. Să numim acest divizor al lor cu 't'.
  • Conform pasului cu numărul 1: Dacă 't' este un divizor al lui 'a' și 'b', atunci e și un divizor al lui 'r1'.
  • Conform pasului cu numărul 2: Dacă 't' este un divizor al lui 'b' și 'r1', atunci e și un divizor al lui 'r2'.
  • Și așa mai departe, până la pasul cu numărul (n-1): Dacă 't' este un divizor al lui 'r(n-3)' și 'r(n-2)', atunci e și un divizor al lui 'r(n-1)'. Dar așa cum am calculat mai sus, acest divizor este ultimul rest diferit de zero, care în cazul nostru este 'r(n-1)'.
  • Deci 't' nu poate fi mai mare decât 'r(n-1)', deoarece trebuie să fie un divizor al acestuia.

Cum se utilizează algoritmul lui Euclid pentru mai mult de două numere:

  • Algoritmul lui Euclid poate fi folosit și pentru a găsi cel mai mare divizor comun al mai multor numere, mai mult de două, cum ar fi 'a', 'b' și 'c'.
  • Mai întâi calculați cmmdc ('a', 'b') = 'd' și după aceea calculați cmmdc ('c', 'd').

Algoritmul lui Euclid: Calculați cel mai mic multiplu comun (cmmmc) pentru numere mari

  • Pentru numere foarte mari, devine nepractic să se calculeze cel mai mic multiplu comun (cmmmc), deoarece obținerea decompunerii în factori primi a acestor numere durează prea mult și apoi înmulțirea tuturor factorilor primi este o altă sarcină îndelungată.
  • Cu ajutorul algoritmului lui Euclid se găsește nu numai cel mai mare divizor comun (cmmdc) - așa cum s-a văzut mai sus, ci și cel mai mic multiplu comun (cmmmc) se calculează după formula:
  • cmmmc ('a', 'b') = ('a' × 'b') / cmmdc ('a', 'b')

  • Această metodă poate fi utilizată atunci când nu există mai mult de două numere.

Dovada formulei cmmmc de mai sus

  • Să presupunem că descompunerile în factori primi ale lui 'a' și 'b' sunt:
  • 'a' = 'm' × 'n' × 'p', unde 'm', 'n', 'p' sunt orice numere prime.
  • 'b' = 'm' × 'q' × 't', unde 'm', 'q', 't' sunt orice numere prime.
  • => cmmmc ('a', 'b') = 'm' × 'n' × 'p' × 'q' × 't'
  • => cmmdc ('a', 'b') = 'm'
  • Prin urmare:
  • ('a' × 'b') / cmmdc ('a', 'b') =
  • ('m' × 'm' × 'n' × 'p' × 'q' × 't') / 'm' =
  • 'm' × 'n' × 'p' × 'q' × 't' =
  • cmmmc ('a', 'b').