Reaping what we've shown

In fact, the number of elements of each order can be obtained simply from the knowledge of the existence of a primitive root. For let $a$ be a primitive root; we will calculate the order of $a^k$ for any integer $k$. To do this, just note that $o(a^k)$ is the smallest number $o$ such that $a^{ko} = 1$. But $a^{ko} = 1$ iff $p-1\ \vert\ ko$; letting $d = (p-1,k)$, this is equivalent to $(p-1)/d\ \vert\ ok/d$. Since $(p-1)/d$ and $k/d$ are relatively prime, the smallest value of $o$ is $(p-1)/d$. Thus, we have shown that the order of $a^k$ is $(p-1)/(p-1,k)$ for each $k$. In particular, the various primitive roots are the numbers $a^k$, where $k$ is relatively prime to $p-1$.

Another consideration is $k$th powers. Since the nonzero elements of ${\mathbb{F}}_p$ are $a, a^2, a^3, \ldots, a^{p-1}$, the $k$th powers are $a^k, a^{2k}, a^{3k}, \ldots, a^{(p-1)k}$. But these may not all be different. How many distinct $k$th powers do we have? Well, $a^{ik} = a^{jk}$ iff $p-1 \ \vert\ (j-i)k$. Letting $d = (p-1,k)$, this is the same as having $(p-1)/d\ \vert\ (j-i)k/d$; equivalently (by coprimality), $(p-1)/d \ \vert\ j-i$. Since $i, j$ range from $1$ to $p-1$, it is evident that, for any fixed $i$, there are exactly $d$ possible values of $j$ satisfying $a^{ik} = a^{jk}$. Thus, in our list $a^k, a^{2k}, a^{3k}, \ldots, a^{(p-1)k}$, each number occurs $d = (p-1,k)$ times. Dividing out, we then see that there are exactly $(p-1)/d$ nonzero $d$th powers in ${\mathbb{F}}_p$ (other than zero, which we still disdain). Moreover, each such $d$th power has exactly $d$ $d$th roots.

Lest this get too abstract, let's take an example: ${\mathbb{F}}_{11} = \{0,1,2,3,\ldots,10\}$. With some experimentation, we can find that $2$ is a primitive root modulo $11$; its successive powers are

$$2, 4, 8, 5, 10, 9, 7, 3, 6, 1.$$

The even-numbered terms are then the squares, and, as we would expect, there are five of them:

$$4 = 2^2 = 9^2;\ \ 5 = 4^2 = 7^2;\ \ 9 = 8^2 = 3^2;\ \ 3 = 5^2 = 6^2;\ \ 1 = 10^2 = 1^2.$$

What about fourth powers? We would expect there to be $10/(10,4) = 5$ of them too, and sure enough, every square is a fourth power:

$$4 = 8^4 = 3^4;\ \ 5 = 2^4 = 9^4;\ \ 9 = 5^4 = 6^4;\ \ 3 = 4^4 = 7^4;\ \ 1 = 10^4 = 1^4.$$

And how about fifth powers? The above predicts two fifth powers, each with five fifth roots. Let's check:

$$10 = 2^5 = 8^5 = 10^5 = 7^5 = 6^5;\ \ 1 = 4^5 = 5^5 = 9^5 = 3^5 = 1^5.$$

For one more example, let's consider the cubes. We expect to find $10/(10,3) = 10$ of them. And, in accordance with prognostications,

$$2 = 7^3;\ \ 4 = 5^3;\ \ 8 = 2^3;\ \ 5 = 3^3;\ \ 10 = 10^3;\ \ 9 = 4^3;\ \ 7 = 6^3;\ \ 3 = 9^3;\ \ 6 = 8^3;\ \ 1 = 1^3.$$

In group-theoretic terms (which may make all these considerations clearer), we've shown that the group of nonzero elements of ${\mathbb{F}}_p$ under multiplication is isomorphic to the group of integers modulo $p-1$ under addition. Taking $k$th powers in ${\mathbb{F}}_p$ corresponds to multiplying by $k$ in the additive formulation.

Let's look at some other exciting implications. For example, there's the ever-famous

Theorem. (Wilson's Theorem) If $p$ is an odd prime, $(p-1)! \equiv -1 \pmod{p}$.

Proof. Let $a$ be a primitive root. Then, $1, 2, \ldots, p-1 \in {\mathbb{F}}_p$ are equal, in some order, to $a, a^2, \ldots, a^{p-1}$. So, $(p-1)!$ is congruent to $a\cdot a^2 \cdots a^{p-1} = a^{p(p-1)/2}$. Now, $a^{p(p-1)} = 1$, but $a^{p(p-1)/2} \neq 1$ since $p(p-1)/2$ is not divisible by $p-1$ (what with $p$ being odd). However, the equation $x^2 - 1 = 0$ can only have two solutions in ${\mathbb{F}}_p$, so these must be $1$ and $-1$. We conclude $a^{p(p-1)/2} = -1$, proving Wilson's theorem. depth-1pt height7pt width6pt

That was a little cheesy since Wilson's theorem can be proven in a better way. In fact, consider the polynomial $x^{p-1}-1$. It has $p-1$ roots in ${\mathbb{F}}_p$, namely $1,2,\ldots,p-1$. By our earlier observations concerning the factorization of polynomials, we can completely factor $x^{p-1}-1 = (x-1)(x-2)(x-3)\cdots(x-p+1)$. Now Wilson's theorem -- along with, indeed, the values of all the elementary symmetric polynomials in the elements of ${\mathbb{F}}_p$ -- falls out by comparing coefficients. More generally, we can use this technique to compute the elementary symmetric polynomials in the $d$th roots of $1$, for each $d\ \vert\ p-1$.

This next result should look familiar.

Fact. Let $p$ be an odd prime. A nonzero element $b \in {\mathbb{F}}_p$ is a square iff $b^{(p-1)/2} = 1$.

Proof. Let $b = a^k$ with $a$ a primitive root. Then $b$ is a square iff $k$ is even (this doesn't depend on the choice of $k$, since the possible values of $k$ for a given $a$ all differ from each other by multiples of the even number $p-1$). But $k$ is even $\Leftrightarrow p-1\ \vert\ k(p-1)/2 \Leftrightarrow a^{k(p-1)/2} = 1$. Since $a^{k(p-1)/2} = b^{(p-1)/2}$, we are done. depth-1pt height7pt width6pt

More generally, if $d\ \vert\ p-1$, the same argument shows that $b$ is a $d$th power iff $b^{(p-1)/d} = 1$.

Fact. Let $p$ be an odd prime. Then $-1$ is a square modulo $p$ iff $p \equiv 1\pmod{4}$.

Proof. Use the above and the fact that $(-1)^{(p-1)/2} = 1$ if $p \equiv 1\pmod{4}$, $-1$ if $p \equiv 3$. depth-1pt height7pt width6pt

Another application of the theory we've developed is to the solution of Diophantine equations (over the integers, not ${\mathbb{F}}_p$!). The following illustrates the general technique.

Problem. (IMO proposal, 1985) For $k \geq 2$, let $n_1, n_2, \ldots, n_k$ be positive integers such that

$$n_2\ \vert\ 2^{n_1}-1;\ \ n_3\ \vert\ 2^{n_2}-1;\ \ \ldots;\ \ n_k\ \vert\ 2^{n_{k-1}}-1;\ \ n_1\ \vert\ 2^{n_k}-1.$$

Prove that $n_1 = n_2 = \cdots = n_k = 1$.

Solution. First note that if $n_i = 1$ for any $i$, then $n_{i+1}$ (or $n_1$ if $i = k$) must divide $2^1 - 1 = 1$, so $n_{i+1} = 1$ also. Proceeding by induction shows that all the $n_i$ are $1$ in this case. Thus, we see that either none of the $n_i$ are equal to $1$ or all of them are. We will assume the former and obtain a contradiction.

Let $p_i$ be the smallest prime factor of $n_i$, for each $i$. By cyclic rotation, we may assume $p_2 = \min\{p_i\}$. In particular, $p_2 \leq p_1$. Furthermore, $p_2 \neq 2$, since $p_2 \ \vert\ n_2 \ \vert\ 2^{n_1} - 1$, which is odd. Now, if $o$ is the order of $2$ modulo $p_2$, we have $o\ \vert\ p_2-1$, so in particular $o \leq p_2-1$. But also $o\ \vert\ n_1$, since $p_2 \ \vert\ 2^{n_1}-1$. However, all the prime factors of $n_1$ are greater than $p_1 - 1 \geq p_2 - 1$; consequently, we are forced to have $o = 1$. This means that $p_2\ \vert\ 2^1 - 1 = 1$, an impossibility. This is the desired contradiction. depth-1pt height7pt width6pt

See the exercises for more examples of this sort.