# How to show the existence of a primitive root modulo $p$?

Let $p$ be a prime. We say an integer $w$ is a primitive root modulo $p$ if $w$ has order $p-1$ modulo $p$.

Question: Use the Mobius inversion formula to show that there exists a primitive root modulo $p$.

What I have so far:

We have $$f(n)=\sum_{d|n}\mu (d) \hat{f}(n/d)$$ and I am given a clue that $\hat{\phi}(n)=n$ where $\phi$ is the Euler-Totient Function.

I'm not sure how to proceed, I suspect it lies in a clever choice of $f$ but I can't think of how Mobius could possibly imply the existence of some $w$ with order $p-1$.

Any hints?

• no idea, are you sure you don't need to use the fact that $\mathbb Z_p$ is a field? – Jorge Fernández Hidalgo Dec 14 '16 at 1:00

This question can be solved using the Inclusion-Exclusion Principle. I also assume that you know that the non-zero residues mod $p$ form a multiplicative group, call it $G$. So $|G|=p-1$.

We see that it is quite difficult to see how many elements there are of order $d$. However, it is fairly easy to see how many elements there are of order at most $d$. The element $x\in G$ has order at most $d$ iff in $G$ it satisfies: $$x^{d}=1$$ Let $S_{d}$ be the set of distinct solutions in $G$ to the above equation. By taking the elements of $G$ modulo $d$, it can be shown that $|S_{d}|=|G|/d = (p-1)/d$ (exercise). By Fermat-Lagrange, we know that every element of $G$ satisfies the above equation when $d=p-1$. So $S_{p-1}=G$.

For convenience, let $p_{1},...,p_{k}$ be the $k$ distinct prime factors of $p-1$.

We wish to find $S$, the number of elements of $S_{p-1}$ which do not lie in $S_{d}$ for any $d<p-1$. We will do this using Inclusion-Exclusion. Let $A_{i}=S_{{p-1}/{p_{i}}}$.

By Inclusion-Exclusion, we can write: $$S=|S_{p-1}|-\sum_{1\leq i \leq k} |A_{i}|+\sum_{1\leq i < j \leq k} |A_{i}\cap A_{j}|-\cdots+(-1)^{k}|A_{1}\cap \cdots \cap A_{k}|$$ In other words, we start with all elements, remove all those with order at most $(p-1)/p_{i}$, add back in (because they have been removed twice) all those elements of order at most $(p-1)/(p_{i}p_{j})$, etc.

Now observe that whether we subtract or add is governed by the number of indices. So the sums which are added have even numbers of indices, those subtracted have an odd number of indices. Hence, by definition of the Mobius function, we have:$$S=\sum_{d|(p-1)}\mu (d) |S_{(p-1)/d}|=\sum_{d|(p-1)}\mu (d) \left(\frac{p-1}{d}\right)$$

Here I have used the fact that: $$A_{i_{1}}\cap \cdots \cap A_{i_{m}}=S_{(p-1)/(p_{i_{1}}\cdots p_{i_{m}})}$$ which is left as an exercise.

Finally, notice that this expression for $S$ can be simplified by applying the Mobius Inversion Formula to the Euler Totient Function (as you suggest). Thus, $$S=\sum_{d|(p-1)}\mu (d) \left(\frac{p-1}{d}\right)=\phi (p-1)$$ So we have shown that the number of primitive roots modulo $p$ is in fact equal to $\phi(p-1)$, which is positive.