2

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

Martin Sleziak
  • 53,687
proless8
  • 25

4 Answers4

1

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

Khosrotash
  • 24,922
0

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?

lab bhattacharjee
  • 274,582
  • 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 . – proless8 Jul 04 '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 http://mathworld.wolfram.com/ChineseRemainderTheorem.html we need co-prime moduli – lab bhattacharjee Jul 04 '17 at 12:12
0

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

Atul Mishra
  • 3,136
0

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

Atul Mishra
  • 3,136