L'inverso di un numero modulo n
L'inverso di un numero a modulo n è un numero b tale che il prodotto ab modulo n è uguale a 1. $$ ab = 1 $$
Se b è il reciproco di a allora b=a-1
$$ a \cdot b = a \cdot a^{-1} = a \cdot \frac{1}{a} = 1 $$
Quindi, il prodotto è uguale a 1.
Un esempio pratico
Considero il numero intero a=5 modulo 6
$$ a = 5 \ \in Z_6 $$
Devo trovare un altro numero b tale che
$$ a \cdot b = 1 \ \in Z_6 $$
Nota. Equivale a trovare un numero tale che il prodotto ab diviso n dia come risultato 1 $$ (ab) \ \% \ n = 1 $$
Sapendo che a=5
$$ 5 \cdot b = 1 \ \in Z_6 $$
Un modo banale per trovarlo è guardare la tavola della moltiplicazione se è disponibile
a ·6 b | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 | 5 |
2 | 0 | 2 | 4 | 0 | 2 | 4 |
3 | 0 | 3 | 0 | 3 | 0 | 3 |
4 | 0 | 4 | 2 | 0 | 4 | 2 |
5 | 0 | 5 | 4 | 3 | 2 | 1 |
In questo caso 5 è sempre 5 perché
$$ (5 \cdot 5)/6 = \frac{25}{6} = 4 \ \text{con resto} \ 1 $$
Quindi, il resto della divisione è 1
$$ (a \cdot b)%n = (5 \cdot 5)%6 = 25%6 = 1 $$
Nota. Non è detto che esista l'inverso di ogni numero non nullo modulo n. Ad esempio, nel modulo Z6 non ci sono elementi inversi di 2, 3 e 4. Esiste un elemento inverso per ogni numero solo se n è un numero primo.
Esempio 2
Considero la tavola moltiplicativa dei numeri modulo 5
a ·5 b | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 |
2 | 0 | 2 | 4 | 1 | 3 |
3 | 0 | 3 | 1 | 4 | 2 |
4 | 0 | 4 | 3 | 2 | 1 |
Poiché n=5 è un numero primo, in questo caso ogni numero modulo 5 non nullo ha un elemento inverso
$$ 1 \cdot 1 = 1 $$
$$ 2 \cdot 3 = 1 $$
$$ 3 \cdot 2 = 1 $$
$$ 4 \cdot 4 = 1 $$
Come calcolare il numero inverso di un numero modulo n
Per calcolare il numero inverso di un numero modulo n posso utilizzare l'algoritmo esteso di Euclide.
L'algoritmo di Euclide si basa sul fatto che se a e n sono relativamente primi, allora esiste un numero x tale che a·x ≡ 1 (mod n).
In generale, se i numeri a e n non sono relativamente primi non esiste un elemento inverso modulo n.
Posso scrivere il problema sotto forma di identità di Bézout dove a e n sono termini noti
$$ a \cdot x + n \cdot y = 1 $$
Il coefficiente intero x è l'inverso del numero a mentre il coefficiente intero y posso anche ignorarlo.
Come funziona? L'algoritmo esteso di Euclide trova le soluzioni dell'equazione di Bézout con la sola differenza che il massimo comune divisore MCD(a,n)=1 non devo calcolarlo perché già lo conosco essendo coprimi i due numeri. Per calcolare l'inverso di a ciò che mi interessa è il coefficiente x.
Nota. In generale l'algoritmo "esteso" di Euclide è un'estensione dell'algoritmo di Euclide che calcola non solo il massimo comune divisore (MCD) ma anche i coefficienti dell'identità di Bézout tali che $$ ax+by=MCD(a,b) $$ Quando i numeri a e b sono relativamente primi (coprimi) tra loro, l'algoritmo si semplifica perché il termine noto dell'identità di Bézout diventa uguale a 1 in quanto il MCD di due numeri coprimi è sempre uguale a 1 $$ ax+by=1 $$ In questo caso, non è necessario calcolare il MCD(a,b). Eventualmente, per trovare i numeri relativamente primi posso usare la funzione di Eulero.
Esempio
Devo trovare l'inverso di 23 nel modulo 40
Essendo 23 un numero primo e non è divisore di 40, so già per certo che i due numeri sono coprimi
$$ MCD(23, 40)=1 $$
Quindi posso utilizzare l'algoritmo esteso di Eulero.
Nota. Se non fossero stati relativamente primi non avrei potuto usare l'algoritmo di Eulero.
Devo risolvere l'equazione di Bézout con a=23 e n=40
$$ 23 \cdot u + 40 \cdot v = 1 $$
Calcolo il resto della divisione 40/23
Poi calcolo il resto della divisione tra il divisore (23) e il resto dellla divisione precedente, finché non ottengo un resto uguale a 1.
In ogni passaggio cerco di riportare i resti nella forma r=23u+40v
resto | |
$$ 40:23 = 23 \cdot 1 + 17 $$ | $$ 17 = 40 - 23 $$ $$ 17 = 40 \cdot 1 + 23 \cdot (-1) $$ |
$$ 23:17 = 17 \cdot 1 + 6 $$ Spiegazione: divido il divisore precedente (23) per il resto precedente (17) | $$ 6 = 23 - 17 $$ $$ 6 = 23 - (40-23) $$ $$ 6= 23 \cdot 2 - 40$$ $$ 6= 23 \cdot 2 + 40 \cdot (-1) $$ |
$$ 17:6 = 6 \cdot 2 + 5 $$ Spiegazione: divido il divisore precedente (17) per il resto precedente (6) | $$ 5 = 17 - 6 \cdot 2 $$ $$ 5 = (40-23) - (23 \cdot 2 - 40) \cdot 2 $$ $$ 5 = 40-23 - 23 \cdot 2 \cdot 2 + 40 \cdot 2 $$ $$ 5 = - 23 \cdot 5 + 40 \cdot 3 $$ $$ 5 = 23 \cdot (-5) + 40 \cdot 3 $$ |
$$ 6:5 = 5 \cdot 1 + 1 $$ Spiegazione: divido il divisore precedente (6) per il resto precedente (5) | $$ 1 = 6 - 5 $$ $$ 1 = [ 23 \cdot 2 + 40 \cdot (-1) ] - [23 \cdot (-5) + 40 \cdot 3] $$ $$ 1 = 23 \cdot 2 + 40 \cdot (-1) - 23 \cdot (-5) - 40 \cdot 3] $$ $$ 1 = 23 \cdot 2 + 40 \cdot (-1) + 23 \cdot (5) + 40 \cdot (-3) $$ $$ 1 = 23 \cdot (2+5) + 40 \cdot (-1-3) $$ $$ 1 = 23 \cdot (7) + 40 \cdot (-4) $$ |
Ora il resto è 1. Quindi, l'iterazione termina qui.
Una volta trovati i coefficienti dell'equazione di Bézout, trovo anche l'inverso di 23 mod 40
$$ 1 = 23 \cdot 7 + 40 \cdot (-4) $$
L'inverso di 23 mod 40 è il coefficiente di 23 nell'equazione di Bézout.
$$ 1 = 23 \cdot \color{red}7 + 40 \cdot (-4) $$
In questo caso l'inverso di 23 (mod 40) è 7
Verifica. Calcolo il prodotto di 23·7 mod 40 $$ 23 \cdot 7 \ \text{(mod 40)} $$ $$ 161 \ \text{(mod 40)} $$ $$ 40 \cdot 4 + 1 \ \text{(mod 40)} $$ Il resto è uguale a 1. Quindi il calcolo è corretto.
E così via.