Algoritmo di Euclide

Algoritmo di Euclide

L'algoritmo di Euclide permette di trovare il MCD di due numeri a e b senza effettuarne la scomposizione in fattori primi.

Descrizione

Dati due numeri a e b, con a < b, il loro MCD sarà lo stesso della coppia di numeri b e a mod b (resto della divisione intera tra a e b). Siccome a mod b è sempre minore di b, l'algoritmo procede esaminando coppie di numeri decrescenti, fino a quando trova a mod b = 0, ovvero quando la coppia di numeri esaminati sono multipli.

a b resto a mod b
a1 b1 r1 = a1 mod b1
a2 = b1 b2 = r1 r2 = a2 mod b2
ai = bi-1 bi = ri-1 ri = ai mod bi

L'algoritmo può essere scritto così:

while(b != 0)
{
    temp = b;
    b = a mod b;
    a = temp;
}
return a;

Esempio

Si considerano i numeri a = 105 e b = 77. Si calcola 105 mod 77 = 28. La prima riga della tabella sarà:

a b resto a mod b
105 77 28

La nuova coppia di numeri sarà a = 77 e b = 28. 77 mod 28 = 21

a b resto a mod b
105 77 28
77 28 21

Si prosegue allo stesso modo considerando a = 28 e b = 21, e così via fino a quando si trova un resto nullo, quindi una coppia di numeri dove b = 0. L'algoritmo termina e l'MCD è il valore di a.

a b resto a mod b
105 77 28
77 28 21
28 21 7
21 7 0
7 0

L'MCD di 105 e 77 è 7.

Algoritmo esteso di Euclide

Questo algoritmo è un'estensione dell'algoritmo di Euclide che permette di determinare il MCD di due numeri. In particolare, dati due numeri a e b l'algoritmo esteso di Euclide ricava il valore del MCD e di due numeri x e y tali che:

(1)
\begin{equation} x a + y b = MCD \end{equation}

Descrizione

Siano x0 = 1, y0 = 0 e x1= 0, y1 = 1. Inoltre a1 = a, b1 = b e q1 = a / b. Si può utilizzare una tabella le cui prime due righe sono sempre fisse e risultano le seguenti:

passo a b q x y
0 - - - 1 0
1 a1 = a b1 = b q1 = a / b 0 1

Al passo i-esimo, si calcolano i seguenti valori: ai = bi-1, bi = ri-1 ovvero ai-1 mod bi-1, qi = ai / bi e i valori xi = xi-2 - qi-1 xi-1 e yi = yi-2 - qi-1 yi-1.

passo a b q x y
0 - - - 1 0
1 a1 = a b1 = b q1 = a / b 0 1
i-2 ai-2 bi-2 qi-2 xi-2 yi-2
i-1 ai-1 bi-1 qi-1 xi-1 yi-1
i ai = bi-1 bi = ri-1 = ai-1 mod bi-1 qi = ai / bi xi = xi-2 - qi-1 xi-1 yi = yi-2 - qi-1 yi-1

L'algoritmo si interrompe quando bi = 0. Allora si ha MCD(a, b) = ai, x = x, y = y con le seguenti proprietà:

  1. ax + by = MCD(a, b)
  2. nel caso in cui a e b siano coprimi, allora MCD(a, b) = 1 per definizione, quindi ax + by = 1. Allora ax = 1 - by, quindi ax mod b = 1. Da questo si deduce che x è il moltiplicativo inverso di a (mod b). Analogamente, essendo ax + by = 1, by = 1 - ax quindi by mod a = 1. y è il moltiplicativo inverso di b (mod a).

L'algoritmo può essere descritto, in pseudocodice così:

function extended_gcd(a, b)
x = 0;
lastx = 1;
y = 1;
lasty = 0;
while(b != 0)
{
    temp = b;
    quotient = a div b;
    b = a mod b;
    a = temp;
 
        temp = x;
    x = lastx-quotient*x;
 
    lastx = temp;
 
    temp = y;
    y = lasty-quotient*y;
 
    lasty = temp;
}
return {lastx, lasty, a}

++++Esempio
Si suppone di voler applicare l'algoritmo ai numeri a=89 e b=47. Si costruisce una tabella in cui vengono inseriti i valori di x e y come illustrato e nella seconda riga i numeri a e b.

passo a b q x y
0 - - - 1 0
1 89 47 - 0 1

89 / 47 = 1 con resto 42. Si inserisce il risultato intero della divisione nella colonna q, e nella riga successiva si inserisce nella colonna a il valore di b e nella colonna b il resto della divisione, ovvero 42

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 - - -

Si calcolano i valori x e y secondo la formula
xi+1 = xi-1 - qi xi e yi+1 = yi-1 - qi yi
Quindi: x2 = x0 - q1 x1 e y2 = y0 - q1 y1. Sostituendo si ha: x2 = 1 - 1*0 = 1 e y2 = 0 - 1*1 = -1.

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 - 1 -1

La divisione 47 / 42 fornisce come risultato 1 con resto di 5. Si inserisce q2=1, nella colonna a il valore di b, ovvero 42 e nella colonna b il resto della divisione, ovvero 5.

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 - - -

i valori di x e y sono: x3 = 0 - 1*1 = -1 e y3 = 1 - (-1)*1 = 2

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 - -1 2

Si ha: 42 / 5 = 8 con resto di 2

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 8 -1 2
4 5 2 - - -

i valori di x e y sono: x4 = 1 - (-1)*8 = 9 e y4 = (-1) - 8*2 = -17

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 8 -1 2
4 5 2 - 9 -17

La divisione successiva è: 5 / 2 = 2 con resto di 1

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 8 -1 2
4 5 2 2 9 -17
5 2 1 - - -

i valori di x e y sono: x5 = (-1) - 2*9 = -19 e y5 = 2 - 2*(-17) = 36

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 8 -1 2
4 5 2 2 9 -17
5 2 1 - -19 36

L'ultima divisione è: 2 / 1 = 2 con resto 0. Infatti si inserisce il valore 1 nella colonna di a e il resto 0 nella colonna di b. Essendo b = 0 l'algoritmo si ferma.

passo a b q x y
0 - - - 1 0
1 89 47 1 0 1
2 47 42 1 1 -1
3 42 5 8 -1 2
4 5 2 2 9 -17
5 2 1 1 -19 36
6 1 0 - - -

Sulla colonna di a si legge il valore del MCD: 1. I due numeri sono quindi coprimi. Gli ultimi valori di x e y sono i valori desiderati: si verifica infatti che

a*x + b*y = 1

89*(-19) + 47*36 = 1

x è il moltiplicativo inverso di a mod b, quindi a*x mod b = 1. Se x è un numero negativo, come in questo caso, per trovare il vero valore desiderato è sufficiente aggiungere a x il modulo b, quindi il moltiplicativo inverso di 89 è (-19)+47 = 28. Si verifica che:

89*28 mod 47 = 2492 mod 47 = 1

Mentre y è il moltiplicativo inverso di b mod a, ovvero b*y mod a = 1

47*36 mod 89 = 1692 mod 89 = 1

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License