Modular Inverses

Division is not directly defined in modular arithmetic. Instead, we multiply by the modular inverse.

Definition

Existence and Uniqueness

• Existence: $a^{-1}$ exists if and only if $\gcd (a,n)=1$.
• Uniqueness: If it exists, it is unique modulo $n$.

Computation Methods

1. Extended Euclidean Algorithm

Solve $ax+ny=1$ for integers $x,y$. Then $ax\equiv 1(\mathrm{mod}n)$, so $a^{-1}\equiv x(\mathrm{mod}n)$.

2. Fermat's Little Theorem (for prime moduli)

If $p$ is prime and $p\nmid a$: Thus, $a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$.

3. Euler's Theorem

For general $n$: $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)⟹a^{-1}\equiv a^{\varphi (n)-1}(\mathrm{mod}n)$.

Practice Problems