Apri il menu principale

Massimo comun divisore

In matematica il massimo comun 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 comune divisoreModifica

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 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àModifica

  • 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 è una 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.
 
 .
  • È 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 commutativiModifica

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

PseudocodiceModifica

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. mentre b è diverso da 0
    1. t=b
    2. b=a mod b
    3. a=t
  4. MCD(a,b)=a

NoteModifica

  1. ^ Hasse, p. 10.

BibliografiaModifica

Voci correlateModifica

Collegamenti esterniModifica

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