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)
Apparently so, but I don't understand how to prove that (c mod s) is in U(s). In general I have a hard time with the concept of mapping.
Can anyone explain this proof in more detail?
-K. Brumbaugh
I'm not sure about that either. I think there was an example of it in the notes or book. I can't remember.
--Jrendall 19:25, 25 February 2009 (UTC)
Is there anything useful in our solution to Q1 from the file that can be applied to Q3?
