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

  • Thread starter booney1983
  • Start date
In summary, the conversation discusses solving a problem with the equation ax = c (mod m) and explains the steps involved in solving such equations. The suggested method is to solve the diophantine equation ax- mn= c for x and m, but this can be complicated. Instead, a simpler method of brute force using a loop is recommended, unless the value of m is too large for the computer to handle.
  • #1
booney1983
4
0
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...
 
Physics news on Phys.org
  • #2
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:

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

What is the concept of solving ax = c (mod m)?

The concept of solving ax = c (mod m) involves finding the value of x that satisfies the given equation, where a and c are integers and m is a positive integer.

Why is solving ax = c (mod m) important in mathematics?

Solving ax = c (mod m) is important in mathematics because it is used in various areas such as number theory, cryptography, and abstract algebra. It also helps in solving problems related to congruences and modular arithmetic.

What are the steps involved in solving ax = c (mod m)?

The steps involved in solving ax = c (mod m) are:

  • Step 1: Find the modular inverse of a modulo m
  • Step 2: Multiply both sides of the equation by the modular inverse
  • Step 3: Simplify the equation to get the value of x

How do I find the modular inverse of a modulo m?

The modular inverse of a modulo m can be found using the extended Euclidean algorithm. This algorithm involves finding the greatest common divisor (GCD) of a and m, and then using this GCD to find the modular inverse.

Can solving ax = c (mod m) have multiple solutions?

Yes, solving ax = c (mod m) can have multiple solutions, depending on the values of a, c, and m. For example, if a and m are relatively prime, then there will be a unique solution for x. However, if they are not relatively prime, there may be multiple solutions for x.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • General Math
Replies
1
Views
1K
Replies
1
Views
166
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
1
Views
980
Replies
13
Views
2K
  • Introductory Physics Homework Help
Replies
3
Views
1K
  • Advanced Physics Homework Help
Replies
12
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
Back
Top