Massimo comun divisore

In matematica, il massimo comune divisore (M.C.D.) di due numeri interi a e b che non siano entrambi uguali a zero, è il numero naturale più grande per il quale possono entrambi essere divisi.

Il massimo comun divisore tra i due numeri a e b viene indicato con MCD(a, b), o più semplicemente (a, b). Ad esempio, MCD(12, 18) = 6, MCD(−4, 14) = 2 e MCD(5, 0) = 5.

Due numeri si dicono coprimi o primi tra loro se il loro massimo comun divisore è uguale a 1. Per esempio, i numeri 9 e 28 sono primi tra loro (ma non sono numeri primi).

Il massimo comun divisore è utile per ridurre una frazione ai minimi termini. Per esempio nella seguente frazione:

${42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}$

è stato semplificato il fattore 14, il massimo comun divisore tra 42 e 56.

Calcolo del M.C.D (Massimo Comune Divisore)

Il massimo comune divisore può essere calcolato, in linea di principio, determinando la scomposizione in fattori primi dei due numeri dati e moltiplicando i fattori comuni, considerati una sola volta con il loro minimo esponente. Per esempio, per calcolare il MCD(18,84) si scompongono dapprima i due numeri in fattori primi, ottenendo 18 = 2·3² e 84 = 2²·3·7, e poi si considerano i fattori comuni con esponente più piccolo ai due numeri, 2 e 3: entrambi compaiono con esponente minimo uguale a 1, e quindi si ottiene che MCD(18,84)=6. Se non ci sono fattori primi comuni, il MCD è 1 e i due numeri sono detti coprimi; ad esempio MCD(242,375)=1.

Questo metodo è utilizzabile, nella pratica, solo per numeri molto piccoli: la scomposizione in fattori primi di un numero richiede in generale troppo tempo.

Un metodo molto più efficiente è fornito dall'algoritmo di Euclide: si divide 84 per 18 ottenendo un quoziente di 4 e un resto di 12. Poi si divide 18 per 12 ottenendo un quoziente di 1 e un resto di 6. Infine si divide 12 per 6 ottenendo un resto di 0, il che significa che 6 è il massimo comune divisore.

Proprietà

• Ogni divisore comune di a e b è un divisore di MCD(a, b).

• MCD(a, b), dove a e b non sono contemporaneamente uguali a zero, può essere definito in modo alternativo ed equivalente come il più piccolo intero positivo d che può essere scritto nella forma d = a·p + b·q dove p e q sono interi. Questa espressione viene chiamata identità di Bézout.

• Se a divide il prodotto b·c, e MCD(a, b) = d, allora a/d divide c.

• Se m è un intero non nullo, allora MCD(m·a, m·b) = m·MCD(a, b) e MCD(a + m·b, b) = MCD(a, b). Se m è un divisore comune diverso da zero di a e b, allora MCD(a/m, b/m) = MCD(a, b)/m.

• Il MCD è una funzione moltiplicativa nel senso seguente: se a₁ e a₂ sono primi tra loro, allora MCD(a₁·a₂, b) = MCD(a₁, b)·MCD(a₂, b).

• Il MCD di tre numeri può essere calcolato come MCD(a, b, c) = MCD(MCD(a, b), c) = MCD(a, MCD(b, c)). Quindi il MCD è una operazione associativa.

• MCD(a, b) è legato al minimo comune multiplo mcm(a, b): si ha

MCD(a, b)·mcm(a, b) = a·b.

Questa formula viene usata spesso per calcolare il minimo comune multiplo: si calcola prima il MCD con l'algoritmo di Euclide e poi si divide il prodotto dei due numeri dati per il loro MCD.

• Vale la seguente proprietà distributiva: rolling

MCD(a, mcm(b, c)) = mcm(MCD(a, b), MCD(a, c))

mcm(a, MCD(b, c)) = MCD(mcm(a, b), mcm(a, c)).

• È utile definire MCD(0, 0) = 0 e mcm(0, 0) = 0 perché in questo modo i numeri naturali diventano un reticolo completo distributivo con MCD e mcm come operazioni. Questa estensione è compatibile anche con la generalizzazione per gli anelli commutativi data più sotto.

• In un sistema di coordinate cartesiane il MCD(a, b) può essere interpretato come il numero di punti con coordinate intere sulla retta che passa per i punti (0, 0) e (a, b), escludendo il punto (0, 0).

Il MCD in anelli commutativi

Il massimo comune divisore può essere definito in maniera più generale per gli elementi di un anello commutativo arbitrario.

Se R è un anello commutativo e a e b appartengono a R, allora un elemento d di R è chiamato divisore comune di a e b se divide sia a che b (e cioè se esistono due elementi x e y in R tali che d·x = a e d·y = b). Se d è un divisore comune di a e b, e ogni divisore comune di a e b divide d, allora d viene chiamato un massimo comun divisore di a e b.

Si noti che, secondo questa definizione, due elementi a e b possono avere più di un massimo comun divisore, oppure nessuno. Ma se R è un dominio di integrità allora due qualsiasi MCD di a e b devono essere elementi associati. Inoltre, se R è un dominio a fattorizzazione unica, allora due qualunque elementi hanno un MCD. Se R è un anello euclideo allora i MCD possono essere calcolati con una variante dell'algoritmo euclideo.

Quello che segue è un esempio di un dominio di integrità con due elementi che non ammettono un MCD:

$R = \mathbb{Z}[\sqrt{-3}],\quad a = 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}),\quad b = (1+\sqrt{-3})\cdot 2$

Gli elementi $1+\sqrt{-3}$ e $2$ sono due "divisori comuni massimali" (cioè ogni divisore comune che è multiplo di 2 è associato a 2, e lo stesso vale per $1+\sqrt{-3}$), ma non sono associati, quindi non esiste il massimo comun divisore di a e b.

Analogamente alla proprietà di Bezout si può considerare, in un qualunque anello commutativo, la collezione di elementi nella forma $p a + q b$, dove p e q variano all'interno dell'anello. Si ottiene l'ideale generato da a e b, che viene denotato semplicemente con $(a,b)$. In un anello i cui ideali sono tutti principali (un anello ad ideali principali, "principal ideal domain" o PID), questo ideale sarà identico all'insieme dei multipli di qualche elemento d dell'anello; allora questo d è un massimo comun divisore di a e b. Ma l'ideale $(a,b)$ può essere utile anche quando non c'è nessun MCD di a e b (in effetti, Ernst Kummer usò questo ideale come sostituto del MCD nel suo studio dell'ultimo teorema di Fermat, anche se lo considerò come l'insieme di multipli di un qualche ipotetico, o ideale, elemento d dell'anello, da qui proviene il termine ideale).

Pseudocodice

In pseudocodice, l'algoritmo può essere esplicitato sia come algoritmo ricorsivo che in modo iterativo: nel primo caso si ha semplicemente

1. a=|a|, b=|b|
2. ordina a e b in modo tale che a > b
3. se b=0 allora MCD(a,b)=a; altrimenti MCD(a,b)=MCD(b,a mod b)

L'algoritmo iterativo può invece essere descritto come

1. a=|a|, b=|b|
2. ordina a e b in modo tale che a > b
3. mentre b è diverso da 0
   1. t=b
   2. b=a mod b
   3. a=t
4. MCD(a,b)=a

Voci correlate

• Minimo comune multiplo (m.c.m)
• Criteri di divisibilità

Collegamenti esterni

• (IT) Scomposizione in fattori primi e calcolo del MCD online
• (EN) Calcolo del MCD online
• (EN) Calcolo del MCD online
• (EN) Un algoritmo per il calcolo veloce del MCD
• Massimo comun divisore in Tesauro del Nuovo Soggettario. BNCF, marzo 2013

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica