There were two somewhat theoretical things on the homework for today. They are worth talking about briefly.
First, a formula for $$\phi(N)=\phi\left( \prod_{k=1}^n p_i^{e_i}\right)$$ Did you get one? Here it is! $$\phi\left( \prod_{k=1}^n p_i^{e_i}\right)=\prod_{k=1}^n \phi\left(p_i^{e_i}\right)=\prod_{k=1}^n \left[1\frac{1}{p_i}\right]p_i^{e_i}=N\cdot \prod_{k=1}^n \left[1\frac{1}{p_i}\right]$$ The moral of the story is that being relatively prime makes up for many omissions.
Click to the left again to hide and once more to show the dynamic interactive window 
The other main component was related to a new function. (Much later in the semester we will see lots of new and interesting functions!) This function was $$f(n)=\frac{\phi(n)}{n}\; .$$ Some thing are very easy to prove about this if you have the formula for $\phi(n)$. For instance, $$f\left(p^k\right)=\frac{p^k\left(11/p\right)}{p^k}=\left(11/p\right)$$ which does not depend on $k$. So in particular it's true for $k=1$, which is $f(p)$.
On the other hand, some things are a little harder to spy. Such as when $f(n)=1/2$.
Click to the left again to hide and once more to show the dynamic interactive window 
But hopefully easy to prove!
Another example of this we didn't put on the homework, but which was mentioned last time, is when $\phi(n)\mid n$. (Notice that if $\phi(n) \mid n$, then $f(n)=\frac{1}{k}$ for some integer $k$.) First, some exploration:
Click to the left again to hide and once more to show the dynamic interactive window 
As you noted last time, it seemed like all the numbers involved were multiples of six. Well, also the powers of two! But not every multiple of six worked (30 and 42 didn't), and not even every even multiple of six worked (for instance, 60).
So in this case, we again make the point that the FTA is useful for many things  maybe I should factor some of the $n$ that do work! Let's do this BY HAND right now.
Okay, now we can check it with Sage.
Click to the left again to hide and once more to show the dynamic interactive window 
Aha! It looks like anything with only powers of two works, as well as anything with a power of three as long as it also has a power of two! Nothing else seems to.
Now let's try to prove it. I will do it with a sort of cases approach. You may wish to notice how the fact that $p1=2$ precisely for $p=3$ works into this.
Remember, there are still other interesting questions to tackle. The first two I mentioned last time.
Click to the left again to hide and once more to show the dynamic interactive window 
You now have the tools you need to tackle such questions. The structure of $\phi$ is very regular!
Now, let's get back to primitive roots. Remember, there are two equivalent ways to characterize/define a primitive root of $n$ among numbers such that $gcd(a,n)=1$:
Take a second and figure out the orders of some elements of some small groups of units. One person each do $U_n$ for $n\in \{5,7,8,9,10,12,14,15\}$; I'll take $n=5$ and $n=15$, if you don't mind. Did we find any primitive roots?
It's useful to try looking for primitive roots by hand, and you'll do some of that in the homework over the weekend. It is also useful to try to prove things about orders in general, and you'll do some of that and we'll do some in class.
One approach for this is to try to find a better way of testing for primitiveness than trying all powers of $a$. As it turns out, there is a very useful lemma for doing this. First, an example to think about it by hand.
Take some number $n$ with a $\phi(n)$ with a few factors  say, $n=11$ and $\phi(11)=10$. Okay, we know that every element $a\in U_{11}$ will have $a^{10}\equiv 1\text{ mod }(11)\; ,$ but which ones don't have it before?
Well, we know that the order of an element has to divide $\phi(11)=10$, so we could try $a^{2}$ and $a^5$. If those aren't $\equiv 1$, there aren't any other possible orders out there, so it would work as a primitive root. You can try this out to discover that $$2^2\equiv 4\not\equiv 1\text{ mod }(11)\text{ and }2^5=32\equiv 1\not\equiv 1\text{ mod }(11)\;, $$ so $2$ must be a primitive root, while $$3^5=9\cdot 9\cdot 3\equiv (2)^2\cdot 3\equiv 12\equiv 1\text{ mod }(11)$$ so $3$ is not a primitive root modulo eleven.
Now we formalize this, and in fact rephrase it in a slightly more efficient way. As far as I understand the code this is how even Sage tests for finding primitive roots.
Lemma for testing primitive roots: An element $a\in U_n$ is a primitive root if and only if $a^{\phi(n)/q}\not\equiv 1$ in $U_n$ for each prime $q$ dividing $\phi(n)$.
Essentially, two things change from trying all divisors of $\phi(n)$.
This lemma is probably still a little hard to understand, but with some examples it will make sense.
Click to the left again to hide and once more to show the dynamic interactive window 
If you try various $n$ and various attempts at primitive roots $a$, you will see that this really works. Make sure you are trying $a$ that are actually coprime to $n$, though! As it turns out, there aren't very many things to try, since $\phi(n)$ in general doesn't have a lot of prime divisors, even if $n$ is a fairly large prime.
Proof:
Why not try it by hand for $n=17$? There is only one prime divisor of $\phi(17)$, which makes things easier.
This lemma makes easy some statements that would otherwise be quite hard. For instance, you should see how to prove that if $a$ is a primitive root of $n$, then so is $a^{1}$ (modulo $n$). Here's something harder:
(It turns out that nearly all numbers fit this criterion  the only exceptions are $2$, perfect powers $p^e$ of primes of the form $p=4n+3$, and products of those two things. There would be a little more work needed to do the converse.)
For next time you should also try to explore what sort of numbers have primitive roots. Look for all the colors!
Click to the left again to hide and once more to show the dynamic interactive window 
Today we'll start this investigation (and end class) by proving that most powers of 2 do not have primitive roots.
Traceback (click to the left of this block for traceback) ... ArithmeticError: There is no primitive root modulo n Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_76.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# * coding: utf8 *\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cG93ZXI9MjUKcHJpbWl0aXZlX3Jvb3QoMl5wb3dlcik="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module> File "/private/var/folders/Yy/YytEJm5VEB0+pBRD7JNLe++++TQ/Tmp/tmpMnjxTO/___code___.py", line 4, in <module> exec compile(u'primitive_root(_sage_const_2 **power) File "", line 1, in <module> File "/Users/karldietercrisman/Downloads/sage4.6.2.rc0/local/lib/python2.6/sitepackages/sage/rings/arith.py", line 3288, in primitive_root raise ArithmeticError, "There is no primitive root modulo n" ArithmeticError: There is no primitive root modulo n 
By the way, there are elements of $U_{2^n}$ that have order $2^{n2}$, just not primitive roots (which would have order $\phi(2^n)=2^{n1}$). In fact, it turns out that $\pm 5$ have this order. (This is Theorem 6.10 in the book  we won't say more about it, but it definitely relates to group theory.)
Click to the left again to hide and once more to show the dynamic interactive window 
Proof: For $n=2$ and $n=4$, there are primitive roots. So assume $n=2^k$ for $k>2$.
Homework for next time:
