Question

can I divide by 2? 8x ≡ 12 (mod 20)

Answer 1

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

Answer 2

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

Answer 3

you can divide by \(2\) again if you want to

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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)

Answer 8

gcd(8,20)*

Answer 9

You want to solve \(8x \equiv 12 \pmod {20} \)

the fastest way to do this is to divide \(8\) through out

Answer 10

\(\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}\)

Answer 11

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}\)

Answer 12

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

Answer 13

our goal is to convert that fraction into an integer

4 is same as -1 in mod 5, so...

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

thank you @ganeshie8 :')

Answer 19

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