Massimo comun divisore

Grafico che rappresenta il massimo comun divisore dei numeri da 1 a 10

In matematica il massimo comun divisore (o massimo comune divisore) di due numeri interi $a$ e $b$, che non siano entrambi uguali a zero, indicato con $\mathrm{MCD}(a,b)$, è il numero naturale più grande per il quale entrambi possono essere divisi esattamente. Se i numeri $a$ e $b$ sono uguali a $0$, allora si pone $\mathrm{MCD}(a,b)=0$.

Ad esempio, $\mathrm{MCD}(12,18)=6$, $\mathrm{MCD}(4,14)=2$ e $\mathrm{MCD}(5,0)=5$.

Spesso il massimo comun divisore è indicato più semplicemente con $(a,b)$.

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 (anche se non sono numeri primi).

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

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

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

Calcolo del 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 $\mathrm{MCD}(18,84)$ si scompongono dapprima i due numeri in fattori primi, ottenendo $18=2\cdot 3^2$ e $84=2^2\cdot 3\cdot 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$, quindi che $\mathrm{MCD}(18,84)=6$. Se non ci sono fattori primi comuni, il MCD è $1$ e i due numeri sono detti coprimi; ad esempio: $\mathrm{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 $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 comun divisore.

Proprietà

• Ogni divisore comune di $a$ e $b$ è un divisore di $\mathrm{MCD}(a,b)$.
• Il $\mathrm{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=ap+bq$ dove $p$ e $q$ sono interi. Questa espressione viene chiamata identità di Bézout.
• Se $a$ divide il prodotto $bc$, e $\mathrm{MCD}(a,b)=d$, allora $a/d$ divide $c$.
• Se $m$ è un intero non nullo, allora $\mathrm{MCD}(ma,mb)=m\mathrm{MCD}(a,b)$ e $\mathrm{MCD}(a+mb,b)=\mathrm{MCD}(a,b)$. Se $m$ è un divisore comune diverso da zero di $a$ e $b$, allora $\mathrm{MCD}(a/m,b/m)=\mathrm{MCD}(a,b)/m$.
• Il MCD è una funzione moltiplicativa, cioè se $a_1$ e $a_2$ sono primi tra loro, allora $\mathrm{MCD}(a_1{a}_2,b)=\mathrm{MCD}(a_1,b)\mathrm{MCD}(a_2,b)$.
• Il MCD di tre numeri può essere calcolato come $\mathrm{MCD}(a,b,c)=\mathrm{MCD}(\mathrm{MCD}(a,b),c)=\mathrm{MCD}(a,\mathrm{MCD}(b,c))$. Quindi il MCD è un'operazione associativa.
• Il $\mathrm{MCD}(a,b)$ è legato al minimo comune multiplo $\mathrm{mcm}(a,b)$: si ha

$\mathrm{MCD}(a,b)\cdot \mathrm{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:

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

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

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

Il MCD in anelli commutativi

Il massimo comun 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 $dx=a$ e $dy=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}],a=4=2\cdot 2=(1+\sqrt{-3})(1-\sqrt{-3}),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 $pa+qb$, 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 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

Bibliografia

• Template:Cita libro

Voci correlate

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

Collegamenti esterni

• Template:Collegamenti esterni
• Template:FOLDOC
• Template:Garzanti
• Template:Cita web
• Template:Cita web
• Template:Cita web
• Template:Cita web