Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular question

  1. Mar 8, 2008 #1
    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...
  2. jcsd
  3. Mar 8, 2008 #2


    User Avatar
    Science Advisor

    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
    Last edited by a moderator: Mar 8, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook