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 ;)
Answer
$\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}$
No comments:
Post a Comment