Modular Operators and Multiple Variables? Extended Euclidean Algorithm and Chinese Remainder TheoremDate: 05/28/2011 at 14:21:49 From: Thomas Subject: Solve s set of linear equations with different modulo values Hi, I stumbled upon a problem and wonder if there is an efficient algorithm for solving it. In principle, these are linear equations involving different modulo values. The goal is to find some pattern for constructing valid (non-zero) c and x values that satisfy all of the equations below. (c - 2*x + 3)%m 245 = 0 (c - 2*x)%m 2 = 0 (c - 2*x)%m 73 = 0 (c - 2*x + 8)%m 10 = 0 (c - 2*x + 15)%m 649 = 0 I'd like to apply the Euclidean algorithm to solve these equations, much as I would if only one variable were involved. It's unclear to me whether there is an efficient algorithm for solving such two-variable equations. In fact, does the modulo operator make them Diophantine? Thanks, Thomas Date: 05/29/2011 at 21:24:57 From: Doctor Vogler Subject: Re: Solve s set of linear equations with different modulo values Hi Thomas, Thanks for writing to Dr. Math. Are you familiar with the Chinese Remainder Theorem (CRT)? It says that if you have some (finite) set of integers m, no two of which share a common prime factor, and an integer a for each m, then the simultaneous equations of the form ... (x - a)%m = 0 ... are equivalent to a single equation ... (x - A)%M = 0, ... where M is the product of all of the m in your set, and there is a formula to compute the number A. Actually, mathematicians would normally write ... x = A (mod M) ... instead of (x - A)%M = 0. We would write that regardless of whether A were, for example, smaller than M, or positive. For example, suppose you have the equations z = 3 mod 5 z = 3 mod 49 z = 0 mod 2 z = 0 mod 73 z = 15 mod 11 z = 15 mod 59 The first two are equivalent to z = 3 mod (5*49) The next two are equivalent to z = 0 mod (2*73) And the last two are equivalent to z = 15 mod (11*59) The CRT says that, for some number A, these are equivalent to one equation of the form z = A mod (5*49*2*73*11*59) To compute A, first we have to use the Extended Euclidean Algorithm, or something similar, to find several multiplicative inverses. A multiplicative inverse of r mod m is an integer k such that k*r = 1 mod m Alternately, (k*r - 1)%m = 0 We compute multiplicative inverses of 2*73*11*59 mod 5*49 5*49*11*59 mod 2*73 5*49*2*73 mod 11*59 The answers are 1/(2*73*11*59) = 4 mod 5*49 1/(5*49*11*59) = 93 mod 2*73 1/(5*49*2*73) = 225 mod 11*59 Now we compute A like so: A = (2*73*11*59)*4*3 + (5*49*11*59)*93*0 + (5*49*2*73)*225*15 = 5787148 mod 5*49*2*73*11*59 You should check that this number A is 3 mod 5 3 mod 49 0 mod 2 0 mod 73 15 mod 11 and 15 mod 59 Now, what does this have to do with your problem? Well, you want to describe solutions to these equations: (c - 2*x + 3)%m 245 = 0 (c - 2*x)%m 2 = 0 (c - 2*x)%m 73 = 0 (c - 2*x + 8)%m 10 = 0 (c - 2*x + 15)%m 649 = 0 Or, as a mathematician would write them: c - 2*x + 3 = 0 mod 245 c - 2*x = 0 mod 2 c - 2*x = 0 mod 73 c - 2*x + 8 = 0 mod 10 c - 2*x + 15 = 0 mod 649 Well, since the CRT requires that numbers have no common factors, first we should split up the larger numbers into prime-power factors. So 245 = 5*49, and 649 = 11*59. By using the CRT in reverse, this means that your five equations are equivalent to c - 2*x + 3 = 0 mod 5 c - 2*x + 3 = 0 mod 49 c - 2*x = 0 mod 2 c - 2*x = 0 mod 73 c - 2*x + 8 = 0 mod 2 c - 2*x + 8 = 0 mod 5 c - 2*x + 15 = 0 mod 11 c - 2*x + 15 = 0 mod 59 If you notice the equivalence of the two equations mod 2 and the two equations mod 5, then you may reduce these to c - 2*x + 3 = 0 mod 5 c - 2*x + 3 = 0 mod 49 c - 2*x = 0 mod 2 c - 2*x = 0 mod 73 c - 2*x + 15 = 0 mod 11 c - 2*x + 15 = 0 mod 59 But remember that we went to all this trouble to compute that number A = 5787148 which was 3 mod 5, 3 mod 49, 0 mod 2, 0 mod 73, 15 mod 11, and 15 mod 59? Well, that means that your equations are the same as c - 2*x + 5787148 = 0 mod 5 c - 2*x + 5787148 = 0 mod 49 c - 2*x + 5787148 = 0 mod 2 c - 2*x + 5787148 = 0 mod 73 c - 2*x + 5787148 = 0 mod 11 c - 2*x + 5787148 = 0 mod 59 By the CRT, they are also equivalent to c - 2*x + 5787148 = 0 mod 5*49*2*73*11*59. So all (x, c) solutions can be generated by letting x be any integer and then setting c = 2*x - 5787148 + 5*49*2*73*11*59*(an integer). Notice that c will always be even. Alternately, you can let c be any even integer, and then set x = (c/2) + 2893574 + 5*49*73*11*59*(an integer). Either way will give you all solutions. 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: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/