Question

Solve linear congruence \[6x≡9 mod 15\]

Answer 1

@jim_thompson5910 @Hero

Answer 2

One way to do it:

x = 1, 6x = 6*1 = 6 (mod 15)
x = 2, 6x = 6*2 = 12 (mod 15)
x = 3, 6x = 6*3 = 18 = 3 (mod 15)
x = 4, 6x = 6*4 = 24 = 9 (mod 15)

So we can stop here

Answer 3

the method i see in my book is to find the inverse congruence class, which i am very confused on
can you please explain the inverse congruence method?
thanks

Answer 4

To find the inverse of 6 mod 15, you would solve the congruence below

6y = 1 (mod 15)

for y

Answer 5

but the problem is that gcd(6,15) = 3 and this doesn't divide 1

So 6 doesn't have an inverse mod 15

ie, there are no solutions to

6y = 1 (mod 15)

Answer 6

so you'll be spending quite a bit of time looking for the inverse, but you'll never find it (because it doesn't exist in this case)

Answer 7

the first step in the book was to divide the whole equation by 3, which would give \[2x≡3mod5\]and then it somehow jumps to\[x≡4mod5\]which confused the bajeezus out of me

Answer 8

oh it's using the rule that if

If ma = mb (mod n), and if d=GCD(m,n), then a = b (mod n/d)

Answer 9

ok i get that so far.

Answer 10

6x = 9 (mod 15)

3*2x = 3*3 (mod 3*5)

2x = 3 (mod 5)

Answer 11

now you can find the inverse because you can solve the following for y

2y = 1 (mod 5)

the solution is y = 3 since 2*3 = 6 which is 1 higher than 5 (so 6 = 1 (mod 5))

so...

2*3 = 1 (mod 5)

2*3*3 = 1*3 (mod 5)

2*9 = 3 (mod 5)

2*4 = 3 (mod 5)

So the solution to 2x = 3 (mod 5) is x = 4 (mod 5)

Answer 12

ok that makes a lot of sense now. because 9 is actually 5+4, so 9 mod 5 is the same as 4 mod 5?

Answer 13

exactly

Answer 14

or another way to think of it

9/5 = 1 remainder 4

that remainder is exactly what the mod is saying