Inverso e classi resto

Ciao Andrea! Poniamoci all'interno delle classi di resto modulo $n$, ossia in $\mathbb{Z}_{n}$. In generale, le normali operazioni di somma e moltiplicazione in $\mathbb{Z}$ passano al quoziente modulo $n$, quindi $\mathbb{Z}_{n}$ è un anello (con unità): possiamo sommare e moltiplicare classi di resto sommando o moltiplicando i loro rappresentanti. $\mathbb{Z}_{n}$ però ha qualcosa di più rispetto a $\mathbb{Z}$: alcuni dei suoi elementi risultano invertibili. Un elemento è invertibile quando possiamo ottenere l'unità, moltiplicandolo per un opportuno inverso: ad esempio, nell'anello $(\mathbb{Q},+,\cdot)$ la frazione $\frac{x}{y}$ è invertibile, perché $\frac{y}{x} \cdot \frac{x}{y} = 1$ (e quindi $\frac{y}{x}$ è un suo inverso). Si può dimostrare che, in $\mathbb{Z}_n$, una classe di resto $[m]$ è invertibile se, e solo se, $m$ è primo con $n$, ossia se non hanno divisori in comune, o meglio ancora, se il loro massimo comune divisore è $1$:$$ [m] \in \mathbb{Z}_n \text{ ammette inverso } \Leftrightarrow \text{ M.C.D.}(m,n) = 1$$Scopriamo allora qual è l'$\text{M.C.D.}$ tra $267$ e $112$: basta seguire questa lezione https://library.weschool.com/lezione/mcm-mcd-calcolo-massimo-comun-divisore-minimo-comune-multiplo-online-13224.html. Con pochi passaggi si scopre che effettivamente $112$ e $267$ sono coprimi, cioè primi tra loro: $112$ ha un inverso modulo $267$. Ora dobbiamo trovarlo! Dobbiamo quindi trovare un numero $x$ che, moltiplicato per $112$, dia come risultato un numero congruo a $1$ modulo $267$. Questo significa che $112 \ x = 1 + 267 \ n$, o meglio, che$$ 267 \ m + 112 \ x = 1$$Si tratta di un'equazione diofantea, che ammette soluzione: la condizione, guarda caso, è che il termine noto ($1$) sia l'$\text{M.C.D.}$ dei coefficienti. Per trovare questa soluzione, si ricorre ad un algoritmo, detto algoritmo di Euclide o delle divisioni successive. Questo funziona così. Poniamo $a_1$ ed $a_2$ uguali ai coefficienti (con $a_1 > a_2$), nel nostro caso sarà $a_1 = 267$ e $a_2 = 112$; eseguo la divisione con resto di $a_1$ per $a_2$: sarà $a_1 = q_1 \cdot a_2 + a_3$, con $q_1$ quoziente e $a_3$ resto. Se $a_3 = 1$, abbiamo finito; sennò proseguiamo, dividendo $a_2$ per $a_3$, e così via, sino a quando non avremo come resto il termine noto $1$. A questo punto avremo una serie di espressioni di questo tipo:$$ \begin{array}{c} a_1 = q_1 \cdot a_2 + a_3 \\ a_2 = q_2 \cdot a_3 + a_4 \\ \dots \\ a_{n-2} = q_{n-2} \cdot a_{n-1} + 1 \end{array}$$Possiamo sostituire, a ritroso, i vari valori ottenuti sino a giungere alla prima. Nel nostro caso, avremo$$ \begin{array}{l} 267 = 2 \cdot 112 + 43 \\ 112 = 2 \cdot 43 + 26 \\ 43 = 1 \cdot 26 + 17 \\ 26 = 1 \cdot 17 + 9 \\ 17 = 1 \cdot 9 + 8 \\ 9 = 1 \cdot 8 +1 \end{array} $$Riscriviamo mettendo in evidenza i resti:$$ \begin{array}{l} 43 = 267 - 2 \cdot 112 \\ 26 = 112 - 2 \cdot 43 \\ 17 = 43 - 1 \cdot 26 \\ 9 = 26 - 1 \cdot 17 \\ 8 = 17 - 1 \cdot 9 \\ 1 = 9 - 1 \cdot 8 \end{array} $$Dall'ultima equazione sostituiamo all'indietro:$$##KATEX##\begin{array}{l} 1 = 9-8 = 9 - (17 - 9) =\\ = 2 \cdot 9 - 17 = 2 \cdot (26-17) -17 =\\ = 2 \cdot 26 - 3 \cdot 17 = 2 \cdot 26 - 3 \cdot(43 - 26) =\\ = -3 \cdot 43 +5 \cdot 26 = -3 \cdot 43 +5 \cdot (112 - 2\cdot 43) =\\ = 5 \cdot 112 - 13 \cdot 43 = 5 \cdot 112 - 13 \cdot(267 - 2 \cdot 112) =\\ = -13 \cdot 267 + 31 \cdot 112 \end{array}##KATEX##$$Confrontando il primo e l'ultimo membro, scopriamo che$$ 1 = -13 \cdot 267 + 31 \cdot 112 $$Dunque l'inverso della classe di resto di $112$ modulo $267$ è la classe di resto di $31$! Spero che sia tutto chiaro. Ciao e buona giornata!

Ti ringrazio infinitamente!! - Andrea Manisi 03 Dicembre 2015