primitive root of residue modulo p

Question

I was trying to prove that for the set $\{1,2,....,p-1\}$ modulo p there are exactly $\phi(p-1)$ generators.Here p is prime.Also the operation is multiplication.

My Try:

So I first assumed that if there exists a generator, then from the set $\{a^1,a^2,...,a^{p-1}\}$ all those powers which are co prime to $p-1$ are also generators.But i am having difficulty in proving the existence of such an $a$. If anyone can help it would be great . Thanks.It would be better if it avoids fundamental theorem of algebra.

Answer 1

Here's the proof that I was given in my course.

It uses the fact that $\displaystyle \sum_{d \mid n} \phi(d) = n$, which can be proved using elementary principles, but is slightly tricky.

We show that if there is an element of order $d$, then there are exactly $\phi(d)$ elements of order $d$.

Let $a$ be an element of order $d$. The argument you provided in your post can be adapted to exhibit $\phi(d)$ elements of order $d$ - elements in the list $1,a,a^2,\ldots,a^{d-1}$ with index coprime to $d$. We need to establish that there can be no others.

Multiplication modulo $p$ is an integral domain, so by Lagrange's theorem any polynomial of degree $k$ can have at most $k$ solutions. Any element of degree $d$ is a solution of the polynomial $x^d=1 \mod p$, and there are at most $d$ solutions. But all of the elements in the above list are solutions, so we have found all possible solutions.

We conclude that there are exactly $\phi(d)$ elements of order $d$.

Now write $S_d$ for the set of elements of order $d$. We have shown that when $d$ divides $p-1$, either $|S_d|=0$, or $|S_d|=\phi(d)$. Clearly, $\displaystyle \sum_{d \mid p-1} |S_d| = p-1$, as the $S_d$ partition $\{1,2,\ldots,p-1\}$. But we also have that $\displaystyle \sum_{d \mid p-1} \phi(d) = p-1$.

Thus, if any of the $S_d$ happened to be empty for $d \mid p-1$, we wouldn't have enough elements in total. We deduce that $|S_d|=\phi(d)$ for each $d$ dividing $p-1$, and so in particular $|S_{p-1}|$ is not empty, so there exists a generator (or more precisely, exactly $\phi(p-1)$ generators).

Answer 2

Assuming $p$ is prime then $\mathbb{Z}/p\mathbb{Z}$ is the finite field $\mathbb{F}_p$ and the set you are interested in is the multiplicative group $\mathbb{F}_p^*$. In this context what you are looking for is a proof that the multiplicative group is cyclic. And with this formulation you can find a lot of answers, for example this collection of proofs: https://mathoverflow.net/questions/54735/collecting-proofs-that-finite-multiplicative-subgroups-of-fields-are-cyclic