I actually managed to write the thing, and it works. I have never written anything like this before, so it was an interesting experiment.
Of course, to write it, I had to write a function to calculate the multiplicative inverse of a number in [1..N-1] (mod N), so naturally the first thing I wanted to do with it when I was done is see what polynomial generates the multiplicative inverse.
My solver only works for prime values of N, and the result was interesting:
x-1 = x (mod 3)
x-1 = x3 (mod 5)x-1 = x5 (mod 7)
x-1 = x9 (mod 11)
The pattern here, of course, is that x-1 = xN-2 (mod N). The Wikipedia article on modular multiplicative inverse mentions that this precise formula works, but only for prime values of N.
My current solver only works for polynomials of a single indeterminate, but I ought to be able to write one that works for multiple indeterminates. If I get the time to do it, the first thing I'm going to look at is the inverses of the exponent function.