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 x₀ = 1, y₀ = 0 e x₁= 0, y₁ = 1. Inoltre a₁ = a, b₁ = b e q₁ = 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: a_i = b_i-1, b_i = r_i-1 ovvero a_i-1 mod b_i-1, q_i = a_i / b_i e i valori x_i = x_i-2 - q_i-1 x_i-1 e y_i = y_i-2 - q_i-1 y_i-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 b_i = 0. Allora si ha MCD(a, b) = a_i, 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
x_i+1 = x_i-1 - q_i x_i e y_i+1 = y_i-1 - q_i y_i
Quindi: x₂ = x₀ - q₁ x₁ e y₂ = y₀ - q₁ y₁. Sostituendo si ha: x₂ = 1 - 1*0 = 1 e y₂ = 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: x₃ = 0 - 1*1 = -1 e y₃ = 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: x₄ = 1 - (-1)*8 = 9 e y₄ = (-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: x₅ = (-1) - 2*9 = -19 e y₅ = 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