How to solve equations with mod?

Taking k= 2, x= -9+ 64= 55. 7(55)= 385= 12(32)+ 1. Taking k= 3, x= -9+ 96= 87. 7(87)= 609= 19(32)+ 1.
  • #1
Goldenwind
146
0
Solving equations with "mod"

Homework Statement


I have a homework problem. I'm in computer science, however one of my programs requires me to solve this equation. I'm afraid it's beyond my expertise.

(a * x) mod b = 1

This needs to be rearranged in the form of x = ...
Due to the existence of "mod", I get confused.

Please don't solve it for me. I'm just looking for a little nudge to help me get over this hump.

Homework Equations


See above.

The Attempt at a Solution


My main goal solving this was to try and get rid of that "mod". Thinking about it logically, if x mod y = 0, that means that x / y = Z, where Z is some integer. I also believe it means there exist values of x and y such that all integer values of Z would exist.

Base equation
(a * x) mod b = 1

Subtracting 1 from both sides
((a * x) - 1) mod b = 0

Converting to division
((a * x) - 1) / b = Z

Solve like normal
x = (Z*b + 1) / a

Now the problem is, the Z is throwing me off. Do I just choose a value? It would make sense for remainders that there are multiple values of x that keep the equation in balance. Due to this being programming, x can be my only unknown. Am I on the right track?
 
Physics news on Phys.org
  • #2


There are many websites covering basic operations of modular arithmetic.

Something you can consider first: if x0 is a solution, what about x0+b?

Now the problem is, the Z is throwing me off. Do I just choose a value?
You would have to choose a value such that x is an integer. No, that does not work (unless you want to guess - possible, but inefficient), but there are methods to solve the original equation for x, for example a simplified version of the extended euclidean algorithm.
 
  • #3


I've looked up plenty of sites, but all of the things are far, far above my comprehension. I guess what I'm (potentially stupidly) expecting is something like:

"a mod b = 1" --> "(a + 1) / b = 0", or:
"x / y" --> "x * (1/y)"

Something I can use to isolate x such that I may continue my coding. I need to emphasize, even though math is related to my field, I'm not a math person. I don't understand all of the complicated things I see on Wikipedia and other sites like this:

http://upload.wikimedia.org/math/3/0/8/308f894eed1a6fe2f4921fbc747db4e8.png

I've done plenty of research, but I'm not finding anything simple like above. Perhaps it's not as simple as I think? Perhaps there's just not that much coverage. In the end, I'm not sure.

~

Edit: I'm starting to see what you were saying by x, versus x+b. That would reinforce my logic that there must be multiple solutions, which doesn't make sense in my scenario. Perhaps the assignment is broken... I will look into this further.
 
Last edited:
  • #4


Goldenwind said:
x = (Z*b + 1) / a

Now the problem is, the Z is throwing me off. Do I just choose a value? It would make sense for remainders that there are multiple values of x that keep the equation in balance. Due to this being programming, x can be my only unknown.

You have the correct answer. Z can be any integer (negative, zero, positive). x is the only unknown, but it has multiple values.

If this was finite field math modulo b, then a, x, and Z would be limited to the range {0, ..., b-1}, and there would be only one solution for x (and Z) for given a and b. There are algorithms to solve this, but I'm not sure if there is a formula.
 
Last edited:
  • #5


There are fundamentally two ways to solve a such an equation.

1) If in the equation ax= 1 (mod b) b is relatively small, you can just do "trial and error": to solve 3x= 1 (mod 5), note that if
a) x= 0, 3(0)= 0, not 1
b) x= 1, 3(1)= 3, not 1
c) x= 2, 3(2)= 6= 5+ 1 and so is 1 (mod 5). x= 2 is the answer. Of course, if you are not just considering the "base values" between 0 and 5, x= 2+ 5n for any integer n is the general answer.

2) If b is rather large, you can use the "Euclidean division algorithm". To solve 7x= 1 (mod 32), Write it as 7x= 1+ 32n or 7x- 32n= 1. Now
7 divides into 32 four times with remainder 4: 32- 4(7)= 4.
4 divides into 7 once with remainder 3: 7- 4= 3.
3 divides into 4 once with remainder 1: 4- 3= 1.

Replace the "3" in 4- 3= 1 with 7- 4 from the previous equation: 4- (7- 4)= 2(4)- 7= 1.
Replace the "4" in 2(4)- 7= 1 with 32- 4(7) from the previous equation: 2(32- 4(7))- 7= 2(32)- 9(7)= 1. We can also write this as (-9)(7)- (-2)(32)= 1 and comparing that with the original equation, 7x- 32n= 1 we see that x= -9 and n= -2 is a solution. But it is easy to see that x=-9+ 32k, n= -2+ 7k is also a solution for any integer k:
7(-9+ 32k)- 32(-2+ 7k)= -63+ 7(32)k+ 64+ (32)(7)k= -63+ 64= 1 because the 7(32)k terms cancel.

So x= -9+ 32k is the general solution or, taking k= 1, x= -9+ 32= 23 is the solution between 0 and 32.

Check: 7(23)= 161= 5(32)+ 1.
 

1. How do you solve equations with mod?

To solve equations with mod, you must first understand the basic rules of modular arithmetic. This includes understanding the modulus operator (%), which gives the remainder of a division operation. To solve an equation with mod, you must isolate the variable on one side of the equation and use the modulus operator to find its possible values on the other side.

2. What is the purpose of using mod in equations?

The purpose of using mod in equations is to find the possible values of a variable within a given range. This is useful in various applications such as cryptography, computer programming, and solving real-world problems involving remainders.

3. Can you solve equations with mod using fractions or decimals?

Yes, you can solve equations with mod using fractions or decimals. However, it is important to remember that the modulus operator only works with integers, so the final answer may need to be rounded or converted to a fraction depending on the context of the problem.

4. What are the common mistakes to avoid when solving equations with mod?

One common mistake to avoid is forgetting to use the modulus operator when isolating the variable on one side of the equation. Another mistake is not considering all possible values of the variable within the given range. It is also important to be careful when dealing with negative numbers, as the modulus operator may give unexpected results.

5. Are there any shortcuts or tricks for solving equations with mod?

Yes, there are some shortcuts and tricks for solving equations with mod. One is the use of the Chinese Remainder Theorem, which can simplify the process for solving systems of linear congruences. Another trick is to use patterns or symmetry to quickly determine the possible values of a variable within a given range.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
1
Views
864
  • Precalculus Mathematics Homework Help
Replies
5
Views
762
  • Precalculus Mathematics Homework Help
2
Replies
40
Views
4K
  • Precalculus Mathematics Homework Help
Replies
17
Views
907
  • Precalculus Mathematics Homework Help
Replies
5
Views
719
  • Precalculus Mathematics Homework Help
Replies
6
Views
238
  • Precalculus Mathematics Homework Help
Replies
6
Views
161
  • Precalculus Mathematics Homework Help
Replies
25
Views
380
  • Precalculus Mathematics Homework Help
Replies
12
Views
387
  • Precalculus Mathematics Homework Help
Replies
19
Views
1K
Back
Top