# Solving three modular equation using Chinese remainder theorem?

Solve the following equations:

\begin{align}7x&\equiv1 \mod 10\\ x-4&\equiv5 \mod 6\\ 3x&\equiv0 \mod 9\end{align}

I tried to bring them to the form $x\equiv a \mod b$, so I can use the Chinese remainder theorem, but I'm not sure how.

This is what I have got :

$7x\equiv1 \mod 10$ (don't know how ?)

$x\equiv9 \mod 6$

$x\equiv0 \mod 3$ (I divided the equation by $3$ )

1$$\text{(mod 10)} 7x\equiv 1 \to 21x\equiv 3 \to 20x+x\equiv 3\to x\equiv3$$ 2$$\text{(mod 6)} x-4\equiv5 \to x\equiv 9 \to x\equiv 6+3\to x\equiv 3$$ 3$$\text{(mod 9)} 3x\equiv0 \to 3x\equiv 9 \text{ divide by 3} \to x\equiv 3$$ from 1 $x=10k_1+3$

from2 $x=6k_2+3$

from 3 $x=3k_3+3$ so $$x-3=[10,6,3]k \to\\x-3=30k \\x=30k+3$$

HINT:

As $7\cdot3\equiv1\pmod{10}$

$7x\equiv1\pmod{10}\iff x\equiv3\pmod{10}\implies x\equiv3\pmod5\ \ \ \ (1)$

and $x\equiv3\pmod2\equiv1\ \ \ \ (2)$

$3x\equiv0\pmod9\iff x\equiv0\pmod3\ \ \ \ (3)$

$x-4\equiv5\pmod6\iff x\equiv9\pmod6\equiv3$

$\implies x\equiv3\pmod3\equiv0\ \ \ \$ which is same as $(3)$

$x\equiv3\pmod2\equiv1\ \ \ \$ which is same as $(2)$

Can you take it from here?

• yes i think i can ,but can you please explain why are these equivalent, i mean generally because i have some other exercises with same idea . Jul 4 '17 at 11:30
• @proless8, $$x\equiv a\pmod{mn}\iff$$ $$x\equiv a\pmod m$$ and $$x\equiv a\pmod n$$ for $(m,n)=1$ and for mathworld.wolfram.com/ChineseRemainderTheorem.html we need co-prime moduli Jul 4 '17 at 12:12

If you want a way to find out the solution of $$7x\equiv 1(mod~10)$$then I will advise you to do this

because you have $$7x\equiv 1(mod~10)$$ it is equivalent to $$7x=10y+1$$$$7x-10y=1$$and solve for $x~and~y$ by bejoutt's method,(I don't know the exact name so I leave it to experts to edit and correct the name)

I am solving this for you

Find the GCD of $7~and~10$$10=7\times 1+3$$$$7=3\times 2+1$$$$2=1\times 2+0$$so the GCD is$1$Now taking it backwards $$10-7\times 1=3$$putting this in next equation$$7=(10-7\times 1)\times 2 +1$$$$7\times 3-10\times 2=1$$so $$x=3,y=2$$which is equivalent to $$x\equiv 3(mod~10)$$ Do it with your third equation to get $$x\equiv 0(mod~3)$$ as you have written Now you are left with three equations $$x\equiv 3(mod~10)$$$$x\equiv 9(mod~ 6)~or~x\equiv 3(mod~6)$$$$x\equiv 0(mod~3)$$And you can solve these as you have mentioned in your question If you have difficulty in solving these , then I will expand this to the solution, You can see more about it here A problem in linear congruences equation • well, i soved the second and the third so i now have :$x\equiv27 \mod 30$and$x\equiv9 \mod 6$but gcd(30,6) != 1 what to do ? Jul 4 '17 at 12:29 • and you have obviously the first and the solution of last two equations which is easier to solve Jul 4 '17 at 12:32 • See my new answer @proless8 Jul 8 '17 at 11:32 Now in the previous answer I left you on $$x\equiv 3(mod~10)$$$$x\equiv 3(mod~6)$$$$x\equiv 0(mod~3)$$In this answer , I will tell you how to solv them Take first two $$x\equiv 3(mod~10)$$$$x\equiv 3(mod~6)$$ To make the$mod$equal , multiply the first by$3$and second by$5$$$3x\equiv 9(mod~30)$$$$5x\equiv 15(mod~30)$$subtract them to get $$2x\equiv 6(mod~30)$$$$x\equiv 3(mod~30)$$Now you have two more $$x\equiv 3(mod~30)$$$$x\equiv 0(mod~3)$$ again to eqaulise the$mod $multiply first by$1$and second by$10$$x\equiv 3(mod~30)$$ $$10x\equiv 0(mod~30)$$subtract them to get $$9x\equiv -3(mod~30)$$ $$9x\equiv 27(mod~30)$$ $$x\equiv 3(mod~30)$$ which completes the solution

If you got something like this in last step $$3x\equiv 4(mod~5)$$ then do the same thing as explained in previous answer

Note that for working of this method GCD is not needed to be $1$.

Hope it helps!!

• Are you satisfied with this answer now, can you use it to solve other exercises? @proless8 Jul 8 '17 at 12:25