Inverso di un numero nelle congruenze
Salve, ho ripreso da poco la parte di aritmetica modulare, mi sono rivsto la definizione di inverso però non riesco bene a capire come calcolare "velocemente" l'inverso di un numero mod m.
Vi presento l'esercizio che stavo facendo, sperando innanzitutto che i passaggi che ho fatto siano corretti:
$2+3k ≡ 1 mod 11$
$3k ≡ 1-2 mod 11$
$3k ≡ -1 mod 11$
Ora ho fatto $11-:3$ che mi da resto $2$, dunque:
$-2k ≡ -1 mod 11$
$2k ≡ 1 mod 11$
Ora devo trovare l'inverso affinchè trasformi la congruenza nella forma: $k ≡ a mod 11$
Mi potete spiegare nel modo più semplice possibile che calcoli devo fare per calcolare velocemente l'inverso?
Grazie in anticipo!
Vi presento l'esercizio che stavo facendo, sperando innanzitutto che i passaggi che ho fatto siano corretti:
$2+3k ≡ 1 mod 11$
$3k ≡ 1-2 mod 11$
$3k ≡ -1 mod 11$
Ora ho fatto $11-:3$ che mi da resto $2$, dunque:
$-2k ≡ -1 mod 11$
$2k ≡ 1 mod 11$
Ora devo trovare l'inverso affinchè trasformi la congruenza nella forma: $k ≡ a mod 11$
Mi potete spiegare nel modo più semplice possibile che calcoli devo fare per calcolare velocemente l'inverso?
Grazie in anticipo!
Risposte
Considera la congruenza
\[ ax \equiv 1 \mod n\]
con $a$ e $n$ fissati.
In generale, $a$ è invertibile modulo $n$ se e solo se $MCD(a,n) = 1$. Dunque calcoli i moltiplicatori dell'identità di bezout (tramite l'algoritmo euclideo) cioè trovi $\alpha,\beta$ tali che
\[ \alpha a + \beta n = 1.\]
Scrivendo questa eguaglianza modulo $n$ ottieni
\[ \alpha a \equiv 1 \mod n\]
ovvero $x = \alpha$ dà un inverso modulo $n$ di $a$.
\[ ax \equiv 1 \mod n\]
con $a$ e $n$ fissati.
In generale, $a$ è invertibile modulo $n$ se e solo se $MCD(a,n) = 1$. Dunque calcoli i moltiplicatori dell'identità di bezout (tramite l'algoritmo euclideo) cioè trovi $\alpha,\beta$ tali che
\[ \alpha a + \beta n = 1.\]
Scrivendo questa eguaglianza modulo $n$ ottieni
\[ \alpha a \equiv 1 \mod n\]
ovvero $x = \alpha$ dà un inverso modulo $n$ di $a$.