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$ )

Please help me continue


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$$



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?

  • $\begingroup$ 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 . $\endgroup$
    – proless8
    Jul 4 '17 at 11:30
  • $\begingroup$ @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 $\endgroup$ 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

  • $\begingroup$ 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 ? $\endgroup$
    – proless8
    Jul 4 '17 at 12:29
  • $\begingroup$ and you have obviously the first and the solution of last two equations which is easier to solve $\endgroup$ Jul 4 '17 at 12:32
  • $\begingroup$ See my new answer @proless8 $\endgroup$ 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!!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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