# Solve this system of equation (modular arithmetics)

$x\equiv 2\:(\text{mod }6)$ and $x \equiv 3\:(\text{mod }9)$

attempted solution:

$x = 2, 8, 14, 20,$

$x = 2+6m$

$x = 3, 12, 21, 30, 39$

x = $3+9m$

$2+6m = 3+9m$ $-1 = 3m$ $-1/3 = m$

$m$is not an integer, therefore there is no common solutions?

-
Where is the system of equations? – Paresh Nov 29 '12 at 20:47
Something wrong with the question as stated, since solutions of the form $(x=2,y=3)$ abound. – Lubin Nov 29 '12 at 20:54
Do you mean $x \equiv 3 (\mod 9)$? – Code-Guru Nov 29 '12 at 20:59
yeah i mean that – internetlearning Nov 29 '12 at 21:01
@internetlearning Then please edit your question, and also give the relation between $x$ an $y$ – Paresh Nov 29 '12 at 21:02

I see no reason why both constants should be the same. It should be more like

$$2+6m=3+9n$$

Doesn't look as helpful, but if you rearrange it like this

$$2=3+9n-6m$$

you will see that the right side is divisible by 3, but the left side is not. Therefore, there are no solutions.

-
@AustinMohr Actually, it appears he is in fact looking for a common solution. You're right, though, he does use 2 different variables. I see no reason why they can't have different values. Something may need to be clarified with the question. – Mike Nov 29 '12 at 21:02
you can know there is no solution without solving for n and m? – internetlearning Nov 29 '12 at 21:14
@internetlearning If $n$ and $m$ are integers, the right side of the equation is a multiple of $3$. $2$ is not. Therefore, there are no solutions with $m$ and $n$ both integers. – Mike Nov 29 '12 at 21:21
@internetlearning The divisibility is even more clear if you write $2 = 3(1 + 3n - 2m)$. Since $2$ is never an integer multiple of $3$, there can be no solution. – Austin Mohr Nov 30 '12 at 0:04

Hint $\rm \ \ \begin{eqnarray}\rm x &\equiv&\,\rm a\,\ (mod\ m)\\ \rm x &\equiv&\rm \,b\,\ (mod\ n)\end{eqnarray}\Rightarrow\: a\!+\!jm = x = b\!+\!kn\:\Rightarrow\:gcd(m,n)\mid jm\!-\!kn = b\!-\!a$

Hence $\rm\ b\!-\!a = \pm1\:\Rightarrow\:gcd(m,n)=1.\$ Since this fails in your system, it has no solution.

Conversely, a solution exists if $\rm\ gcd(m,n)\mid b\!-\!a,\:$ see the Chinese Remainder Theorem (CRT).

-