If $(a,n)=1$, prove that $ax \equiv b \mod n$ has exactly one solution $t$ such that $0\leq t < n$.

Question

Problem:

If $(a,n)=1$, prove that $ax \equiv b \mod n$ has exactly one solution $t$ such that $0\leq t < n$.

My attempt:

I know that $ax - b = nk$ for some integer $k$, so $x$ must be of the form $\frac{nk+b}{a}$ for the equation to hold. To find such an $x$ I started with the fact that $(a,n)=1$. This means that there exists integers $u,v$ (not necessarily unique) such that $au+nv=1$. Now solving for $u$ and multiplying by $b$ gives $bu=\frac{b-bnv}{a}$, which is a solution as it is in the right form.

My problem is that I don't know how to show the $0<bu \leq n$ part. Am I on the right track in how I constructed a solution? Could someone please give me a hint as to what to do next? Thanks!

Answer 1

You can use your observation that there exists $u,v$ such that $au+nv=1$. This essentially means that $u$ is a multiplicative inverse of $a$ modulo $n$.

Then, $aux\equiv ub\pmod n$

$(1-nv)x\equiv ub\pmod n$

$x\equiv ub\pmod n$

You can add and subtract $n$ from $bu$ till it satisfies the range $0\leq t<n$, it will still be a solution of the congruence.