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 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 MCD⁡(a,b)=0.

Ad esempio:

MCD⁡(12,18)=6,MCD⁡(4,14)=2,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:

4256=3⋅144⋅14=34

è 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 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, quindi 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 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à

MCD⁡(ma,mb)=mMCD⁡(a,b),
MCD⁡(a+mb,b)=MCD⁡(a,b).
Se m è un divisore comune diverso da zero di a e b, allora
MCD⁡(a/m,b/m)=MCD⁡(a,b)/m.
MCD⁡(a1a2,b)=MCD⁡(a1,b)MCD⁡(a2,b).
MCD⁡(a,b,c)=MCD⁡(MCD⁡(a,b),c)=MCD⁡(a,MCD⁡(b,c)).
Quindi il MCD è un'operazione associativa.
MCD⁡(a,b)⋅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.
MCD⁡(a,mcm⁡(b,c))=mcm⁡(MCD⁡(a,b),MCD⁡(a,c)),
mcm⁡(a,MCD⁡(b,c))=MCD⁡(mcm⁡(a,b),mcm⁡(a,c)).

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.

Ad esempio, nel dominio di integrità R=ℤ[−3], i due elementi

a=4=2⋅2=(1+−3)(1−−3)eb=(1+−3)⋅2

non ammettono un MCD, infatti 1+−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+−3), ma non sono associati tra loro, quindi non esiste il massimo comun divisore di a e b.

Analogamente alla proprietà di Bézout 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

Note

  1. ↑ Hasse, p. 10.

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Controllo di autoritàThesaurus BNCF 34805
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica