Ce este şi cum se determină cel mai mare divizor comun

Ce înseamnă cel mai mare divizor comun

Pentru o mulțime de numere întregi pozitive, cel mai mare divizor comun a două sau mai multe numere naturale întregi a și b este definit ca un alt număr natural d, care nu este niciodată negativ sau 0, deoarece cel mai mic număr întreg pozitiv comun oricăror două numere este întotdeauna 1, potrivit Cuemath.com. Cel mai mare divizor comun al unor numere întregi ne ajută la găsirea factorului comun.

Acesta se notează cu (a, b) și se prescurtează cmmdc sau gcd, care provine din englezescul greatest common divisor. Ca să fie cel mai mare divizor comun, acest număr trebuie, pe de-o parte, să se împartă exact la fiecare dintre numerele date, adică să se împartă fără rest (d este divizor comun al numerelor a și b, adică d|a și d|b). De asemenea, orice alt divizor comun c al numerelor a și b divide pe d, adică c|a și c|b =˃ c|d, iar cel mai mare divizor comun d trebuie să fie cel mai mare număr posibil.

Spre exemplu, pentru numerele 12 și 18, divizorii comuni sunt:

• divizorii lui 12 sunt: 1, 2, 3, 4, 6 și 12;
• divizorii lui 18 sunt: 1, 2, 3, 6, 9 și 18;
• divizorii comuni ai lui 12 și 18 sunt: 1, 2, 3 și 6;
• cmmdc al numerelor 12 și 18 este 6

Dacă (a, b) = 1, spunem că a și b sunt numere prime între ele sau relativ prime ori că a este prim cu b. Spre exemplu, numerele 12 și 25 sunt numere prime între ele pentru că numărul 1 este singurul lor divizor comun. În acest caz vom scrie (12, 25) = 1

Recomandări

Drama unui român după internarea la sanatoriu, în Techirghiol. Fractura provocată de kinetoterapeut, „pedepsită” cu daune morale de 100.000 de lei

Cum se determină cel mai mare divizor comun

Determinarea celui mai mare divizor comun al două numere naturale nenule a și b este o abilitate fundamentală în matematică. Există diferite metode, fiecare cu avantajele ei, de la descompunerea în factori primi, continuând cu metoda scăderilor repetate și terminând cu metoda împărțirilor repetate, care este cunoscută și sub denumirea de algoritmul lui Euclid. Alegerea celei mai potrivite metode depinde de context și de complexitatea numerelor pe care le analizăm. Iată care sunt aceste metode de aflare a celui mai mare divizor comun pentru două numere naturale întregi:

Metoda clasică: descompunerea în factori primi

Această metodă presupune descompunerea celor două numere naturale în factori primi, apoi alegerea factorilor primi comuni, adică cei pe care îi vedem atât la numărul a, cât şi la numărul b, luați o singură dată fiecare, cu exponentul cel mai mic (la puterea cea mai mică) şi se inmulţesc între ei.

Recomandări

Înțelegerea dintre Nicusor Dan și Ilie Bolojan pe tema majorării TVA. Când și cu cât va crește

Exemplu

Avem de determinat cel mai mare divizor comun (60, 48). Iată ce trebuie să facem:

Descompunem cele două numere în factori primi

60 = 2 × 2 × 3 × 5 = 2² x 3 x 5

48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3

Se aleg factorii comuni: 2 și 3

Se alege cea mai mică putere:

pentru 2 este 2²

pentru 3 este 3¹

În aceste condiții, cmmdc (60, 48) = 2² × 3¹ = 4 x 3 = 12

Metoda împărțirilor repetate (algoritmul lui Euclid)

Aceasta este o metodă rapidă și eficientă de calcul al celui mai mare divizor comun, care folosește împărțiri succesive. În matematică, această metodă este cunoscută și sub denumirea de algoritmul lui Euclid și a fost denumită după matematicianul grec Euclid, care l-a descris în Cărțile VII și X din lucrarea intitulată „Elementele”, care este alcătuită din 13 cărți (sau capitole numite cărți după procedura uzuală în Antichitate), care a fost scrisă în jurul anului 300 î.Hr., potrivit enciclopediei virtuală Wikipedia.

Algoritmul lui Euclid se bazează pe ideea că cel mai mare divizor comun al două numere naturale nenule rămâne neschimbat dacă din numărul mai mare se scade cel mai mic. Se bazează pe principiul: cmmdc (a, b) = cmmdc (b, a mod b), până când restul este 0, iar cmmdc este ultimul rest nenul.

Recomandări

Drama unui român după internarea la sanatoriu, în Techirghiol. Fractura provocată de kinetoterapeut, „pedepsită” cu daune morale de 100.000 de lei

Exemplu

Avem de determinat cel mai mare divizor comun (252, 105). Pentru asta va trebui să împărțim succesiv pentru a afla ultimul rest diferit de 0:

252 : 105 = 2, rest 42

105 : 42 = 2, rest 21

42 : 21 = 2, rest 0

În aceste condiții, cmmdc (252, 105) = 21

Metoda scăderilor repetate (varianta veche a algoritmului lui Euclid)

Metoda scăderilor repetate este o variantă mai veche a algoritmului lui Euclid, fiind mai puțin eficientă, însă mai ușor de înțeles. Dacă aplicăm această metodă de calcul a celui mai mare divizor comun a două numere naturale atunci trebuie să scădem la fiecare pas numărul mai mic din numărul mai mare până când unul dintre rezultate va deveni 0. 

La final, valoarea numărului care a rămas nenul va fi cmmdc-ul numerelor inițiale. Această variantă a algoritmului euclidian se bazează pe principiul următor: dacă d este divizor comun al numerelor a și b, adică d|a și d|b, atunci d|(a – b) (unde a ≥ b), dacă d se împarte exact la ambele numere, atunci se va împărți exact și la diferența dintre acestea. Acest algoritm nu poate fi aplicat dacă unul dintre numere este 0.

Exemplu

Avem de calculat cel mai mare divizor comun (28, 20). Așa cum spuneam, pentru a afla cmmdc al celor două numere naturale va trebui să scădem succesiv numărul mai mic din cel mai mare, după cum urmează:

28 – 20 = 8

20 – 8 = 12

12 – 8 = 4

8 – 4 = 4

4 – 4 = 0

Datorită faptului că rezultatul scăderii este egal, cmmdc (28, 20) = 4

Calcularea cmmdc pentru mai multe numere

Pentru a determina cel mai mare divizor comun pentru mai mult de două numere trebuie parcurși câțiva pași, după cum urmează:

Pasul 1

Se determină cmmdc-ul primelor două numere.

Pasul 2

Se va folosi rezultatul de la pasul 1 (cmmdc-ul primelor două numere) pentru a se determina apoi cmmdc-ul acestuia și al celui de-al treilea număr din listă.

Pasul 3

În continuare se va repeta operațiunea și se va determina cel mai mare divizor comun între cmmdc-ul anterior și cel de-al patrulea număr din listă și tot așa până când se va calcula cmmdc-ul cu ultimul număr rămas din listă.

Pasul 4

Odată aflat cmmdc-ul cu ultimul număr din listă, acela va fi și cmmdc-ul tuturor numerelor inițiale.

Exemplu:

Să presupunem că avem de determinat cmmdc-ul (12, 18, 24). Iată ce avem de făcut:

Pasul 1

cmmdc (12, 18) = 6

Pasul 2

cmmdc (6, 24) = 6

Așadar, cmmdc (12, 18, 24) = 6.

Pentru a determina cel mai mare divizor comun pentru mai mult de două numere se mai poate aplica și metoda tabelară. Pentru asta, trebuie să se scrie toate numerele și să se extragă succesiv factorii comuni pentru acestea, până în momentul în care nu se vor mai putea extrage factori comuni. Produsul tuturor acestor factori comuni va fi cel mai mare divizor comun al numerelor inițiale.

Exemplu:

Pentru a determina cmmdc (36, 60, 48) vom extrage succesiv factorii comuni pentru cele trei numere după care vom scrie toate numerele într-un tabel.

36 : 2 = 18 : 2 = 9 : 3 = 3

60 : 2 = 30 : 2 = 15 : 3 = 5

48 : 2 = 24 : 2 = 12 : 3 = 4

Așa cum se poate observa din acest tabel, nu mai există factori comuni pentru 3, 5 și 4, ceea ce înseamnă că cmmdc (36, 60, 48) = 2 × 2 × 3 = 12.

Vezi şi cum se calculează volumul!