Inverso modulare con Euclide esteso

Testo

Trova l’inverso di $5$ modulo $26$ con l’algoritmo di Euclide esteso.

Soluzione

Cerchiamo $x$ con $5x\equiv 1\pmod{26}$. L’algoritmo di Euclide esteso su $\mathrm{mcd}(5,26)$ dà la combinazione lineare $26 = 5\cdot 5 + 1 \ \Rightarrow\ 1 = 26 - 5\cdot 5 = 26 - 5\cdot 5.$ Riducendo modulo $26$: $-5\cdot 5 \equiv 1$, cioè $5\cdot(-5)\equiv 1$, e $-5 \equiv 21 \pmod{26}$. Verifica: $5\cdot 21 = 105 = 4\cdot 26 + 1 \equiv 1 \pmod{26}.$ L’inverso è $\boxed{21}$.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare
Metodi: Aritmetica modulare
Competenze: Calcolare
Tipo di esercizio: Calcolo espressioni