Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Modular Operators and Multiple Variables?

Date: 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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/