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