# Proving a congruence solution is unique $\pmod {m/\gcd(c,m)}$

Prove that one can solve the congruence $cx \equiv b \pmod m \Longleftrightarrow \gcd(c,m)|b$. Show, moreover, that the answer is unique $\bmod{m/\gcd(c,m)}$

My Work

Proof of $(\Rightarrow)$:

Assume that $cx \equiv b \pmod m$ has a solution, call it $x_1$. Let $d = \gcd(c,m)$ Then \begin{align*} cx_1 \equiv b \pmod m &\Longleftrightarrow m | (cx_1 - b) \\ &\Longleftrightarrow cx_1 = km + b, \quad k \in \Bbb Z \\ &\Longleftrightarrow cx_1 + (-k)m = b \\ \end{align*} As the $\gcd$, $d$ divides all linear combinations of $c$ and $m$, so $d | b$.

Proof of $(\Leftarrow)$:

Assume $d | b$. Then $b = dn$ for some $n \in \Bbb Z$. As the $\gcd$, $d = cs + mt$ for some $s,t$. So \begin{align*} dn &= csn + mtn \\ b &= csn + mtn \\ csn - b &= (-tn)m \\ csn - b &\equiv 0 \pmod m\\ csn &\equiv b \pmod m \end{align*}

Taking $x = sn$, we have a solution to the linear congruence $cx \equiv b \pmod m$.

My Question

I am not sure how to prove uniqueness from here. Should I say that $cx \equiv b \pmod m$ gives that, for $d = \gcd(c,m)$, $$m | (cx -b ) \Longrightarrow \left({m \over d}\right) \mid \left({cx - b \over d}\right) = {c \over d}x - {b \over d}$$ However, I'm not sure how to move from here to uniqueness. I have that ${c \over d}x = {m\over d}k + {b\over d}$, but this doesn't seem to be much.

-
Lemma: $gx \equiv gy \pmod{gn}$ if and only if $x \equiv y \pmod n$. – Hurkyl Sep 14 '12 at 23:27

Hint $\$ If $\rm\:x,y\:$ are solutions then $\rm\ cx\equiv b\equiv cy\pmod m\$ so, defining $\rm\ d=(m,c)\:$ we have

$$\rm\,m\:|\:c\,(x\!-\!y) \iff \frac{m}d\:\bigg|\:\frac{c}d\,(x\!-\!y)\color{#C00}{\iff} \frac{m}d\:\bigg|\ x\!-y\,\ \ by \ \ \left(\frac{m}d,\frac{c}d\right)= \frac{(m,c)}d = 1$$

Remark $\$ The $\rm\color{#C00}{final}\,$ equivalence employs Euclid's Lemma and the distributive law for GCDs.

Alternatively $\$ By Bezout $\rm\: d = (c,m) = jc+km,\,\ j,k\in\Bbb Z.\:$ Let $\rm\:z = x-y.\:$ Then

$\rm\ mod\ m\!:\ cz\equiv 0\equiv mz\ \Rightarrow\ dz = (c,m)z = j(cz)+k(mz) \equiv 0,\:$ so $\rm\ m\:|\:dz\:\Rightarrow\:m/d\:|\:z$

-

You want to show that if $cx_1\equiv b\pmod m$ and $cx_2\equiv b\pmod m$, then $x_1\equiv x_2\pmod{m/d}$. Let $c'=c/d$ and $m'=m/d$. You’ve shown that $d\mid b$, so let $b\,'=b/d$.

You have $cx_1-b=k_1m$ and $cx_2-b=k_2m$ for some $k_1,d_2\in\Bbb Z$, so $c'x_1-b\,'=k_1m'$ and $c'x_2-b\,'=k_2m'$, and therefore $c'x_1\equiv b\,'\pmod {m'}$ and $c'x_2\equiv b\,'\pmod {m'}$. In particular, $c'x_1\equiv c'x_2\pmod{m'}$. Now use the fact that $c'$ and $m'$ are relatively prime to get the desired conclusion.

-

Suppose that $cx_1\equiv b\pmod{m}$ and $cx_2\equiv b\pmod{m}$. Then $$c(x_1-x_2)\equiv 0\pmod{m}.$$ Let $d=\gcd(c,m)$, and let $c=kd$ and $m=dn$. Then $kd(x_1-x_2)\equiv 0\pmod{dn}$, and therefore $k(x_1-x_2)\equiv 0\pmod{n}$.

Suppose that $c\ne 0$. Since $k$ and $n$ are relatively prime, $k$ has an inverse $l$ modulo $n$. Multiply through by $l$. We get $x_1-x_2\equiv 0\pmod{n}$, which is the desired result.

In the degenerate case $c=0$, we need to show that any two solutions of $(0)x\equiv 0\pmod{m}$ are congruent modulo $1$, which is clearly true.

-