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

Powered by vBulletin® Version 4.2.5 Copyright © 2019 vBulletin Solutions Inc. All rights reserved.