Massimo comun divisore

Da Wikipedia, l'enciclopedia libera.

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

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

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

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

Il massimo comune 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.[modifica | modifica wikitesto]

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 \operatorname{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, e quindi si ottiene che \operatorname{MCD}(18,84)=6. Se non ci sono fattori primi comuni, il MCD è 1 e i due numeri sono detti coprimi; ad esempio \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 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à[modifica | modifica wikitesto]

  • Ogni divisore comune di a e b è un divisore di \operatorname{MCD}(a,b).
  • Il 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 \operatorname{MCD}(a,b)=d, allora a/d divide c.
  • Se m è un intero non nullo, allora \operatorname{MCD}(ma,mb)=m\operatorname{MCD}(a,b) e \operatorname{MCD}(a+mb,b)=\operatorname{MCD}(a,b). Se m è un divisore comune diverso da zero di a e b, allora \operatorname{MCD}(a/m,b/m)=\operatorname{MCD}(a,b)/m.
  • Il MCD di tre numeri può essere calcolato come \operatorname{MCD}(a,b,c)=\operatorname{MCD}(\operatorname{MCD}(a,b),c)=\operatorname{MCD}(a,\operatorname{MCD}(b,c)). Quindi il MCD è una operazione associativa.
\operatorname{MCD}(a,b)\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.
\operatorname{MCD}(a,\operatorname{mcm}(b,c))=\operatorname{mcm}(\operatorname{MCD}(a,b),\operatorname{MCD}(a,c))
\operatorname{mcm}(a,\operatorname{MCD}(b,c))=\operatorname{MCD}(\operatorname{mcm}(a,b),\operatorname{mcm}(a,c)).
  • È utile definire \operatorname{MCD}(0,0)=0 e \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 \operatorname{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[modifica | modifica wikitesto]

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 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}],\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 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[modifica | modifica wikitesto]

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

Note[modifica | modifica wikitesto]

  1. ^ Hasse, p. 10

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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