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)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à:
- ax + by = MCD(a, b)
- 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