Revision as of 08:11, 22 February 2009 by Podarcze (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett