Solving ax = c (mod m): Step-by-Step Guide

[booney1983]

how can i solve this problem by step to step? i will make computer program, due to this reason i ve got to learn it's solving method...

ax = c ( mod m )

( example: 5x = 7 ( mod 37) )

could someone explain it with ax = c (mod m).. thank you and best regards...

 

[HallsofIvy]

if ax= c (mod m) then ax and c have the same remainder when divided by m (same thing: ax- c is divisible by m). That means that ax= mn+ c for some integer n. Solve the diophantine equation ax- mn= c for x and m (which, of course, gives you x). Unfortunately, that can be complicated!

In your example, 5x= 7 (mod 37), which is the same as 5x- 37n= 7, I would do this:
Divide 37 by 5: quotient 7, remainder 2: 37- 7(5)= 2. Divide 5 by the remainder, 2: quotient 2, remainder 1: 5- 2(2)= 1.

Now replace the "(2)" with the previous equation: 5- 2(37- 7(5))= 1 or 15(5)- 2(37)= 1 (check that).

Multiplying that last equation by 7, 105(5)- 14(37)= 7 . So one possible solution is x= 105: 105*5= 525= 14(37)+ 7.

Of course, you will want to reduce that to between 0 and 36: 105= 2(37)+ 31 so x= 31 is the answer. 5*31= 155= 4(37)+ 7.

The general method, repeatedly dividing each previous divisor by the remainder until you have a remainder of 1 (the Euclidean division algorithm) can be complicated to program. Since computers are very good at doing simple-minded things very fast, I would frankly recommend "brute strength". Unless your "m" is exteremely large- larger than your computer allows for "int"s- just do a loop, taking x= 0 to m-1, and multiplying by "a" until you get the remainder equal to c