For week 7: Show that |U(st)| = |U(s)| * |U(t)| provided that gcd(s,t)=1.
Hint: Suppose (c mod st) is in U(st). Show that (c mod s) is in U(s). That sets up a map from U(st) to U(s).
Next show that each (a mod s) gets hit U(t) times as follows. Prove that if (c mod st) maps to (a mod s) then we must have c=a+ks for some k between 0 and t-1, and that we want to find the k's in this range for which a+ks is coprime to t.
Now recall that gcd(s,t)=1 so that there is an equation xs+yt=1. Conclude a=axs+ayt, feed that into a+ks and conclude that we want the k's in the given range for which ax+k is coprime to t.
Notice that there are U(t) such k's.
Are we just supposed to write a proof that follows the hint?
--Jrendall 13:02, 22 February 2009 (UTC)
