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.

 


 

Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

FacebookTwitterLinkedinLinkedin
knowledge base

Tool