PDA

View Full Version : Modular math

PJYelton
09-30-2003, 12:36 PM
Im working on an algorithm where a section of it appears to boil down to a modular arithmetic problem, but unfortunately my modular math sucks. Does anyone here know how to solve modular equations?

Basically this is what I want. As an example, say Im trying to solve for x in the equation (4x-6)%7=0. Doing a little trial and error, you can find out that x=5+7n where n can be any integer>=zero, so 5, 12, 19 etc are all answers. But when dealing with big numbers, then trial and error obviously cant be done in my algorithm. So does anyone know how to solve the generic equation (Ax-B)%C=0?

Clyde
09-30-2003, 12:44 PM
I don't know much modular maths but can't you just use (Ax-B)/C = n

-> x = (Cn +B)/A

PJYelton
09-30-2003, 01:27 PM
Oops, don't think I was completely clear, all variables (A,B,C,x,n) must be integers. The problem with solving something like (Ax-B)/C = n and then just plugging values for n and solving for x is that x can only be an integer. So like in my above example, (4x-6)/7=n, if n=0 then x=3/2, if n=1 then x=13/4, but if n=2 then we are good since x=5. But the only way to find out which values of n produce an integer that I know of is by doing brute force, which is out of the question if the numbers are say over a million.

confuted
09-30-2003, 01:45 PM
Isn't solving for integer solutions known as "Diophantine equations"?

Zach L.
09-30-2003, 06:54 PM
More specifically, linear Diophantine equations (in this particular case). Just a quick note, in "x=5+7n", n need not be positive; it only needs to be an integer.

As for how to solve it, I'm not entirely sure. I am relatively sure, however, that it is non-trivial at best. I know that www.generation5.org has a GA solver for linear Diophantine equations, you might want to look at that.

PJYelton
10-01-2003, 08:35 AM
Bah, I had no idea this would turn out to be such a pain... thanks all, guess I 'll get studying on Diophantine equations :D