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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.