Massimo comun divisore

Da Wikipedia, l'enciclopedia libera.

In matematica, il 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 entrambi essere divisi. Se entrambi i numeri e sono uguali a , allora si pone [1].

Ad esempio, , e .

Spesso il massimo comun divisore è più semplicemente indicato 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 (ma 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 divisore[modifica | modifica wikitesto]

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à[modifica | modifica wikitesto]

  • 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 nel senso seguente: 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 sulla retta che passa per i punti e , escludendo il punto .

Il MCD in anelli commutativi[modifica | modifica wikitesto]

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

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

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