# Primitive roots mod p

• Feb 9th 2009, 06:13 PM
chiph588@
Primitive roots mod p
Here's a fun challenge problem!

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

Show that the sum of all primitive roots modulo $p$ is congruent to $\mu(p-1)$ modulo $p$.
• Feb 9th 2009, 06:40 PM
ThePerfectHacker
Here is a hint. If $a$ is a primitive root, then all primitive roots of mod $p$ are $a^k$ where $1\leq k\leq n$ and $(k,n)=1$.

Quote:

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

So we approach this by the hint, let $a$ be a primitive root. Then the product of all primitive roots mod $p$ is $\prod_{1\leq k \leq n}^{(k,n)=1} a^k$. Now for every primitive root $a^k$ we see that $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 $a^k$ is not paired with itself. But $a^k \not \equiv a^{p-k}(\bmod p)$ if $p>2$. Thus, if $p>2$ we get $1$ and if $p=2$ then we get $-1$. And so it is correct to write $(-1)^{\phi(p-1)}$ because $\phi(m)$ is even for $m\geq 3$.

Quote:

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

First a little Theorem that always comes in handy.

Theorem
: Let $
F\left( n \right) = \sum\limits_{\left( {k,n} \right) = 1;{\text{ }}1 \leqslant k \leqslant n} {f\left( {\tfrac{k}
{n}} \right)}
$
then $
\sum\limits_{\left. d \right|n} {F\left( d \right)} = \sum\limits_{k = 1}^{n} {f\left( {\tfrac{k}
{n}} \right)}
$
with $
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: $
f\left( {\tfrac{k}
{n}} \right)
$
with $
1 \leqslant k \leqslant n
$
then $
\tfrac{k}
{n} = \frac{{\tfrac{k}
{{\left( {k,n} \right)}}}}
{{\tfrac{n}
{{\left( {k,n} \right)}}}} = \tfrac{{k'}}
{{n'}}
$
where $
k' = \tfrac{k}
{{\left( {k,n} \right)}} \wedge n' = \tfrac{n}
{{\left( {k,n} \right)}}
$
note also that this implies: $
\left( {k',n'} \right) = 1 \wedge \left. {n'} \right|n
$
, hence it corresponds to one of the terms (and only one) in $
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. $\square$

_______________________________________

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

We have: $
\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: $
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: $
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)}
$
$
= \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: $
\left. p \right|\left( {1 - g^{p - 1} } \right)
$
and $
p \not| ( 1-g^{\tfrac{p-1}{d}} )
$
when $
\left. d \right|\left( {p - 1} \right) \wedge d \ne 1
$
simply because g is a primitive root.

Thus: $
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)
$
$\square$
• Feb 11th 2009, 08:55 AM
chiph588@
Quote:

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

What's $n$?

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

And isn't the inverse of $a^k$ congruent to $a^{p-k-1}$ because $a^k a^{p-k-1} = a^{p-1} \equiv 1 \mod{p}$?
• Feb 11th 2009, 02:03 PM
ThePerfectHacker
Quote:

Originally Posted by chiph588@
What's $n$?

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

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

Quote:

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