(New page: 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 ...) |
|||
| Line 16: | Line 16: | ||
Notice that there are U(t) such k's. | Notice that there are U(t) such k's. | ||
| + | |||
| + | ---- | ||
Revision as of 07:11, 22 February 2009
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.
