# Thread: Primitive roots mod p

1. ## Primitive roots mod p

Here's a fun challenge problem!

Show that the product of all primitive roots modulo $\displaystyle p$ is congruent to $\displaystyle (-1)^{\phi(p-1)}$ modulo $\displaystyle p$.

Show that the sum of all primitive roots modulo $\displaystyle p$ is congruent to $\displaystyle \mu(p-1)$ modulo $\displaystyle p$.

2. Here is a hint. If $\displaystyle a$ is a primitive root, then all primitive roots of mod $\displaystyle p$ are $\displaystyle a^k$ where $\displaystyle 1\leq k\leq n$ and $\displaystyle (k,n)=1$.

Originally Posted by chiph588@
Show that the product of all primitive roots modulo $\displaystyle p$ is congruent to $\displaystyle (-1)^{\phi(p-1)}$ modulo $\displaystyle p$.
So we approach this by the hint, let $\displaystyle a$ be a primitive root. Then the product of all primitive roots mod $\displaystyle p$ is $\displaystyle \prod_{1\leq k \leq n}^{(k,n)=1} a^k$. Now for every primitive root $\displaystyle a^k$ we see that $\displaystyle a^{p-k}$ is a primitive root also. Therefore, we can pair the primitive roots with their inverses. We just need to be careful, we need to know that $\displaystyle a^k$ is not paired with itself. But $\displaystyle a^k \not \equiv a^{p-k}(\bmod p)$ if $\displaystyle p>2$. Thus, if $\displaystyle p>2$ we get $\displaystyle 1$ and if $\displaystyle p=2$ then we get $\displaystyle -1$. And so it is correct to write $\displaystyle (-1)^{\phi(p-1)}$ because $\displaystyle \phi(m)$ is even for $\displaystyle m\geq 3$.

Show that the sum of all primitive roots modulo $\displaystyle p$ is congruent to $\displaystyle \mu(p-1)$ modulo $\displaystyle p$.
This one should be approached like the one above. But this one is tricker. Let us focus on an easier case first, say $\displaystyle p\equiv 1(\bmod 4)$. Now $\displaystyle a$ is a primitive then $\displaystyle p-a$ is a primitive root too (prove this). And so the entire sum can be paired to cancel out mod $\displaystyle p$. And so we are left with zero. Notice that if $\displaystyle p\equiv 1(\bmod 4)$ then $\displaystyle 4$ divides $\displaystyle p-1$ and so $\displaystyle \mu(p-1)=0$. Now you need to consider other cases.

3. Another approach for the second question. (this also works for the first one)

First a little Theorem that always comes in handy.

Theorem
: Let $\displaystyle F\left( n \right) = \sum\limits_{\left( {k,n} \right) = 1;{\text{ }}1 \leqslant k \leqslant n} {f\left( {\tfrac{k} {n}} \right)}$ then $\displaystyle \sum\limits_{\left. d \right|n} {F\left( d \right)} = \sum\limits_{k = 1}^{n} {f\left( {\tfrac{k} {n}} \right)}$ with $\displaystyle n \in \mathbb{Z}^+$

Proof.

We will show first that all of the terms of the RHS are appear once and only once on the LHS.

So, consider: $\displaystyle f\left( {\tfrac{k} {n}} \right)$ with $\displaystyle 1 \leqslant k \leqslant n$ then $\displaystyle \tfrac{k} {n} = \frac{{\tfrac{k} {{\left( {k,n} \right)}}}} {{\tfrac{n} {{\left( {k,n} \right)}}}} = \tfrac{{k'}} {{n'}}$ where $\displaystyle k' = \tfrac{k} {{\left( {k,n} \right)}} \wedge n' = \tfrac{n} {{\left( {k,n} \right)}}$ note also that this implies: $\displaystyle \left( {k',n'} \right) = 1 \wedge \left. {n'} \right|n$, hence it corresponds to one of the terms (and only one) in $\displaystyle F\left( {n'} \right)$ (we are considering each of the terms as if they were different elements)

Conversly, it's easy to see that each of the terms on the LHS of our identity appears once only on the RHS. $\displaystyle \square$

_______________________________________

Now let's go to our problem, let $\displaystyle g$ be a primitive root module $\displaystyle p$, then our sum is congruent to $\displaystyle S =\sum\limits_{\left( {k,p - 1} \right) = 1;{\text{ }}1 \leqslant k \leqslant p-1} {g^k }$ module $\displaystyle p$ (since the exponents must be coprime with $\displaystyle \phi \left( p \right) = p - 1$ for them to be primitive roots, and that is sufficient). So consider in general: $\displaystyle S_n = \sum\limits_{\left( {k,n} \right) = 1;{\text{ }}1 \leqslant k \leqslant n} {a^{\tfrac{k} {n}} }$ then we'll set $\displaystyle n = p - 1 \wedge a = g^{p - 1}$

We have: $\displaystyle \sum\limits_{\left. d \right|n} {S_d } = \sum\limits_{k = 1}^n {a^{\tfrac{k} {n}} } = \tfrac{{a^{\tfrac{1}{n}} - a^{\tfrac{{n + 1}} {n}} }} {{1 - a^{\tfrac{1} {n}} }}$ hence by Möbius inversion formula: $\displaystyle S_n = \sum\limits_{\left. d \right|n} {\tfrac{{a^{\tfrac{1}{d}} - a^{1 + \tfrac{1} {d}} }} {{1 - a^{\tfrac{1} {d}} }} \cdot \mu \left( {\tfrac{n} {d}} \right)}$

Thus: $\displaystyle S = \sum\limits_{\left. d \right|\left( {p - 1} \right)} {\left( {\tfrac{{g^{\tfrac{{p - 1}} {d}} - g^{\left( {\tfrac{{p - 1}} {d}} \right) \cdot \left( {d + 1} \right)} }} {{1 - g^{\tfrac{{p - 1}} {d}} }}} \right) \cdot \mu \left( {\tfrac{{p - 1}} {d}} \right)}$$\displaystyle = \sum\limits_{\left. d \right|\left( {p - 1} \right)} {g^{\tfrac{{p - 1}} {d}} \cdot \left( {\tfrac{{1 - g^{p - 1} }} {{1 - g^{\tfrac{{p - 1}} {d}} }}} \right) \cdot \mu \left( {\tfrac{{p - 1}} {d}} \right)}$

Next note that: $\displaystyle \left. p \right|\left( {1 - g^{p - 1} } \right)$ and $\displaystyle p \not| ( 1-g^{\tfrac{p-1}{d}} )$ when $\displaystyle \left. d \right|\left( {p - 1} \right) \wedge d \ne 1$ simply because g is a primitive root.

Thus: $\displaystyle S \equiv g^{\tfrac{{p - 1}} {1}} \cdot \left( {\tfrac{{1 - g^{p - 1} }} {{1 - g^{\tfrac{{p - 1}} {1}} }}} \right) \cdot \mu \left( {\tfrac{{p - 1}} {1}} \right) \equiv \mu \left( {p - 1} \right)\left( {\bmod .p} \right)$ $\displaystyle \square$

4. Originally Posted by ThePerfectHacker
Here is a hint. If $\displaystyle a$ is a primitive root, then all primitive roots of mod $\displaystyle p$ are $\displaystyle a^k$ where $\displaystyle 1\leq k\leq n$ and $\displaystyle (k,n)=1$.
What's $\displaystyle n$?

You mean $\displaystyle \phi(p)$, right?

And isn't the inverse of $\displaystyle a^k$ congruent to $\displaystyle a^{p-k-1}$ because $\displaystyle a^k a^{p-k-1} = a^{p-1} \equiv 1 \mod{p}$?

5. Originally Posted by chiph588@
What's $\displaystyle n$?

You mean $\displaystyle \phi(p)$, right?
If $\displaystyle a$ is primitive root say for $\displaystyle p=11$ then all other primitive roots are congruent with $\displaystyle a,a^3,a^7,a^9$ because we need to have $\displaystyle a^k$ where $\displaystyle (k,n)=1$ here $\displaystyle n=\phi(11) = \phi(10)$ so we have $\displaystyle (k,10)=1$ which happens with $\displaystyle k=1,3,7,9$.

And isn't the inverse of $\displaystyle a^k$ congruent to $\displaystyle a^{p-k-1}$ because $\displaystyle a^k a^{p-k-1} = a^{p-1} \equiv 1 \mod{p}$?
I meant that . But the idea is still okay, again if $\displaystyle p=11$ then product of primitive roots is congruent to $\displaystyle a\cdot a^3 \cdot a^7\cdot a^9$. Now pair the inverses $\displaystyle a\to a^9 , a^3\to a^7$ and everything collapses to 1 mod p.