1
$\begingroup$

Ok, I found a lot of questions asking about solving $a = b \pmod c$ where you could divide $a$ and $b$ by some $x$ where gcd$(x, c) = 1$. How do you solve when this is not the case?

Suppose I have $10 x \equiv 5 \pmod{15}$. How do I solve this? How can you solve to get a linear equation in $x$?

On inspection (and trying out values), I see that $x = 3n + 2$ is what I'm looking for. How can I get this mathematically?

And yes, this is homework, but I changed the numbers so that I could practice on the actual problem ;)

  • 0
    See [here](http://math.stackexchange.com/questions/186674/how-to-solve-100x-19-0-pmod23/186702#186702).2012-09-16

2 Answers 2

1

$\begin{eqnarray}\rm{\bf Hint}\ &&\rm mod\ mc\!:\ ac\,x\equiv bc&\iff&\rm mod\ m\!:\ ax\equiv b\quad for\ \ c\ne0\\ \rm &&\rm by\ \ \ \ mc\, \:|\: \ ac\,x-bc&\iff&\rm m\ |\ ax-b\\ \rm &&\rm because\ \ \ \dfrac{ac\,x-bc}{mc}&\ \ =\ \ &\rm \dfrac{ax-b}{m} \end{eqnarray}$

  • 0
    Essentially: we can cancel $\rm\,c\,$ from the congruences (or the equivalent divisibilty relations) because they are equivalent to said fraction being integral, and $\rm\,c\,$ cancels in the fraction.2012-09-17
0

Hint: In general, if $k\ne 0$, we have $kax\equiv kb \pmod{km} \quad\text{iff}\quad ax\equiv b \pmod{m}.$