Massimo comun divisore

Da Wikipedia, l'enciclopedia libera.

In matematica, il massimo comun divisore (M.C.D.) di due numeri interi a e b che non siano entrambi uguali a zero, è il numero naturale più grande per il quale possono entrambi essere divisi.

Il massimo comune divisore tra i due numeri a e b viene indicato con MCD(ab), o più semplicemente (ab). Ad esempio, MCD(12, 18) = 6, MCD(4, 14) = 2 e MCD(5, 0) = 5.

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 sorgente]

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 MCD(18,84) si scompongono dapprima i due numeri in fattori primi, ottenendo 18 = 2·32 e 84 = 22·3·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 MCD(18,84)=6. Se non ci sono fattori primi comuni, il MCD è 1 e i due numeri sono detti coprimi; ad esempio 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 sorgente]

  • Ogni divisore comune di a e b è un divisore di MCD(ab).
  • MCD(ab), 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 = a·p + b·q dove p e q sono interi. Questa espressione viene chiamata identità di Bézout.
  • Se a divide il prodotto b·c, e MCD(ab) = d, allora a/d divide c.
  • Se m è un intero non nullo, allora MCD(m·am·b) = m·MCD(ab) e MCD(a + m·bb) = MCD(ab). Se m è un divisore comune diverso da zero di a e b, allora MCD(a/mb/m) = MCD(ab)/m.
  • Il MCD di tre numeri può essere calcolato come MCD(abc) = MCD(MCD(ab), c) = MCD(a, MCD(bc)). Quindi il MCD è una operazione associativa.
MCD(ab)·mcm(ab) = a·b.
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.
MCD(a, mcm(bc)) = mcm(MCD(ab), MCD(ac))
mcm(a, MCD(bc)) = MCD(mcm(ab), mcm(ac)).
  • È utile definire MCD(0, 0) = 0 e 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 MCD(ab) può essere interpretato come il numero di punti con coordinate intere sulla retta che passa per i punti (0, 0) e (ab), escludendo il punto (0, 0).

Il MCD in anelli commutativi[modifica | modifica sorgente]

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 d·x = a e d·y = 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 p a + q b, 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 sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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