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

Cel mai mare divizor comun este un instrument matematic folosit în algebră, aritmetică și informatică. El ajută la rezolvarea unor algoritmi și la simplificarea fracțiilor. Să descoperim ce este cel mai mare divizor comun și care sunt metodele prin care poate fi calculat!

Cuprins

1 Ce sunt numerele naturale
2 Ce este divizorul comun
3 Cum se notează cel mai mare divizor comun
4 Cum se determină CMMDC
5 De ce este atât de eficient algoritmul lui Euclid

Cel mai mare divizor comun a două sau mai multe numere naturale este cel mai mare număr natural care poate divide numerele respective. Cel mai mare divizor comun este adesea prescurtat cu inițialele cmmdc, c.m.m.d.c. sau CMMDC. În cazul în care studiezi o lucrare de matematică în limba engleză, vei întâlni prescurtarea GCD sau gcd care vine de la greatest common divisor.

Ce sunt numerele naturale

Așa cum am subliniat mai sus, cel mai mare divizor comun se aplică doar numerelor naturale. Încă din primii ani de școală aflăm că numerele naturale sunt toate numerele strict pozitive și întregi precum 1, 2, 3, 4, 5…. până la infinit. Așa cum vedem, în matematică, numerele naturale sunt numerele folosite pentru numărarea și ordonarea obiectelor.

Ce este divizorul comun

Divizorul comun a două numere naturale este un număr întreg și pozitiv care divide cele două numere. Cel mai mare divizor comun este, bineînețeles, numărul cu cea mai mare valoare care divide cele două numere.

Trecutul neștiut al lui Joseph Adam, soțul Andei Adam. Cu ce se ocupă, de fapt, concurentul de la Asia Express și din ce face bani

Recomandarea zilei

Cu alte cuvinte, cmmdc trebuie să se împartă exact la cele două numere, adică să se împartă fără rest, ceea ce în formule matematice se exemplifică prin:

Ex: d este divizor comun al numerelor a și b, adică d/a și d/b

S-a aflat! De ce Adrian Alexandrov nu a mers în vacanță cu Elena Udrea și fiica lor, Eva Maria. Plănuiseră o excursie în familie, dar în ultimul moment el a rămas acasă. Apropiații cuplului au făcut o dezvăluire neașteptată

Recomandarea zilei

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.
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. Cel mai mare divizor comun ne ajută la găsirea factorului comun.

Cum se notează cel mai mare divizor comun

În formulele matematice, cel mai mare divizor comun este notat folosind parantezele rotunde. Astfel, putem avea următoarea formulă: (a, b) sau se prescurtează cmmdc.

Spre exemplu, dacă vrem să notăm cel mai mare divizor comun al numerelor 12 și 18, vom întâlni formula (12, 18) = 6. Avem aici un exemplu simplu, la rezolvarea căruia putem ajunge prin a nota toți divizorii lui 12 și toți divizorii lui 18.

Numerele care îl pot divide pe 12 sunt – 1, 2, 3, 4, 6 și 12;

Numerele care îl pot divide pe 18 sunt: 1, 2, 3, 6, 9 și 18;

Divizorii comuni ai lui 12 și 18 sunt: 1, 2, 3 și 6;

În acest caz, cel mai mare divizor comun al celor două numere este 6, ca atare avem formula (12, 18) = 6.

Cum se determină CMMDC

Determinarea celui mai mare divizor comun al două numere naturale se învață încă din ciclul gimnazial și face parte din lecțiile de matematică de complexitate medie, care ajută elevii să își dezvolte gândirea analitică și abstractă.

Există mai multe metode prin care poate fi determinat cel mai mare divizor comun. Metoda clasică, pe care o învățăm adesea prima la școală, este descompunerea în factori primi. O altă metodă presupune scăderi repetate, urmate de împărțiri repetate, cunoscută și sub denumirea de algoritmul lui Euclid.

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ă). Ulterior aceștia se înmulţesc între ei.

Spre exemplu, să aflăm cel mai mare divizor comun pentru numerele 24 și 60.

Descompunerea în factori primi:
24 = 2³ × 3
60 = 2² × 3 × 5
Aflarea factorilor comuni: 2 și 3
Puterea minimă: 2²și 3¹
Înmulțirea: 2² × 3 = 12
În concluzie, CMMDC pentru numerele 24 și 60 este 12. (24, 60) = 12

Dacă încercăm să vizualizăm geometric acest exemplu, ne putem imagina un dreptunghi cu lățimea de 24 de centimetri și lungimea de 60 de centimetri.

Acest dreptunghi se poate diviza în pătrate de: 1-pe-1, 2-pe-2, 3-pe-3, 6-pe-6 sau 12-pe-12. Deci pătratele cele mai mari vor avea latura de 12 centimetri, iar acesta este cel mai mare divizor comun al lui 24 și 60.

Așadar, dreptunghiul de 24-pe-60 poate fi împărțit într-un grid de 12-pe-12 pătrate, cu două pătrate pe o latură (24/12 = 2) și cinci pătrate pe cealaltă (60/12 = 5).

Un alt exemplu:

Să calculăm cel mai mare divizor comun al numerelor 126 și 180.

descompunem în factori primi numerele 126 și 180:

126 = 2 × 3²× 7

180 = 2²× 3²× 5

considerăm doar factorii comuni la puterea cea mai mică, luați o singură dată, adică 2 și 3². Produsul obținut este 2 × 3²= 18; acesta este cel mai mare divizor comun al numerelor 126 și 180.

Cel mai mare divizor comun și numerele prime între ele

În cazul în care avem două numere prime între ele, cum sunt 12 și 25, știm că numărul 1 este singurul lor divizor comun. Ca atare, (12, 25) = 1

Dacă CMMDC (a, b) = 1, atunci a și b sunt prime între ele. Această proprietate nu depinde de primalitatea lui a și a lui b.

De exemplu, numerele 6 și 35 nu sunt numere prime, deoarece ambele au doi factori: 6 = 2 × 3 și 35 = 5 × 7. Cu toate acestea, 6 și 35 sunt prime între ele. Niciun alt număr natural în afară de 1 nu divide nici pe 6, nici pe 35, deoarece ele nu au niciun factor prim în comun.

CMMDC și algortimul lui Euclid

Algoritmul lui Euclid este o metodă eficientă de calcul al celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a descris în Cărțile VII și X din Elementele.

CMMDC a două numere este cel mai mare număr care le divide pe ambele. Algoritmul lui Euclid exploatează observația că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare.

De exemplu, 21 este CMMDC al numerelor 252 și 105 (252 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 și 105 este tot 21.

Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul.

Exemplu

252 : 105 = 2, rest 42

105 : 42 = 2, rest 21

42 : 21 = 2, rest 0

În aceste condiții, cmmdc (252, 105) = 21
Inversând pașii algoritmului lui Euclid, CMMDC se poate exprima sub formă de suma celor două numere inițiale, fiecare înmulțite cu un întreg pozitiv sau negativ, de exemplu: 21 = 5 × 105 + (−2) × 252.

Metoda scăderilor repetate

Este o metodă mai veche, inspirată tot de algoritmul lui Euclid, este mai ușor de înțeles și folosită mai des în școală.

Prin această metodă 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: cel mai mare divizor comun (28, 20) = ?

Vom scădea succesiv numărul mai mic din cel mai mare:

28 – 20 = 8
20 – 8 = 12
12 – 8 = 4
8 – 4 = 4
4 – 4 = 0
Datorită faptului că rezultatul scăderii este nul, cmmdc (28, 20) = 4

De ce este atât de eficient algoritmul lui Euclid

Prima descriere rămasă a algoritmului lui Euclid în lucrarea Elementele (c. 300 î.e.n.), este unul dintre cei mai vechi algoritmi numerici încă utilizați. Algoritmul original a fost descris doar pentru numere naturale și lungimi geometrice (numere reale), dar algoritmul a fost generalizat în secolul al XIX-lea și la alte tipuri de numere, cum ar fi polinoamele de o variabilă, sau la noțiuni moderne de algebră abstractă, cum ar fi inelele euclidiene.

Algoritmul lui Euclid are numeroase aplicații practice și teoretice. Este un element cheie al algoritmului RSA, primul algoritm folosit ca metodă de criptare cu chei publice în comerțul electronic și semnătura electronică.

Algoritmul lui Euclid calculează eficient CMMDC a două numere oricât de mari sunt, deoarece nu necesită niciodată un număr de pași mai mare decât de cinci ori decât numărul de cifre (în bază 10) al celui mai mic întreg.