Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Discrete MathReduce Function
Posted:
Oct 17, 1999 8:04 PM


I see that one of my students has asked for explanation of one of the standard problems that I give in my discrete math class, a problem which is closely related to the Chinese Remainder theorem and in fact requires a fair amount of careful methodical work to get all the parts worked out (purposely with big numbers).
Here is the general setting: For any positive integer m, let Zm denote the set of residues modulo m, {0,1,2,...,m1}, then there is a reduce map from Z to Zm given by t > Remainder(t,m), that is, just the usual function otherwise denoted by Mod(. ,m). Aside: No one should ever for teaching purposes use simultaneously the infix function notation '19 mod 11' for Mod(19,11) or Remainder(19,11), while at the same time using 'mod 11' as the name of the congruence relation modulo 11 where we write things like '30 congr. 19 mod 11'. This gets much too confusing for students.
Now given two pos. ints. m and k, we can define a paired reduce function from Z to Zm x Zk, given by t > (Mod(t,m), Mod(t,k)). It's a good exercise to see that this reduce map is surjective iff gcd(k,m)=1, and to find its exact image (or at least its size) when it's not surjective. Of course this reduce map actually factors through Z(m*k) and it is the induced map from Z(m*k) into Zm X Zk which I usually refer to as the reduce map. It's more interesting because of both sets being finite and in fact of the same size. Now for this reduce map, we can easily see that it is injective iff gcd(m,k)=1, and hence it is surjective under the same circumstances. Thus we have the Chinese Remainder theorem: every pair (a,b) is reduce(t) for some unique residue t. Here we have a nice invertible function, so I always have my students find explicitly its inverse. To do that I point out that Euclid's algorithm gives 1=r*m+s*k and so r*m congr. 0 mod m and r*m congr. 1 mod k while s*k congr. 1 mod m and s*k congr. 0 mod k. So let x be Mod(s*k, m*k), and let y be Mod(r*m, m*k) then reduce(x) = (1,0) and reduce(y) = (0,1). Then for any (a,b) in Zm X Zk, the pullback under reduce is Mod(a*x+b*y, m*k), so we have an explicit formula for the inverse function. Aside: Notice that 1 = x + y  m*k, and for example, if r*m is positive, then x = r*m and y = m*k + s*k , at least if you do Euclid's Algorithm the usual way so that both the final products r*m and s*k have abs. value less than m*k.
Now that the students have that done, I ask them to find all square roots of 1 in Z(m*k), and all t such that t^2 congr. t mod m*k, all nilpotent elements, etc. where of course the whole idea is to find first all pairs (a,b) where the a and b satisfy the required conditions, and then pull them back to Z(m*k). The point is to use this reduce map and its inverse to reduce the size of the integers involved in the arithmetic and the searches. Notice also that this reduce map when restricted to U(m*k), the invertible residues mod m*k, maps onto Um x Uk, and so we get the result phi(m*k)=phi(m)*phi(k).
And of course all of the above works for 3 or more relatively prime factors in the same way.



