Modular question

  • Thread starter booney1983
  • Start date
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

Science Advisor
41,618
821
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:

Want to reply to this thread?

"Modular question" You must log in or register to reply here.

Related Threads for: Modular question

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Top Threads

Top