Massimo comun divisore

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

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

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

Due numeri si dicono coprimi, o primi tra loro, se il loro massimo comun divisore è uguale a ${\displaystyle 1}$. Per esempio, i numeri ${\displaystyle 9}$ e ${\displaystyle 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:

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

è stato semplificato il fattore ${\displaystyle 14}$, il massimo comun divisore tra ${\displaystyle 42}$ e ${\displaystyle 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 ${\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}$, e quindi si ottiene 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 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 ${\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.

Proprietà

• 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 MCD in anelli commutativi

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).

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

Note

Bibliografia

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

Voci correlate

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

Altri progetti

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

Collegamenti esterni

• 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, Massimo comun divisore, su MathWorld, Wolfram Research.
• (EN) Massimo comun divisore, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) greatest common divisor, in Free On-line Dictionary of Computing, Denis Howe. 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.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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