How to solve equations with mod?

[Goldenwind]

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?

 

[mfb]

There are many websites covering basic operations of modular arithmetic.

Something you can consider first: if x₀ is a solution, what about x₀+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.

 

[Goldenwind]

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.

 

[rcgldr]

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.

 

[HallsofIvy]

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.