Let $ \scriptstyle p $ be a prime. Describe $ \scriptstyle U(p^n) $ and find the order of this group. Using your guess from HW3 in Chapter 3 now predict $ \scriptstyle\mid U(750)\mid $.
To gain some insight into this problem, lets compute $ \scriptstyle U(p^n) $ for a few values of $ \scriptstyle n $. Let $ \scriptstyle p $ be 3, for simplicity purposes.
$ \scriptstyle U(3^1)\ =\ \{1,2\} $
$ \scriptstyle U(3^2)\ =\ \{1,2,4,5,7,8\} $
$ \scriptstyle U(3^3)\ =\ \{1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26\} $
Notice how the only gaps in the sequence of numbers $ \scriptstyle\{1,2,\ldots,p^n-1,p^n\} $ are those numbers divisible by $ \scriptstyle p $. Since $ \scriptstyle p $ is prime, we should expect this. The question then boils down to exactly how many of these gaps there are. In $ \scriptstyle U(3) $, there is one gap (including $ \scriptstyle p^n $). In $ \scriptstyle U(9) $ there are three, and in $ \scriptstyle U(27) $, there are nine. It would seem that the number of such gaps is equal to the prime power of the previous unit group. Then, the order of the group $ \scriptstyle U(p^n) $ would be $ \scriptstyle p^n-p^{n-1} $. Let's try to prove this.
Observe that for $ \scriptstyle n=1 $, $ \scriptstyle U(p^n)\ =\ U(p)\ =\ \{1,2,\ldots,p-2,p-1\} $, with no gaps (save for $ \scriptstyle p $ itself), such that $ \scriptstyle\mid U(p^n)\mid\ =\ p-1\ =\ p^1-p^0\ =\ p^n-p^{n-1}\checkmark $
Now assume that for an arbitrary but finite $ \scriptstyle n $, $ \scriptstyle\mid U(p^n)\mid\ =\ p^n-p^{n-1} $.
We now want to think of what happens when we move from $ \scriptstyle U(p^n) $ to $ \scriptstyle U(p^{n+1}) $. We now have the sequence $ \scriptstyle\{1,2,\ldots,p^{n+1}-1\} $, minus all the gaps due to the multiples of $ \scriptstyle p $. For now we can disregard all the numbers from $ \scriptstyle1 $ to $ \scriptstyle p^n $, since we already know how many gaps are in there.
Following $ \scriptstyle p^n $, we have $ \scriptstyle p^n+1,p^n+2,\ldots,p^n+p-2,p^n+p-1 $. The reason we have the $ \scriptstyle+p $ factor is because we want to approach the next multiple of $ \scriptstyle p $ without actually including it (obviously since it can't be included in the unit group of $ \scriptstyle p^{n+1} $). In similar fashion, the next "section" would be $ \scriptstyle p^n+p+1,p^n+p+2,\ldots,p^n+2p-2,p^n+2p-1 $.
This process of counting the elements in between the multiples of $ \scriptstyle p $ continues until we reach the end: $ \scriptstyle p^n+(p^n-p^{n-1}-1)\cdot p+1,\ p^n+(p^n-p^{n-1}-1)\cdot p+2,\ \ldots,\ p^n+(p^n-p^{n-1})\cdot p-2,\ p^n+(p^n-p^{n-1})\cdot p-1 $.
So, why is the last multiple of $ \scriptstyle p $ we are approaching $ \scriptstyle p^n+(p^n-p^{n-1})\cdot p $? Well, this is because $ \scriptstyle p^n+(p^n-p^{n-1})\cdot p\ =\ p^n+p^{n+1}-p^n\ =\ p^{n+1} $. Obviously the last multiple of $ \scriptstyle p $ we want to approach is $ \scriptstyle p^{n+1} $, since we are dealing with $ \scriptstyle U(p^{n+1}) $.
To recap, we have:
$ \scriptstyle U(p^{n+1})\ =\ \textstyle\{\scriptstyle\overbrace{\scriptstyle1,2,\ldots,p^n-2,p^n-1}^{p^n-p^{n-1}}\textstyle,\scriptstyle\ \ \overbrace{\scriptstyle p^n+1,p^n+2,\ldots,p^n+p-2,p^n+p-1}^{p-1}\textstyle, $
$ \scriptstyle\overbrace{\scriptstyle p^n+p+1,p^n+p+2,\ldots,p^n+2p-2,p^n+2p-1}^{p-1}\textstyle,\ \cdots, $
$ \scriptstyle\overbrace{\scriptstyle p^n+(p^n-p^{n-1}-2)\cdot p+1,\ p^n+(p^n-p^{n-1}-2)\cdot p+2,\ \ldots,\ p^n+(p^n-p^{n-1}-1)\cdot p-2,\ p^n+(p^n-p^{n-1}-1)\cdot p-1}^{p-1}\textstyle, $
$ \scriptstyle\overbrace{\scriptstyle p^n+(p^n-p^{n-1}-1)\cdot p+1,\ p^n+(p^n-p^{n-1}-1)\cdot p+2,\ \ldots,\ p^n+(p^n-p^{n-1})\cdot p-2,\ p^n+(p^n-p^{n-1})\cdot p-1\ =\ p^{n+1}-1}^{p-1}\textstyle\} $
Each section of elements (denoted by the overbraces) after $ \scriptstyle p^n $ contains exactly $ \scriptstyle p-1 $ elements, because we are counting the number of elements in between each multiple of $ \scriptstyle p $. We have $ \scriptstyle p^n-p^{n-1} $ such sections of length $ \scriptstyle p-1 $. This is because in each section, recall that we are "approaching" the next multiple of $ \scriptstyle p $. In the second overbrace we approach $ \scriptstyle p^n+1\cdot p $, in the third overbrace $ \scriptstyle p^n+2\cdot p $, and so on until in the last section we approach $ \scriptstyle p^n+(p^n-p^{n-1})\cdot p $.
Now, we can finally count the number of elements in $ \scriptstyle U(p^{n+1}) $. The first section has $ \scriptstyle p^n-p^{n-1} $ elements; this comes from the inductive assumption. We have also just shown that the remaining $ \scriptstyle p^n-p^{n-1} $ sections each have $ \scriptstyle p-1 $ elements, for a total of $ \scriptstyle (p^n-p^{n-1})*(p-1)\ =\ p^{n+1}-2p^n+p^{n-1} $ elements. Adding this to the number of elements from the first section, we have a grand total of:
$ \scriptstyle p^n-p^{n-1}+p^{n+1}-2p^n+p^{n-1}\ =\ p^{n+1}-p^n $ elements.
It follows that $ \scriptstyle\mid U(p^{n+1})\mid\ =\ p^{n+1}-p^n $.
We have proved that $ \textstyle(\scriptstyle\mid U(p^n)\mid\ =\ p^n-p^{n-1}\textstyle)\ \rightarrow\ (\scriptstyle\mid U(p^{n+1})\mid\ =\ p^{n+1}-p^n\textstyle) $, and have shown that $ \scriptstyle\mid U(p^n)\mid\ =\ p^n-p^{n-1} $ for $ \scriptstyle n=1 $, so by induction, $ \scriptstyle\mid U(p^n)\mid\ =\ p^n-p^{n-1} $ for all $ \scriptstyle n\in\mathbb{N} $. $ \scriptstyle\Box $
To predict $ \scriptstyle\mid U(750)\mid $, note that $ \scriptstyle750\ =\ 2*3*5*5*5\ =\ 6*5^3 $. $ \scriptstyle gcd(6,5^3)\ =\ 1 $, so by our conjecture in the Chapter 3 homework, $ \scriptstyle\mid U(750)\mid\ =\ \mid U(6)\mid*\mid U(5^3)\mid $. $ \scriptstyle U(6)\ =\ \{1,5\} $, so $ \scriptstyle\mid U(6)\mid\ =\ 2 $. We just proved that $ \scriptstyle\mid U(p^n)\mid\ =\ p^n-p^{n-1} $, so $ \scriptstyle\mid U(5^3)\mid\ =\ 5^3-5^2\ =\ 125-25\ =\ 100 $.
Thus, $ \scriptstyle\mid U(750)\mid\ =\ 2*100\ =\ 200 $.
- --Nick Rupley 03:03, 9 February 2009 (UTC)
well done.
I have a question of clarification. Should the above be:
To recap, we have:
$ \scriptstyle U(p^{n+1})\ =\ \textstyle\{\scriptstyle\overbrace{\scriptstyle1,2,\ldots,p^n-2,p^n-1}^{p^n-p^{n-1}}\textstyle,\scriptstyle\ \ \overbrace{\scriptstyle p^n+1,p^n+2,\ldots,p^n+p-2,p^n+p-1}^{p-1}\textstyle, $
?? In the original it's said the first overbrace has $ \scriptstyle p^n-p^{n+1} $ but I thought it contained $ \scriptstyle p^n-p^{n-1} $. (Especially since $ \scriptstyle p^n-p^{n+1} $ would be a negative number...) I'm not trying to be nit-picky, just trying to contribute for credit :) --Bcaulkin 00:27, 12 February 2009 (UTC)
Man this stuff is like a square peg in a round hole. Great work Nick. I'm still trying to understand the majority of it, but the result is quite cool. I think you should run a recitation.
Bcaulkin (sorry I don't know your name ^^;;), you're right, it should be $ \scriptstyle p^n-p^{n-1} $, my mistake. It's fixed now though.
Dane, thanks for the kind words, I'm just glad to help out (and call me crazy, but challenging proofs are kinda fun lol).
- --Nick Rupley 02:51, 12 February 2009 (UTC)
I don't understand how you came about the formula. Did you try test cases and make a general formula from them or was it more intuition. I just couldn't see the relationship. -- Ross Kersey
Well, I started out with $ \scriptstyle U(3^1)\ =\ \{1,2\} $ and $ \scriptstyle U(3^2)\ =\ \{1,2,4,5,7,8\} $, and noted that when you multiply the power of $ \scriptstyle p $ (in this case $ \scriptstyle3^n $) by another $ \scriptstyle p $, you are expanding the cardinality of the set $ \scriptstyle\{1,2,\ldots,p^n\} $ by $ \scriptstyle p $. So, the number of multiples of $ \scriptstyle p $ that appear in the expanded set is going to be $ \scriptstyle p $ times more than the original set. The set of $ \scriptstyle\{1,2,\ldots,p\} $ contains only one multiple of $ \scriptstyle p $ ($ \scriptstyle p $ itself), so it would make sense that $ \scriptstyle\{1,2,\ldots,p^2\} $ contains $ \scriptstyle p $ multiples of $ \scriptstyle p $, and so on. So to answer your question, I suppose it was a bit of intuition which came from a couple of test cases.
- --Nick Rupley 03:13, 13 February 2009 (UTC)
