Wednesday, 8 April 2026

Exercise (6.1).9

Let the order of $a$ modulo $n$ be $k$. Show that inverse of $a$ modulo $n$ is

$$ a^{k−1} \pmod n $$


That $k$ is the order of $a$ modulo $n$ means

$$ a^k \equiv 1 \pmod {n} $$

Factorising

$$ a \times a^{k-1} \equiv 1 \pmod {n} $$

By definition of inverse, this tells us the inverse of $a$ modulo $n$ is $a^{k-1}$.