Okay, so here's an example of where dropping out of math classes after Differential Equations is coming back to bite me a bit. I'm working on a kind of puzzle, mostly for fun, but possibly to incorporate into a future software product.
At its most basic, the solution process for the puzzle turns out to be solving a system of simultaneous equations. Which is something I learned how to do way back in High School, and for linear equations, I can even find off-the-shelf algorithms and libraries for doing so.
The catch, of course, is that these aren't linear equations. They use modular arithmetic, which is something I understand at a basic level, like anybody who programs for a living probably does, but I don't know where to even start breaking this down to solve a non-trivial version, and Google isn't helping me.
Let's start with a simple linear example:
5x + 7y + 4 = 0
4x + 3y + 1 = 0
Use whatever method you like, and you get:
x = 0.3846
y = -0.846
Piece of cake. Now, what if the equation looks like this?
5x + 7y + 4 = 0 (modulo 16)
4x + 3y + 1 = 0 (modulo 16)
If we want to find a few integer solutions for x and y, how do we find them? I could write a program to just guess every integer between 1 and 1,000,000 for each of the coefficients, and that'd find me a solution, but it doesn't scale well if I have a large number of variables. In the example equations given, there are rather a lot of solutions ([9,9],[9,25],[25,25]...), but I suspect that some other (carefully chosen?) sets of coefficients would have a much smaller set of solutions. Actually, that's kind of the point of the whole exercise.
Anyone out there got some hints for me?
Googling "simultaneous modular equations" got me:
http://en.wikibooks.org/wiki/Discrete_mathematics/Modular_arithmetic#Simultaneous_equations
and
http://www.nada.kth.se/~johanh/rsalowexponent.ps
,both of which are interesting, but not quite what I'm looking for.
For the case where the modulus is 2, addition is equivalent to XOR, and so logic minimization techniques from EE can be used, but it's not clear to me how to move those up to work in a higher modulus.
