## anonymous one year ago can I divide by 2? 8x ≡ 12 (mod 20)

1. anonymous

to get 4x ≡ 6 (mod 10) ??

2. ganeshie8

sure you can : $$8x\equiv 12\pmod{20} \implies 20\mid (8x-12) \\~\\\implies 20\mid 2(4x-6) \implies 10\mid (4x-6)$$

3. ganeshie8

you can divide by $$2$$ again if you want to

4. anonymous

So general, if ax ≡ b (mod c) and a,b,c have a common factor d and i can do (a/d)x ≡ (b/d) (mod c/d) ??

5. ganeshie8

thats right, notice that $ab \mid ac \implies b\mid c$

6. ganeshie8

$$2*10\mid 2(4x-6) \implies 10\mid (4x-6)$$

7. anonymous

ah I see. Is there a way to find the solution without trial and error initially? I know that if n is a solution then all solutions is x = n + t*20/gcd(8/20)

8. anonymous

gcd(8,20)*

9. ganeshie8

You want to solve $$8x \equiv 12 \pmod {20}$$ the fastest way to do this is to divide $$8$$ through out

10. ganeshie8

$$\large 8x \equiv 12 \pmod {20}$$ $$\large x \equiv \dfrac{12}{8} \pmod {\dfrac{20}{\gcd(8,20)}}$$ $$\large x \equiv \dfrac{12}{8} \pmod {5}$$

11. ganeshie8

Now look at $$\dfrac{12}{8}$$ in mod 5 : $\dfrac{12}{8} = \dfrac{6}{4}\equiv \dfrac{6}{-1} \equiv -6\equiv 4$ therefore the solution is $$x\equiv 4\pmod{5}$$

12. anonymous

you did you get 6/4 ≡ 6/(-1)? Looks like you did 4 - 5 in the denominator?

13. ganeshie8

our goal is to convert that fraction into an integer 4 is same as -1 in mod 5, so...

14. ganeshie8

you don't need to do it that way if it doesn't look intuitive... you can solve it the long way using reverse euclid gcd algorithm or by some other means..

15. ganeshie8

i just want to show you that division works pretty naturally with congruences whenever the ivnverses are defined

16. anonymous

Maybe I'll stick to guess and check for now. I will study this method further

17. ganeshie8

this is not a big method as such as you can see we're treating it as a regular algebraic equation and dividing stuff both sides

18. anonymous

thank you @ganeshie8 :')

19. ganeshie8

np, with the orthodox method you will be solving $$2x\equiv 3\pmod{5}$$ by using reverse euclid division algorithm, step by step, I think