1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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: Mar 8, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular question
  1. A question (Replies: 1)

  2. FTC Question (Replies: 16)

  3. Trigonometry Question (Replies: 1)

  4. Integration question (Replies: 4)

Loading...