Modular inverse with the extended Euclidean algorithm

Question

Find the inverse of $5$ modulo $26$ with the extended Euclidean algorithm.

Solution

We look for $x$ with $5x\equiv 1\pmod{26}$. The extended Euclidean algorithm on $\mathrm{mcd}(5,26)$ gives the linear combination $26 = 5\cdot 5 + 1 \ \Rightarrow\ 1 = 26 - 5\cdot 5 = 26 - 5\cdot 5.$ Reducing modulo $26$: $-5\cdot 5 \equiv 1$, that is $5\cdot(-5)\equiv 1$, and $-5 \equiv 21 \pmod{26}$. Check: $5\cdot 21 = 105 = 4\cdot 26 + 1 \equiv 1 \pmod{26}.$ The inverse is $\boxed{21}$.

Links

Topics: Probability distributions
Concepts: Modular arithmetic
Methods: Modular arithmetic
Skills: Computing
Exercise type: Expression evaluation