Thread: Questions on solving linear congruences - Please answer whichever ones you can :)

I have to solve the congruence 15x = 45 mod 50. I used the normal equals sign as I can't get the three one.

To solve it, I did this:

General linear congruence is ax = b mod n (a,n)=d, where d is the greatest common factor.

(a,n) = (15,50) = 5 .................. 5 divides 45 => solutions exist.

15x = 45 mod 50 is the same as 3x = 9 mod 10

Greatest common factor of (3,10) = 1, and therefore the inverse of 3 exists, which means that x = 3mod 10.


I don't understand how to get the answer for that very last bit. So what if the inverse exists? Does that mean you simply divide 9 by the number in front of the x? Why not the 10 as well? What if the inverse didn't exist?


Thank you

Here is how I would solve such a problem:
15x= 45 (mod 50). Since both 15 and 45 are divisible by 5, that becomes 3x= 9 (mod 50).

That means that 3x= 9+ 50y for some integer y. That is the same as 3x- 50y= 9

Now, 3 divides into 50 16 times with a remainder 2. 2 divides into 3 once with remainder 1.

That is, 3- 2= 1 and 50- 3(16)= 2. Then 3- (50- 3(16))= 3(17)- 50= 1 and, multiplying by 9, 3(153)- 50(9)= 9. That is, x= 153= 3 (mod 50),

Check: 15*3= 45 which is, of course, 45 (mod 15).

Hello, ironz!

I too have an alternate approach . . .

We have: .

Solve for

And we have: . .[1]


Since is an integer, must be a multiple of 3: .

Substitute into [1]: .


Therefore: .