# Thread: Sum of primitive roots module p

1. ## Sum of primitive roots module p

Let p be a prime, show that the sum of all the primitive roots module p is congruent to $u(p-1)$ module p. u is the mobius function.
I am considering the polymonial $\Pi (x-g^k)$ in $Z/pZ[x]$, where g is a primitive root, and the product is taken over all k such that g^k is also a primitive root. and...???

Any help or new idea would be appriciated.

2. A couple ideas.

Idea 1: Let $g$ be a primitive root module $p$.

What you want to compute is: $\displaystyle\sum_{(k,p-1)=1; 1\leq k \leq p-1} g^k$ in module p.

Idea 2: Let $f:\mathbb{Q}^+\to \mathbb{R}$ and $F(n) = \displaystyle\sum_{(k,n)=1; 1\leq k \leq n} f \left( \frac{k}{n}\right)$

Then it can be shown that: $\sum_{k|n} F(k) = \sum_{k=1}^n f\left(\frac{k}{n}\right)$ - prove this!.

Mixing these 2 well works, I leave you the rest.

3. I have proved the idea 2 by argument on the fractions k/n, where all k are between 1 and n.
But I don't see how idea 2 is applied to this problem.
Will you expain the details, please? or give a hint. Thanks again for you new idea.

4. First, we begin ignoring the module (and then eventually we will take the module).

We want to be able to compute $F(n) = \displaystyle\sum_{(k,n)=1; 1\leq k \leq n} f \left( \frac{k}{n}\right)$ where $f \left( \frac{k}{n}\right) = a^{\tfrac{k}{n}}$ for a fixed $a\in \mathbb{R}$

We know that $\sum_{k|n} F(k) = \sum_{k=1}^n a^{\tfrac{k}{n}} = \displaystyle\frac{a^{\tfrac{1}{n}} - a^{\tfrac{1}{n} + 1}}{1-a^{\tfrac{1}{n}}}$

Now we apply Möbius inversion formula: $F(n) = \sum_{d|n}{\mu\left(\frac{n}{d}\right)\cdot \frac{a^{\tfrac{1}{d}} - a^{\tfrac{1}{d} + 1}}{1-a^{\tfrac{1}{d}}} }$

Set $n = p-1$ and $a = g^{p-1}$

Thus: $F(p-1) = \displaystyle\sum_{d|(p-1)}{\mu\left(\frac{p-1}{d}\right)\cdot g^{\frac{p-1}{d}} \cdot \frac{1 - g^{p-1}}{1- g^{\frac{p-1}{d}}}$ - no module involved yet.

But now, $g^{p-1} \equiv 1 (\bmod. p)$ and $g^{\tfrac{p-1}{d}} \not\equiv 1 (\bmod. p)$ for all $d|(p-1)$ such that $d>1$ ( since g is a primitive root) and so in those cases we have that $\frac{1 - g^{p-1}}{1- g^{\frac{p-1}{d}}}$ is a multiple of $p$ (it's not difficult to see it's an integer).

Hence $F(p-1)\equiv \mu(p-1) \cdot g^{p-1} \cdot \frac{1 - g^{p-1}}{1- g^{p-1}} (\bmod. p)$, therefore $F(p-1) \equiv \mu(p-1) (\bmod.p)$

But $F(p-1)(\bmod.p)$ is what we wanted to compute! - by idea 1.

5. but then 1-g^(p-1) is equivlent to 0 mod p. what is 0/0 mod p? I think, it can be any nonzero element in Z/pZ, or even 0 itself. It is not well defined, and I am not convinced that it equals 1. why not 2 ?
we can't just ignore the fraction part, right? I believe, you have noticed that, too.
Although a little disagreement appears, thank you all the same.