How to solve equations with mod?

  • Thread starter Thread starter Goldenwind
  • Start date Start date
  • Tags Tags
    Solving equations
AI Thread Summary
To solve the equation (a * x) mod b = 1, it's essential to recognize that multiple integer solutions exist due to the nature of modular arithmetic. The variable Z can represent any integer, leading to a general solution of x = (Z * b + 1) / a. For small values of b, trial and error can be effective, while larger values may require the Euclidean division algorithm for a systematic approach. Understanding that x can take on multiple values, including x + b, is crucial for programming applications. The discussion emphasizes the importance of recognizing the structure of modular equations and the methods available for solving them.
Goldenwind
Messages
145
Reaction score
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


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.
 


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:


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:


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.
 
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...
Back
Top