From: Dave Rusin <rusin@math.niu.edu>
Subject: Re: Multiplying congruences
Date: Wed, 5 Jan 2000 11:36:46 -0600 (CST)
Newsgroups: sci.math
To: mlugo@thelabelguy.com
Summary: Chinese Remainder Theorem

In article <s72rgqa05k260@corp.supernews.com> you write:

>Yesterday I was trying to solve a problem (I abandoned this approach now)
>and arrived at the system of congruences:
>
>a = 1 (mod p)
>b = 1 (mod q)
>
>with p, q relatively prime.  From this, it follows that
>
>p | a-1
>q | b-1
>
>and thus pq | ab-a-b+1
>
>ab - a - b = -1 (mod pq).
>
>OK, that was straightforward enough.  But what about the general system of
>integer congruences
>
>a = m (mod p)
>b = n (mod q)
>
>How can we "multiply" these to give a congruence modulo pq?

Not really sure what you're trying to accomplish. In case you haven't seen
it, you should be aware of the

Chinese Remainder Theorem: if  p  and  q  are coprime then for every pair
of integers  m  and  n  there exists and integer  k  such that the
statements
        x = k mod pq
and
	(x = m mod p) and (x = n mod q)
are logically equivalent (i.e. the first is true for precisely the same
integers  x  for which the second, compound, statement is true).

Moreover, the proof is constructive if you know how (using the Euclidean
algorithm) to find a pair of integers  r, s  making  p r + q s = 1.
For then  p r = 1  mod  q  so  p r n = n  mod  q  and hence
(p r n + q s m) = n  mod  q; likewise we observe that
(p r n + q s m) = m  mod  p. So  k = (p r n + q s m)  is the integer we seek.

dave