Massimo comun divisore

Il massimo comun 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 esponente più piccolo. Per esempio, per calcolare il ${\displaystyle \operatorname {MCD} (18,84)}$  si scompongono dapprima i due numeri in fattori primi, ottenendo ${\displaystyle 18=2\cdot 3^{2}}$  e ${\displaystyle 84=2^{2}\cdot 3\cdot 7}$ , e poi si considerano i fattori comuni con esponente più piccolo ai due numeri, ${\displaystyle 2}$  e ${\displaystyle 3}$ : entrambi compaiono con esponente minimo uguale a ${\displaystyle 1}$ , quindi che ${\displaystyle \operatorname {MCD} (18,84)=6}$ . Se non ci sono fattori primi comuni, il MCD è ${\displaystyle 1}$  e i due numeri sono detti coprimi; ad esempio: ${\displaystyle \operatorname {MCD} (242,375)=1}$ .

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

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

• Ogni divisore comune di ${\displaystyle a}$  e ${\displaystyle b}$  è un divisore di ${\displaystyle \operatorname {MCD} (a,b)}$ .
• Il ${\displaystyle \operatorname {MCD} (a,b)}$ , dove ${\displaystyle a}$  e ${\displaystyle b}$  non sono contemporaneamente uguali a zero, può essere definito in modo alternativo ed equivalente come il più piccolo intero positivo ${\displaystyle d}$  che può essere scritto nella forma ${\displaystyle d=ap+bq}$  dove ${\displaystyle p}$  e ${\displaystyle q}$  sono interi. Questa espressione viene chiamata identità di Bézout.
• Se ${\displaystyle a}$  divide il prodotto ${\displaystyle bc}$ , e ${\displaystyle \operatorname {MCD} (a,b)=d}$ , allora ${\displaystyle a/d}$  divide ${\displaystyle c}$ .
• Se ${\displaystyle m}$  è un intero non nullo, allora ${\displaystyle \operatorname {MCD} (ma,mb)=m\operatorname {MCD} (a,b)}$  e ${\displaystyle \operatorname {MCD} (a+mb,b)=\operatorname {MCD} (a,b)}$ . Se ${\displaystyle m}$  è un divisore comune diverso da zero di ${\displaystyle a}$  e ${\displaystyle b}$ , allora ${\displaystyle \operatorname {MCD} (a/m,b/m)=\operatorname {MCD} (a,b)/m}$ .
• Il MCD è una funzione moltiplicativa, cioè se ${\displaystyle a_{1}}$  e ${\displaystyle a_{2}}$  sono primi tra loro, allora ${\displaystyle \operatorname {MCD} (a_{1}a_{2},b)=\operatorname {MCD} (a_{1},b)\operatorname {MCD} (a_{2},b)}$ .
• Il MCD di tre numeri può essere calcolato come ${\displaystyle \operatorname {MCD} (a,b,c)=\operatorname {MCD} (\operatorname {MCD} (a,b),c)=\operatorname {MCD} (a,\operatorname {MCD} (b,c))}$ . Quindi il MCD è un'operazione associativa.
• Il ${\displaystyle \operatorname {MCD} (a,b)}$  è legato al minimo comune multiplo ${\displaystyle \operatorname {mcm} (a,b)}$ : si ha

${\displaystyle \operatorname {MCD} (a,b)\cdot \operatorname {mcm} (a,b)=ab}$ .

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:

${\displaystyle \operatorname {MCD} (a,\operatorname {mcm} (b,c))=\operatorname {mcm} (\operatorname {MCD} (a,b),\operatorname {MCD} (a,c))}$ 

${\displaystyle \operatorname {mcm} (a,\operatorname {MCD} (b,c))=\operatorname {MCD} (\operatorname {mcm} (a,b),\operatorname {mcm} (a,c))}$ .

• È utile definire ${\displaystyle \operatorname {MCD} (0,0)=0}$  e ${\displaystyle \operatorname {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 ${\displaystyle \operatorname {MCD} (a,b)}$  può essere interpretato come il numero di punti con coordinate intere sul segmento di retta congiungente i punti ${\displaystyle (0,0)}$  e ${\displaystyle (a,b)}$ , escludendo il punto ${\displaystyle (0,0)}$ .

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

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

Si noti che, secondo questa definizione, due elementi ${\displaystyle a}$  e ${\displaystyle b}$  possono avere più di un massimo comun divisore, oppure nessuno. Ma se ${\displaystyle R}$  è un dominio di integrità allora due qualsiasi MCD di ${\displaystyle a}$  e ${\displaystyle b}$  devono essere elementi associati. Inoltre, se ${\displaystyle R}$  è un dominio a fattorizzazione unica, allora due qualunque elementi hanno un MCD. Se ${\displaystyle 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:

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

Analogamente alla proprietà di Bezout si può considerare, in un qualunque anello commutativo, la collezione di elementi nella forma ${\displaystyle pa+qb}$ , dove ${\displaystyle p}$  e ${\displaystyle q}$  variano all'interno dell'anello. Si ottiene l'ideale generato da ${\displaystyle a}$  e ${\displaystyle b}$ , che viene denotato semplicemente con ${\displaystyle (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 ${\displaystyle d}$  dell'anello; allora questo ${\displaystyle d}$  è un massimo comun divisore di ${\displaystyle a}$  e ${\displaystyle b}$ . Ma l'ideale ${\displaystyle (a,b)}$  può essere utile anche quando non c'è nessun MCD di ${\displaystyle a}$  e ${\displaystyle 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 ${\displaystyle d}$  dell'anello, da qui proviene il termine ideale).

In pseudocodice, l'algoritmo può essere esplicitato sia come algoritmo ricorsivo sia 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. finché b è diverso da 0
   1. t=b
   2. b=a mod b
   3. a=t
4. MCD(a,b)=a

• (EN) Helmut Hasse, Number Theory, 3ª ed., New York, Springer-Verlag, 1980, ISBN 0-387-08275-1.

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

•   Wikizionario contiene il lemma di dizionario «massimo comune divisore»
•   Wikimedia Commons contiene immagini o altri file sul massimo comun divisore

• massimo comun divisore, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.  
• M.C.D., su sapere.it, De Agostini.  
• Massimo comun divisore, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.  
• (EN) greatest common divisor, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  
• (EN) Eric W. Weisstein, Greatest Common Divisor, su MathWorld, Wolfram Research.  
• (EN) Greatest common divisor, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.  
• (EN) Denis Howe, greatest common divisor, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• M.C.D., in Grande Dizionario di Italiano, Garzanti Linguistica.
• Scomposizione in fattori primi e calcolo del MCD online, su blia.it.
• (EN) Calcolo del MCD online, su easycalculation.com.
• (EN) Calcolo del MCD online, su wims.unice.fr.
• (EN) Un algoritmo per il calcolo veloce del MCD, su nist.gov.