Algoritmo di euclide

Massimo comun divisore

L'algoritmo di Euclide serve per il calcolo del massimo comun divisore tra e , dove non sono entrambi nulli.


Definizione

Un intero si dice un massimo comun divisore tra e , se e (cioè se è un comun divisore) inoltre se e , allora ( è massimo).

 


Definizione

Si dice che divide () se è multiplo di , cioè

 


Con questa notazione, è vero che .


Proposizione

Se sono entrambi massimi comun divisori di e , allora o , o .

 


Dimostrazione

è un massimo comun divisore quindi per definizione , ma anche è un massimo comun divisore quindi . Allora

ma quindi, inserendo l'espressione di in quella di , si ha:
e semplificando per , . Siccome sono interi, il loro prodotto è 1 se e solo se oppure .

 


Per convenzione, prendiamo come massimo comun divisore quello positivo. Ad esempio

Osservazioni preliminari per l'algoritmo

Considero interi non entrambi nulli.


Osservo che la definizione di massimo comun divisore è simmetrica rispetto ad e , quindi

e cambiando segni ai termini l'M.C.D. non cambia. Quindi basta considerare il caso in cui e sono non negativi.


Considero il caso in cui . Allora

Ci si riduce quindi al caso in cui e sono entrambi maggiori di 0.

Algoritmo di Euclide

Considero una tabella con tre colonne: le prime due righe sono i vettori e e costruiamo le altre righe. Possiamo scrivere

La terza riga si costruisce sottraendo alla prima riga la seconda riga per volte, e ottengo
infatti

Proposizione

.

 


Dimostrazione

Mostro che se pongo e , segue che . Infatti

Segue che e , allora . Per la stessa ragione , infatti
Segue che , , e allora . Per le due relazioni e , segue che .

 


La tabella costruita finora è

Tenendo conto che , per costruire le altre righe itero l'algoritmo applicandolo a ed , se , la quarta riga si ottiene sottraendo alla seconda riga la terza moltiplicata per , e quindi come quarta riga avrò , e così via, finché non si ottiene un resto uguale a 0.


Esempio

Sia e . Allora determino ed a ogni passo dell'algoritmo.

 


Esempio

Sia e .

Se inizialmente non si pone , il primo passo riordina i numeri, e poi si continua come prima.

 


Considero la tabella costruita e osservo che vale la seguente relazione: per ogni riga della forma , si ha che . Infatti, ad esempio, per le prime tre righe si ha:

Suppongo di continuare con l'algoritmo di euclide. Su tutte le righe da costruire, si preserva la proprietà che il primo coefficiente della riga moltiplicato per sommato al secondo moltiplicato per è uguale al terzo elemento della riga.


Esempio

Costruisco la tabella relativa all'esempio precedente, , . Aggiungo una colonna iniziale che serve solo a me, in cui annoto quoziente e resto delle divisioni successive eseguite, in questa colonna, nell'i-esima riga in particolare metto quoziente e resto della divisione tra il terzo elemento della riga e quello della riga .


Per costruire l'n-esima riga, moltiplico la riga per il quoziente che compare su quella riga, e la sottraggo alla . Quindi

Osservo che sull'ultima riga ho tutti i resti.


Vale la proprietà per le righe della tabella dimostrata prima, infatti, considerando ad esempio la terza riga

 

Identità di Bezout

Teorema

Dati interi non entrambi nulli, e dato , esistono interi tali che

 


Basta osservare che per ogni riga della tabella si ha

L'ultimo elemento dell'ultima riga è uguale al massimo comun divisore, quindi i coefficienti su quella riga sono i coefficienti e che compaiono nell'identità di Bezout.


Nel caso di , si ha , e .


Esempio

e . Trova interi con

Non calcolo la riga successiva, perché il resto è 0. Allora e .

 


Esempio

Determinare tali che con e .

quindi , .

 


Esempio

Determinare tali che con e .

I due numeri sono coprimi, e .

 
 PrecedenteSuccessivo