Show that the only solution of the congruence equation $ax \equiv b\pmod{p}$ is $x \equiv a^{-1}b\equiv a^{p-2}b\pmod{p}$

Let $a$, $b$ be integers, and let $p$ be a prime not dividing $a$. Show that the only solution of the congruence equation $ax \equiv b\pmod{p}$ is $x \equiv a^{p-2}b\pmod{p}$

I've shown that this is a solution to the congruence equation, but how do I show that it is the only solution to the equation.

Solution 1:

Assume that there are two solutions $x_1$ and $x_2$, so $ax_1\equiv b \pmod p$ and $ax_2\equiv b \pmod p$. This implies $ax_1\equiv ax_2 \pmod p$, which means that $p\mid a(x_1-x_2)$. When a prime number divides the product of two integers, it has to divide at least one of them. Since $p\nmid a$, $p\mid x_1-x_2 \Leftrightarrow x_1\equiv x_2 \pmod p$, i.e., the solution has to be unique. Uniqueness here means that there's only $1$ equivalency class (numbers that give the same remainder when divided by $p$) satisfying the equation

Solution 2:

$\,ax\equiv b\!\!\overset{\large \times\ a^{p-2}\!\!\!\!\!}\iff x\equiv a^{p-2}b\,$ proves both existence $(\Leftarrow)$ and uniqueness $(\Rightarrow)$. Recall that scaling by a unit (invertible) always yields an equivalent equation (congruence). Here $(\Rightarrow)$ we scaled by $\,a^{-1}\equiv a^{p-2}\,$ by Fermat. The reverse $(\Leftarrow)$ is the inverse operation: scaling by $\,a\equiv (a^{-1})^{-1}$

Remark $ $ Thus the proof is no different from the same proof that $\,ax = b\,$ has a unique solution for rationals or reals, i.e. if $\,a\neq 0\,$ then $\,ax = b\iff x = a^{-1}b,\,$ by scaling by invertibles $\,a\,$ or $\,a^{-1}$.

See here and here for much further discussion of subtleties regarding such uniqueness.