Massimo comun divisore
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c5/Greatest_common_divisor_chart.svg/350px-Greatest_common_divisor_chart.svg.png)
In matematica il massimo comun divisore (o massimo comune divisore) di due numeri interi e , che non siano entrambi uguali a zero, si indica con ed è il numero naturale più grande per il quale possono essere divisi entrambi. Se i numeri e sono uguali a , allora si pone [1].
Ad esempio, , e .
Spesso il massimo comun divisore è indicato più semplicemente con .
Due numeri si dicono coprimi, o primi tra loro, se il loro massimo comun divisore è uguale a . Per esempio, i numeri e 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:
è stato semplificato il fattore , il massimo comun divisore tra e .
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 si scompongono dapprima i due numeri in fattori primi, ottenendo e , e poi si considerano i fattori comuni con esponente più piccolo ai due numeri, e : entrambi compaiono con esponente minimo uguale a , e quindi si ottiene che . Se non ci sono fattori primi comuni, il MCD è e i due numeri sono detti coprimi; ad esempio: .
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 per ottenendo un quoziente di e un resto di . Poi si divide per ottenendo un quoziente di e un resto di . Infine si divide per ottenendo un resto di , il che significa che è il massimo comun divisore.
Proprietà
- Ogni divisore comune di e è un divisore di .
- Il , dove e non sono contemporaneamente uguali a zero, può essere definito in modo alternativo ed equivalente come il più piccolo intero positivo che può essere scritto nella forma dove e sono interi. Questa espressione viene chiamata identità di Bézout.
- Se divide il prodotto , e , allora divide .
- Se è un intero non nullo, allora e . Se è un divisore comune diverso da zero di e , allora .
- Il MCD è una funzione moltiplicativa, cioè se e sono primi tra loro, allora .
- Il MCD di tre numeri può essere calcolato come . Quindi il MCD è un'operazione associativa.
- Il è legato al minimo comune multiplo : si ha
- .
- 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:
- .
- È utile definire e 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 può essere interpretato come il numero di punti con coordinate intere sul segmento di retta congiungente i punti e , escludendo il punto .
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 è un anello commutativo e e appartengono a , allora un elemento di è chiamato divisore comune di e se divide sia che (e cioè se esistono due elementi e in tali che e ). Se è un divisore comune di e , e ogni divisore comune di e divide , allora viene chiamato un massimo comun divisore di e .
Si noti che, secondo questa definizione, due elementi e possono avere più di un massimo comun divisore, oppure nessuno. Ma se è un dominio di integrità allora due qualsiasi MCD di e devono essere elementi associati. Inoltre, se è un dominio a fattorizzazione unica, allora due qualunque elementi hanno un MCD. Se è 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:
Gli elementi e sono due "divisori comuni massimali" (cioè ogni divisore comune che è multiplo di è associato a , e lo stesso vale per ), ma non sono associati, quindi non esiste il massimo comun divisore di e .
Analogamente alla proprietà di Bezout si può considerare, in un qualunque anello commutativo, la collezione di elementi nella forma , dove e variano all'interno dell'anello. Si ottiene l'ideale generato da e , che viene denotato semplicemente con . 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 dell'anello; allora questo è un massimo comun divisore di e . Ma l'ideale può essere utile anche quando non c'è nessun MCD di e (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 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
- a=|a|, b=|b|
- ordina a e b in modo tale che a > b
- 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
- a=|a|, b=|b|
- ordina a e b in modo tale che a > b
- finché b è diverso da 0
- t=b
- b=a mod b
- a=t
- MCD(a,b)=a
Note
- ^ Hasse, p. 10.
Bibliografia
- (EN) Helmut Hasse, Number Theory, 3ª ed., New York, Springer-Verlag, 1980, ISBN 0-387-08275-1.
Voci correlate
Altri progetti
Altri progetti
- Wikizionario
- Wikimedia Commons
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) 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.
V · D · M | ||
---|---|---|
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 |
Controllo di autorità | Thesaurus BNCF 34805 |
---|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)