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? I couldnt find anything... I'm not sure how to go about this problem at all. --Clwarner 22:50, 25 February 2009 (UTC)
Consider the map $ \scriptstyle\phi(c\ mod\ st)\ =\ (c\ mod\ s,\ c\ mod\ t) $. Obviously, $ \scriptstyle c\ mod\ st\ \in\ Z_{st} $, $ \scriptstyle c\ mod\ s\ \in\ Z_s $, and $ \scriptstyle c\ mod\ t\ \in\ Z_t $, so $ \scriptstyle(c\ mod\ s,\ c\ mod\ t)\ \in\ Z_s\oplus Z_t $. From this we know that $ \scriptstyle\phi $ is a map from $ \scriptstyle Z_{st} $ to $ \scriptstyle Z_s\oplus Z_t $. We will eventually restrict this further to $ \scriptstyle\phi:\ U(st)\ \rightarrow\ U(s)\oplus U(t) $.
First let's show that $ \scriptstyle\phi $ is a well-defined mapping. Assume that $ \scriptstyle c\ mod\ st\ =\ d\ mod\ st $. We must show that $ \scriptstyle\phi(c\ mod\ st)\ =\ \phi(d\ mod\ st) $. Through some simple modular arithmetic, $ \scriptstyle(c-d)\ mod\ st\ =\ 0 $, and $ \scriptstyle st\mid(c-d) $.
$ \scriptstyle\Rightarrow\ s\mid(c-d) $, $ \scriptstyle t\mid(c-d) $
$ \scriptstyle\Rightarrow\ c\ mod\ s\ =\ d\ mod\ s $, $ \scriptstyle c\ mod\ t\ =\ d\ mod\ t $
$ \scriptstyle\Rightarrow\ (c\ mod\ s,\ c\ mod\ t)\ =\ (d\ mod\ s,\ d\ mod\ t) $
$ \scriptstyle\Rightarrow\ \phi(c\ mod\ st)\ =\ \phi(d\ mod\ st)\ \checkmark $
Now, is the map $ \scriptstyle\phi $ operation-preserving? Indeed it is, because:
$ \scriptstyle\phi(cd\ mod\ st)\ =\ (cd\ mod\ s,\ cd\ mod\ t) $
$ \scriptstyle=\ (c\ mod\ s\ \cdot\ d\ mod\ s,\ c\ mod\ t\ \cdot\ d\ mod\ t) $
$ \scriptstyle=\ (c\ mod\ s,\ c\ mod\ t)\ \cdot\ (d\ mod\ s,\ d\ mod\ t) $
$ \scriptstyle=\ \phi(c\ mod\ st)\phi(d\ mod\ st).\ \checkmark $
Next we'll show that $ \scriptstyle\phi $ is injective. If $ \scriptstyle\phi(c\ mod\ st)\ =\ \phi(d\ mod\ st) $, then we must show that $ \scriptstyle(c\ mod\ st)\ =\ (d\ mod\ st) $:
$ \scriptstyle(c\ mod\ s,\ c\ mod\ t)\ =\ (d\ mod\ s,\ d\ mod\ t) $
$ \scriptstyle\Rightarrow\ c\ mod\ s\ =\ d\ mod\ s,\ \ c\ mod\ t\ =\ d\ mod\ t $
$ \scriptstyle\Rightarrow\ s\mid(c-d),\ \ t\mid(c-d) $.
We know that $ \scriptstyle s $ and $ \scriptstyle t $ are coprime, so $ \scriptstyle st $ must also divide $ \scriptstyle(c-d) $.
$ \scriptstyle\Rightarrow\ c\ mod\ st\ =\ d\ mod\ st.\ \checkmark $
Now for the tricky part. We've shown that $ \scriptstyle\phi $ is well-defined, operation-preserving, and one-to-one, so we just need to show that the image of $ \scriptstyle U(st) $ is onto $ \scriptstyle U(s)\oplus U(t) $.
Assume $ \scriptstyle c\ mod\ st\ \in\ U(st) $. Then $ \scriptstyle gcd(c,st)\ =\ $ 1. $ \scriptstyle c $ and $ \scriptstyle st $ share no common divisors (besides 1), so $ \scriptstyle gcd(c,s)\ =\ $ 1 and $ \scriptstyle gcd(c,t)\ =\ $ 1. Therefore, $ \scriptstyle c\ mod\ s\ \in\ U(s),\ \ c\ mod\ t\ \in\ U(t) $.
$ \scriptstyle\Rightarrow\ \phi(c\ mod\ st)\ =\ (c\ mod\ s,\ c\ mod\ t)\ \in\ U(s)\oplus U(t) $.
It's clear that the image of $ \scriptstyle U(st) $ is in $ \scriptstyle U(s)\oplus U(t) $.
Now, since $ \scriptstyle s $ and $ \scriptstyle t $ are relatively prime, there exist integers $ \scriptstyle x,y\in\mathbb{Z} $ such that $ \scriptstyle xs\ +\ yt\ =\ $ 1. Suppose that $ \scriptstyle(c\ mod\ s,\ d\ mod\ t)\ \in\ U(s)\oplus U(t) $.
$ \scriptstyle\Rightarrow\ cxs\ +\ cyt\ =\ c $, $ \scriptstyle dxs\ +\ dyt\ =\ d $
We know that $ \scriptstyle yt\ mod\ s\ =\ xs\ mod\ t\ =\ 1 $, so:
$ \scriptstyle\Rightarrow\ cxs\ mod\ s\ =\ 0, $ $ \scriptstyle cyt\ mod\ s\ =\ c\ mod\ s, $ $ \scriptstyle dxs\ mod\ t\ =\ d\ mod\ t, $ $ \scriptstyle dyt\ mod\ t\ =\ 0 $.
$ \scriptstyle\phi\textstyle(\scriptstyle(cyt\ +\ dxs)\ mod\ st\textstyle)\scriptstyle\ =\ \textstyle(\scriptstyle(cyt\ +\ dxs)\ mod\ s,\ (cyt\ +\ dxs)\ mod\ t\textstyle) $ $ \scriptstyle=\ (cyt\ mod\ s,\ dxs\ mod\ t) $ $ \scriptstyle=\ (c\ mod\ s,\ d\ mod\ t) $
Since $ \scriptstyle\phi\textstyle(\scriptstyle(cyt\ +\ dxs)\ mod\ st\textstyle)\scriptstyle\ =\ (c\ mod\ s,\ d\ mod\ t) $, we just have to show that $ \scriptstyle(cyt\ +\ dxs)\ mod\ st $ is in $ \scriptstyle U(st) $, because this will show that for every $ \scriptstyle\beta $ in $ \scriptstyle U(s)\oplus U(t) $ there is an $ \scriptstyle\alpha $ in $ \scriptstyle U(st) $ such that $ \scriptstyle\phi(\alpha)\ =\ \beta $.
So, observe that $ \scriptstyle cyt\ +\ dxs $ is in the class of $ \scriptstyle c\ modulo\ s\ =\ \{\ldots,c-2s,c-s,c,c+s,c+2s,\ldots\} $, because $ \scriptstyle yt\ mod\ s\ =\ $ 1.
$ \scriptstyle cyt\ +\ dxs $ is also in the class of $ \scriptstyle d\ modulo\ t\ =\ \{\ldots,d-2t,d-t,d,d+t,d+2t,\ldots\} $, because $ \scriptstyle xs\ mod\ t\ =\ $ 1.
Because $ \scriptstyle c\ mod\ s\ \in\ U(s) $, we know that $ \scriptstyle cyt\ +\ dxs $ is relatively prime to s. Similarly, because $ \scriptstyle d\ mod\ t\ \in\ U(t) $, we know that $ \scriptstyle cyt\ +\ dxs $ is relatively prime to t. $ \scriptstyle cyt\ +\ dxs $, $ \scriptstyle s $, and $ \scriptstyle t $ share no common divisors other than 1, so $ \scriptstyle cyt\ +\ dxs $ must then be relatively prime to $ \scriptstyle st $ as well.
Thus, $ \scriptstyle(cyt\ +\ dxs)\ mod\ st\ \in\ U(st) $, and $ \scriptstyle\phi $ is onto $ \scriptstyle U(s)\oplus U(t) $.
We have shown that $ \scriptstyle\phi $ is a well-defined bijective mapping from $ \scriptstyle U(st) $ to $ \scriptstyle U(s)\oplus U(t) $ that preserves the group operation, so $ \scriptstyle U(st) $ is therefore isomorphic to $ \scriptstyle U(s)\oplus U(t) $ when $ \scriptstyle gcd(s,t)\ =\ $ 1.
Since $ \scriptstyle U(st)\ \approx\ U(s)\oplus U(t) $ when $ \scriptstyle s $ and $ \scriptstyle t $ are coprime, $ \scriptstyle\mid U(st)\mid $ must equal $ \scriptstyle\mid U(s)\oplus U(t)\mid $. But then obviously $ \scriptstyle\mid U(s)\oplus U(t)\mid\ =\ \mid U(s)\mid\cdot\mid U(t)\mid $, so it follows that $ \scriptstyle\mid U(st)\mid\ =\ \mid U(s)\mid\cdot\mid U(t)\mid $ provided that $ \scriptstyle gcd(s,t)\ =\ $ 1. $ \scriptstyle\Box $
- --Nick Rupley 23:45, 25 February 2009 (UTC)
Sorry, it's a little bit different of a method than the hint that Uli gave in the question employs, but it made more sense to me to do it this way (and it's essentially doing the same thing anyway).
- --Nick Rupley 23:52, 25 February 2009 (UTC)
Well, that is just impressive. I think I can speak for the whole class when I say thanks and you rock.
--Jniederh 01:37, 26 February 2009 (UTC) I agree thank you for the solution to this problem. I was working on this one for a long time. Thanks again.--Nswitzer 19:11, 26 February 2009 (UTC)
