I have been working through exercises in a book on polynomials. There is a section in the first chapter on some basic number theory. I am having trouble completing one of the exercises. Part (e.) of the exercises goes like this :
"We say that the solution of a congruence $ax \equiv b ( \mod m)$ is unique modulo $m$, or simply, unique, if the difference between any two solutions is divisible by $m$. In other words, the requirement is that $au \equiv av \equiv b (\mod m)$ implies $u \equiv v (\mod m)$. Show that the solution of the congruence is unique if and only if $\text{gcd}(a,m) = 1$."
Here a solution to the congruence is some $x \in \mathbb{Z}$ s.t. $ax \equiv b(\mod m)$ is true. I suspect $u$ and $v$ are two arbitrarily chosen solutions.
I think I am able to prove the forward implication but not the backwards one. We see :
\begin{equation}
au \equiv av \equiv b ( \mod m) \Rightarrow m | (au - b) \text{ and } m|(av-b)
\end{equation}
Where $x|y$ means that $y$ is divisible by $x$. The above implies :
\begin{align}
& \Rightarrow m | \left[ (au - b) - (av - b) \right] \\\\
& \Rightarrow m | \left[ (au - av) + (b - b ) \right] \\\\
& \Rightarrow m | (au - av) \\\\
& \Rightarrow au \equiv av ( \mod m)
\end{align}
So this implies :
\begin{align}
\Rightarrow m | (au - av) \Rightarrow m | a(u-v)
\end{align}
We then see :
\begin{equation}
\text{gcd}(a,m) = 1 \text{ and } m | a(u-v) \Rightarrow m | (u-v) \text{ and } m \not | a
\end{equation}
Where $m \not | a$ means that $a$ is not divisible by $m$.
So in this case : \begin{equation} u \equiv v ( \mod m ) \; \checkmark \end{equation}
So here I've shown that : \begin{equation} \text{gcd}(a,m) = 1 \text{ and } au \equiv av \equiv b (\mod m) \Rightarrow u \equiv v (\mod m) \end{equation} But I haven't shown that : \begin{equation} \text{gcd}(a,m) \neq 1 \text{ and } au \equiv av \equiv b (\mod m) \Rightarrow u \not \equiv v (\mod m) \end{equation} Can anyone help me with how to prove the converse ?