Our first item for today is just the coolest result. I hope you conjectured it, but it could be quite challenging to do so. Yet once you see it, it seems obvious to at least try it!
Proposition: If $m\mid n$, then $\phi(m)\mid \phi(n)$.
Click to the left again to hide and once more to show the dynamic interactive window 
This quick and clever proof is in fact from the text.
Proof: Since $m\mid n$, we can write $n/m$ as as product of the prime factors of $n$ which are not in $m$. Then since all prime divisors of $m$ are prime divisors of $n$ as well, $$\phi(n)/\phi(m)=(n/m)\left(\prod_{p\mid n} (11/p) / \prod_{p\mid m} (11/p) \right)=(n/m)\prod_{p\mid (n/m)}(11/p)=(n/m)\prod_{p\mid (n/m)}\frac{p1}{p}\, .$$ This is not selfevidently an integer, of course! But note that $n/m$ is an integer, and every $p$ in the denominator is a (different) factor of $n/m$, so in fact we can cancel all the denominators and this is an integer! Thus $\phi(n)$ is an integer multiple of $\phi(m)$.
Two of the other homework problems are actually quite important lemmas for being able to do more work with primitive roots. I want you to keep trying to prove these. However, we will also use them today.
In the first one, if the order is $p1$, then if $a$ is a primitive root modulo $p$, then so is $a^b$ for all $b$ coprime to $p1$  which implies that if there is a primitive root modulo $p$, then there are in fact $\phi(p1)$ of them! (This turns out to be true for general $n$, replacing $p1$ by $\phi(n)$, in fact.) It works; let's check this out.
Click to the left again to hide and once more to show the dynamic interactive window 
Today's biggest proof is that every prime number $p$ has a primitive root, and it uses both of the above as lemmas. In order to understand that proof, let's see in what sense these lemmas fail (or don't).
Let's pick a nonprime number we know something about. Last time we saw that powers of 2 don't have cyclic groups of units, but they do have lots of elements with the next smallest possible order. So for $n=32$, we can look at whether powers $b$ coprime to that order of such an element are in fact also elements with the same order.
5^{1}\equiv 5 has order 8 (and gcd(1,8)=1) 5^{3}\equiv 29 has order 8 (and gcd(3,8)=1) 5^{5}\equiv 21 has order 8 (and gcd(5,8)=1) 5^{7}\equiv 13 has order 8 (and gcd(7,8)=1) 5^{1}\equiv 5 has order 8 (and gcd(1,8)=1) 5^{3}\equiv 29 has order 8 (and gcd(3,8)=1) 5^{5}\equiv 21 has order 8 (and gcd(5,8)=1) 5^{7}\equiv 13 has order 8 (and gcd(7,8)=1) 
So it works; indeed, the first lemma should be true whether $p$ is prime or not, though I won't ask you to prove it. The second lemma also seems to be working; there are exactly $\phi(8)=4$ powers here, which have order eight.
The problem, though, is that there might be some element of the same order as the ones above which is not actually one of them!
27^{1}\equiv 27 has order 8 (and gcd(1,8)=1) 27^{3}\equiv 3 has order 8 (and gcd(3,8)=1) 27^{5}\equiv 11 has order 8 (and gcd(5,8)=1) 27^{7}\equiv 19 has order 8 (and gcd(7,8)=1) 27^{1}\equiv 27 has order 8 (and gcd(1,8)=1) 27^{3}\equiv 3 has order 8 (and gcd(3,8)=1) 27^{5}\equiv 11 has order 8 (and gcd(5,8)=1) 27^{7}\equiv 19 has order 8 (and gcd(7,8)=1) 
In some sense, then, there are "extra" elements with order $8$ in the above example. If you have eight elements of order eight, and obviously at least one element of order 1, in $U_{32}$, then it is impossible to have the required eight elements of order sixteen one would need for there to be a primitive root modulo $32$ (because $8+1+8>16=U_{32}$). In essence, the fact that this can't happen for a prime modulus is why primitive roots do exist in that case.
A primitive root of 2 is 1 A primitive root of 3 is 2 A primitive root of 5 is 2 A primitive root of 7 is 3 A primitive root of 11 is 2 A primitive root of 13 is 2 A primitive root of 17 is 3 A primitive root of 19 is 2 A primitive root of 23 is 5 A primitive root of 29 is 2 A primitive root of 31 is 3 A primitive root of 37 is 2 A primitive root of 41 is 6 A primitive root of 43 is 3 A primitive root of 47 is 5 A primitive root of 53 is 2 A primitive root of 59 is 2 A primitive root of 61 is 2 A primitive root of 67 is 2 A primitive root of 71 is 7 A primitive root of 73 is 5 A primitive root of 79 is 3 A primitive root of 83 is 2 A primitive root of 89 is 3 A primitive root of 97 is 5 A primitive root of 2 is 1 A primitive root of 3 is 2 A primitive root of 5 is 2 A primitive root of 7 is 3 A primitive root of 11 is 2 A primitive root of 13 is 2 A primitive root of 17 is 3 A primitive root of 19 is 2 A primitive root of 23 is 5 A primitive root of 29 is 2 A primitive root of 31 is 3 A primitive root of 37 is 2 A primitive root of 41 is 6 A primitive root of 43 is 3 A primitive root of 47 is 5 A primitive root of 53 is 2 A primitive root of 59 is 2 A primitive root of 61 is 2 A primitive root of 67 is 2 A primitive root of 71 is 7 A primitive root of 73 is 5 A primitive root of 79 is 3 A primitive root of 83 is 2 A primitive root of 89 is 3 A primitive root of 97 is 5 
The previous cell shows us that we get a primitive root for the first 25 primes. Now let's use our lemmas to prove that every prime has a primitive root  or, in other words, that the order $p1$ group $U_p$ is always cyclic.
The key is to try to write $\phi(p)=p1$ in two different ways:
The first one we have already proved, of course. The second makes sense too, though; after all, we already proved (the other Lagrange's Theorem) that the order of any element of a group divides the order of the group, so the only possible orders of elements in $U_p$ are positive divisors of $p1$. We know that every element of $U_p$ has some order, so that $p1$ is divided up into (disjoint) sets of different orders as above.
Let's see what that looks like for two examples  one where we know we have a primitive root, and one where we know we don't.
Here is the list of sets of different order elements for $n=41$:
There are 1=\phi(1) elements of order 1  [1] There are 1=\phi(2) elements of order 2  [40] There are 2=\phi(4) elements of order 4  [9, 32] There are 4=\phi(5) elements of order 5  [10, 16, 18, 37] There are 4=\phi(8) elements of order 8  [3, 14, 27, 38] There are 4=\phi(10) elements of order 10  [4, 23, 25, 31] There are 8=\phi(20) elements of order 20  [2, 5, 8, 20, 21, 33, 36, 39] There are 16=\phi(40) elements of order 40  [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35] There are 1=\phi(1) elements of order 1  [1] There are 1=\phi(2) elements of order 2  [40] There are 2=\phi(4) elements of order 4  [9, 32] There are 4=\phi(5) elements of order 5  [10, 16, 18, 37] There are 4=\phi(8) elements of order 8  [3, 14, 27, 38] There are 4=\phi(10) elements of order 10  [4, 23, 25, 31] There are 8=\phi(20) elements of order 20  [2, 5, 8, 20, 21, 33, 36, 39] There are 16=\phi(40) elements of order 40  [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35] 
But here is the list of sets for $n=32$; there aren't any for the highest possible order, and all the other sets have orders exact multiples of $\phi(d)$.
There are 1=\phi(1) elements of order 1  [1] There are 3\neq\phi(2) elements of order 2  [15, 17, 31] There are 4\neq\phi(4) elements of order 4  [7, 9, 23, 25] There are 8\neq\phi(8) elements of order 8  [3, 5, 11, 13, 19, 21, 27, 29] There are 0\neq\phi(16) elements of order 16  [] There are 1=\phi(1) elements of order 1  [1] There are 3\neq\phi(2) elements of order 2  [15, 17, 31] There are 4\neq\phi(4) elements of order 4  [7, 9, 23, 25] There are 8\neq\phi(8) elements of order 8  [3, 5, 11, 13, 19, 21, 27, 29] There are 0\neq\phi(16) elements of order 16  [] 
So what is going on here? Let's go back to our assumption that $p$ is prime. Well, for any of the divisors $d$ of $p1$ (not just $p1$ itself), the size of the set $$\{a\in U_p \mid a\text{ has order }d\}$$ certainly can't be bigger than $\phi(d)$, by our second lemma. That should be clear. On the other hand, as we just pointed out, every element of $U_p$ has some order! And once we find one $a$ with order $d$, then all the powers of $a$ coprime to $d$ also have that order, so there are $\phi(d)$ of them  and no more than $\phi(d)$ of them  once we find such an $a$.
This means that if any of the sets for $d$ (such as the set of primitive roots! for $d=p1$) is empty, then the orders of $\phi(d)$ elements of our group of units have to be distributed among the other sets. But we know that none of the sets is bigger than $\phi(d)$, and $$\sum_{d\mid p1, d<p1} \phi(d)<p1\; ;$$ yet all $p1$ elements must be in one of the sets. This doesn't make sense unless there is at least one element in each of the sets of elements with order $d$, so in particular there is at least one (and in fact $\phi(p1)$) with order $p1$, as we suspected all along!
If you are curious, you can explore more below.
Click to the left again to hide and once more to show the dynamic interactive window 
There is more to the story, but we won't cover the rest in detail. The complete story of which $n$ have groups of units $U_n$ that are cyclic is given by Sage here:
File: /Applications/MathApps/sage/devel/sage/sage/libs/pari/gen.pyx Type: <type ‘builtin_function_or_method’> Definition: a.znprimroot() Docstring:
File: /Applications/MathApps/sage/devel/sage/sage/libs/pari/gen.pyx Type: <type ‘builtin_function_or_method’> Definition: a.znprimroot() Docstring:

(Chapter 6.7 tells the complete algebraic story of how to interpret this, culminating in Corollary 6.14, which is way more algebra than we will do in this course but which is satisfyingly complete.)
To make this result plausible, the following cell demonstrates yet another of the exercises from last time  that an odd primitive root for a prime power is also a primitive root for twice that modulus.
Click to the left again to hide and once more to show the dynamic interactive window 
Obviously this is consistent, since $\phi(2p^e)=\phi(p^e)$. Does this pattern help you think how you might prove it?
We will soon begin talking about cryptography and related matters. Before we do so, we will preview our computational needs by using primitive roots to solve some congruences in a cool way.
Suppose you want to solve a more mysterious congruence than the basic ones we have tackled thus far. Here are two examples:
You can think of the first one as finding a higher root modulo $n$, and the second one as finding a logarithm modulo $n$. Indeed, solving the second problem is an example of what is called a discrete log problem. Such problems are apparently very, very hard to solve quickly, but (!) no one has every actually proved this.
Here's one way to solve the first one. First we find a primitive root modulo $19$. Obviously we could just ask Sage, or use the criterion from last time with trial and error; in the not too distant past (such as my own undergraduate days), the back of every number theory text had a table of primitive roots!
2 2 
Now what we will do is try to represent both sides of $$x^4\equiv 13\text{ mod }(19)$$ as powers of that primitive root!
The easy part is representing $x^4$; we just say that $x\equiv 2^i$ for some (as yet unknown) $i$, so $$x^4\equiv \left(2^i\right)^4\equiv 2^{4i}\; .$$ The harder part is figuring out what power of $2$ gives $13$. Again, there is no shortcut, though books in the past would have huge tables of these things.
2^{2}\equiv 4\not\equiv 13 2^{3}\equiv 8\not\equiv 13 2^{4}\equiv 16\not\equiv 13 2^{5}\equiv 13  hooray! 2^{2}\equiv 4\not\equiv 13 2^{3}\equiv 8\not\equiv 13 2^{4}\equiv 16\not\equiv 13 2^{5}\equiv 13  hooray! 
So we can say that $$x^4\equiv 13\text{ mod }(19)$$ becomes $$2^{4i}\equiv 2^{5}\text{ mod }(19)\; .$$ Now we can use some insight from precalculus. You would solve it this way, with equations (not congruences): $$2^{4i}=2^{5}\Rightarrow 4i=5 \Rightarrow i=5/4\; .$$ We will try to do the same thing here.
What is very important is that this is really no longer a congruence in $\mathbb{Z}_{19}$; after all, everything in sight is really in $U_{19}$, a cyclic group of order $\phi(19)=18$. But a cyclic group of order $18$ would just be modulo 18! So we take the exponents, but mod (18): $$4i\equiv 5\text{ mod }(18)\; .$$
Sadly, this does not have a solution. But we figured it out without taking every fourth power out there! Indeed, doing that confirms our result:
[16, 5, 9, 17, 4, 7, 11, 6, 6, 11, 7, 4, 17, 9, 5, 16, 1] [16, 5, 9, 17, 4, 7, 11, 6, 6, 11, 7, 4, 17, 9, 5, 16, 1] 
Let's try the same thing modulo $17$ instead  that is, can we solve $$x^4\equiv 13\text{ mod }(17)\; ?$$ Here, a primitive root is $3$, and it turns out that $3^4\equiv 13$, so we can try. This gives $$3^{4i}\equiv 3^4\text{ mod }(17)\Rightarrow 4i\equiv 4\text{ mod }(16)\, ,$$ which definitely does have solutions  in fact, four solutions ($1,5,9,13$) to the reduced congruence $$i\equiv 1\text{ mod }(4)$$ so there are four solutions ($3^1,3^5,3^9,3^{13}$) to the original congruence. Let's check this:
[13, 13, 13, 13] [13, 13, 13, 13] 
You can even see it at work for more complicated things. If we try solving $x^6\equiv 8$ mod (49), we'll need a primitive root of 49; 3 works. I can find out what power of 3 is 8:
3^{2}\equiv 9\not\equiv 8 3^{3}\equiv 27\not\equiv 8 3^{4}\equiv 32\not\equiv 8 3^{5}\equiv 47\not\equiv 8 3^{6}\equiv 43\not\equiv 8 3^{7}\equiv 31\not\equiv 8 3^{8}\equiv 44\not\equiv 8 3^{9}\equiv 34\not\equiv 8 3^{10}\equiv 4\not\equiv 8 3^{11}\equiv 12\not\equiv 8 3^{12}\equiv 36\not\equiv 8 3^{13}\equiv 10\not\equiv 8 3^{14}\equiv 30\not\equiv 8 3^{15}\equiv 41\not\equiv 8 3^{16}\equiv 25\not\equiv 8 3^{17}\equiv 26\not\equiv 8 3^{18}\equiv 29\not\equiv 8 3^{19}\equiv 38\not\equiv 8 3^{20}\equiv 16\not\equiv 8 3^{21}\equiv 48\not\equiv 8 3^{22}\equiv 46\not\equiv 8 3^{23}\equiv 40\not\equiv 8 3^{24}\equiv 22\not\equiv 8 3^{25}\equiv 17\not\equiv 8 3^{26}\equiv 2\not\equiv 8 3^{27}\equiv 6\not\equiv 8 3^{28}\equiv 18\not\equiv 8 3^{29}\equiv 5\not\equiv 8 3^{30}\equiv 15\not\equiv 8 3^{31}\equiv 45\not\equiv 8 3^{32}\equiv 37\not\equiv 8 3^{33}\equiv 13\not\equiv 8 3^{34}\equiv 39\not\equiv 8 3^{35}\equiv 19\not\equiv 8 3^{36}\equiv 8  hooray! 3^{2}\equiv 9\not\equiv 8 3^{3}\equiv 27\not\equiv 8 3^{4}\equiv 32\not\equiv 8 3^{5}\equiv 47\not\equiv 8 3^{6}\equiv 43\not\equiv 8 3^{7}\equiv 31\not\equiv 8 3^{8}\equiv 44\not\equiv 8 3^{9}\equiv 34\not\equiv 8 3^{10}\equiv 4\not\equiv 8 3^{11}\equiv 12\not\equiv 8 3^{12}\equiv 36\not\equiv 8 3^{13}\equiv 10\not\equiv 8 3^{14}\equiv 30\not\equiv 8 3^{15}\equiv 41\not\equiv 8 3^{16}\equiv 25\not\equiv 8 3^{17}\equiv 26\not\equiv 8 3^{18}\equiv 29\not\equiv 8 3^{19}\equiv 38\not\equiv 8 3^{20}\equiv 16\not\equiv 8 3^{21}\equiv 48\not\equiv 8 3^{22}\equiv 46\not\equiv 8 3^{23}\equiv 40\not\equiv 8 3^{24}\equiv 22\not\equiv 8 3^{25}\equiv 17\not\equiv 8 3^{26}\equiv 2\not\equiv 8 3^{27}\equiv 6\not\equiv 8 3^{28}\equiv 18\not\equiv 8 3^{29}\equiv 5\not\equiv 8 3^{30}\equiv 15\not\equiv 8 3^{31}\equiv 45\not\equiv 8 3^{32}\equiv 37\not\equiv 8 3^{33}\equiv 13\not\equiv 8 3^{34}\equiv 39\not\equiv 8 3^{35}\equiv 19\not\equiv 8 3^{36}\equiv 8  hooray! 
So we write $x=3^i$ for some as yet unknown $i$, and get $$3^{6i}\equiv 3^{36}\text{ mod }(49)\; ,$$ which gives us $$6i\equiv 36\text{ mod }(\phi(49)=42)$$ and this reduces to $$i\equiv 6\text{ mod }(7)\; .$$ So $i=6,13,20,27,34,41$ all work, which means (from our little info above) that $x=3^{i}\equiv 43,10,16,6,39,33$ all should work.
[8, 8, 8, 8, 8, 8] [8, 8, 8, 8, 8, 8] 
Similarly, we can try to solve logarithmic guys like $$7^x\equiv 6\text{ mod }(17)\; .$$ A primitive root modulo 17 is 3, and we can check that $7\equiv 3^{11}\text{ mod }(17)$ and $5\equiv 3^{15}\text{ mod }(17)$. Then, replacing these, we see that $$3^{11x}\equiv 3^{15}\text{ mod }(17)\text{ yields }11x\equiv 15\text{ mod }(16)\, ;$$ since $3\cdot 11=33=32+1$, we see that 3 and 11 are inverses modulo 16, so $x\equiv 3\cdot 15\equiv 45\equiv 13$ mod (16). And indeed:
True True 
Homework:
