massimo comune divisore

massimo comune divisore

massimo comune divisore (in simbolo mcd) tra due numeri interi a, b è il numero intero M che soddisfa le due seguenti proprietà:

• M divide a e b;

• se c è un intero che divide a e b, allora c divide M. Il massimo comune divisore tra due interi a e b esiste sempre ed è unico, a meno del segno; è il più grande numero che li divide tutti e quindi il massimo fra i sottomultipli comuni. Convenzionalmente, esso viene preso con il segno positivo ed è indicato con il simbolo mcd(a, b), oppure, nella notazione inglese, con gcd(a, b). Il massimo comune divisore tra due interi a e b può essere calcolato applicando l’algoritmo di → Euclide; alternativamente, note le due fattorizzazioni in numeri primi di a e b, esso può essere calcolato effettuando il prodotto di tutti i fattori primi comuni ad a e b, elevati al minimo esponente con cui essi compaiono nelle due fattorizzazioni: per esempio, poiché 264 = 2³ ⋅ 3 ⋅ 11 e 2420 = 2² ⋅ 5 ⋅ 11², si ricava mcd(264, 2420) = 2² ⋅ 11 = 44. Tra il massimo comune divisore M e il → minimo comune multiplo m di due interi a e b sussiste la relazione ab = mM. Una situazione analoga si ha se, invece di numeri interi, si considerano polinomi (a coefficienti in un qualsiasi campo K): anche in questo caso il massimo comune divisore tra due polinomi p(x) e q(x), definito dalle stesse proprietà formali enunciate nel caso di due interi, esiste sempre ed è unico, a meno di un fattore invertibile, vale a dire costante; convenzionalmente, si considera il polinomio monico, indicato con il simbolo mcd(p, q). Analogamente al caso di due numeri interi, il massimo comune divisore tra due polinomi p e q può essere calcolato applicando l’algoritmo di Euclide oppure a partire da due fattorizzazioni note in polinomi irriducibili dei polinomi dati, effettuando il prodotto dei fattori comuni a p e q elevati al minimo esponente con cui compaiono nelle due fattorizzazioni.

Più in generale, la nozione di massimo comune divisore è definibile in un qualsiasi dominio d’integrità D; non sempre però esso esiste. Se però D è un dominio a fattorizzazione unica, allora il massimo comune divisore tra due elementi dell’anello esiste sempre ed è unico, a meno di un fattore invertibile. Come nei casi precedenti, dati due elementi di D, il loro massimo comune divisore è sempre calcolabile a partire da due fattorizzazioni note degli elementi dati; se in aggiunta D è un dominio euclideo, allora l’algoritmo di Euclide, opportunamente riformulato in tale contesto, offre un metodo alternativo per il calcolo.