Friday, 21 November 2025

Exercise (3.3).15

Show that every integer $a$ such that $1 ≤ a < p$ where $p$ is prime has a multiplicative inverse modulo $p$.


Since $p$ is prime, it only has factors 1 and $p$. This means $\gcd(a,p)=1$ for $1 \le a < p$.

Then then means the following linear congruence has a unique solution for $x$

$$ ax \equiv 1 \pmod p$$

Here $x$ is the multiplicative inverse of $a$ modulo $p$.