Solving a System of Modular Equations with Multiple Variables

Date: 12/15/2004 at 15:01:30
From: Colin
Subject: Modular equations with multiple variables

Hello, 

I have the following question which looked simple to me at first 
glance, but is actually a difficult to solve set of modular equations.

(1919ab) mod 5107 = 1
1919(a+1)(b-1) mod 5108 = 5047
1919(a+2)(b-2) mod 5109 = 1148
1919(a+3)(b-3) mod 5110 = 3631	
1919(a+4)(b-4) mod 5111 = 2280	

Is there a way to solve these equations?  I can only generate answers
for the first equation.  I do not know how to work with the other 
equations, since I do not know how to use the Chinese remainder 
theorem on multiple variables.

I tried to expand the formulas, 1919ab-1919a+1919b-1 mod 5108=5047
and so on, but that doesn't bring me closer to the answer.  I do
however believe that there is only one answer possible for a and b
between 1 and 5107.

The other thing I tried is writing a program that generates answers, 
but I must do that for every number and also have to test for 
primality and (a+1)((b-1) and so on, so this takes forever.

Date: 12/15/2004 at 16:29:34
From: Doctor Vogler
Subject: Re: Modular equations with multiple variables

Hi Colin,

Thanks for writing to Dr. Math.  That's a very interesting question!

Well, the first thing to do is to divide each equation (or 
equivalence) by 1919.  That requires computing the modular inverse of
1919 mod each of 5107, 5108, 5109, 5110, and 5111.  The easiest way to
do that is with the Euclidean algorithm (or a math computer program
that implements it).  You'll have no trouble except in the last case,
where you find that 19 is a divisor of both 1919 and 5111 (so there is
no modular inverse).  In fact, 19 is also a divisor of 2280; otherwise
there would have been no solutions to the last equation and therefore
no solution to the system of equations.  So you change the last
equation to

  101(a+4)(b-4) = 120 (mod 269),

where I've divided 1919, 2280, and 5111 by 19.  Then you find the
modular inverse of 101 mod 269.  After multiplying by the modular
inverses, you find the remarkable fact that the results on the right
are all very close together.  Add that constant from the left side,
and then you find that these numbers were carefully chosen to create
the following pattern:

  ab           = 165 (mod 5107)
  ab -  a +  b = 166 (mod 5108)
  ab - 2a + 2b = 167 (mod 5109)
  ab - 3a + 3b = 168 (mod 5110)
  ab - 4a + 4b = 169 (mod  269).

You have three sets of numbers that count.  If you subtract the
modulus from each of the other two numbers, you get the same equation
five times:

  ab - 5107a + 5107b = -4942 (mod 5107)
  ab - 5107a + 5107b = -4942 (mod 5108)
  ab - 5107a + 5107b = -4942 (mod 5109)
  ab - 5107a + 5107b = -4942 (mod 5110)
  ab - 5107a + 5107b = -4942 (mod  269)

That means that you have

  ab - 5107a + 5107b + 4942

is divisible by the LCM of 5107, 5108, 5109, 5110, and 269, which
happens to be

  91600075916256180.

So now you rewrite this as

  (a + 5107)(b - 5107) = 4241*6151 (mod 91600075916256180).

You'll find that if a and b are remotely small, then the product on
the left will be much smaller than the modulus, so that the two
factors will have to be 4241 and 6151 (which are both prime).  If you
also want a and b to be positive, then there is only one way to assign
those factors.

On the other hand, if you wanted all integer solutions, then you can
choose any integer m which is relatively prime to the giant modulus
(i.e. relatively prime to 5107, 5108, 5109, 5110, and 269), compute
the modular inverse of m mod that giant modulus (call the inverse n),
and then either let

  a = m - 5107
  b = 4241*6151*n + 5107 + 91600075916256180*k

for any integer k, or let

  b = m + 5107
  a = 4241*6151*n - 5107 + 91600075916256180*k

for any integer k.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/