Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Discrete Math--Reduce Function
Replies: 0

 Ladnor Geissinger Posts: 69 Registered: 12/4/04
Discrete Math--Reduce 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,...,m-1}, 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.