Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote 1 down vote accepted

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$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.