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.
Best Answer
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