Let $p$ be a prime that is congruent to 1 mod 4. Show that the sum of the primitive roots mod $p$ is zero mod $p$

Let $p$ be a prime that is congruent to 1 mod 4. Show that the sum of the primitive roots mod $p$ is zero mod $p$.

Kind of at a loss here of how to do this. Can also reformulate the question as being if $S$ is a complete set of residues $mod\ p$, then the sum of the primitive roots in $S$ is $0\ mod\ p$.

If $p \equiv 1 \bmod 4$ and $g$ is a primitive root mod $p$, then so is $-g$.

Indeed, let $m$ be the order of $-g$. Then of course $m \le p-1$.

If $m$ is even, then $1=(-g)^m=g^m$ and so $m \ge p-1$. Hence, $m=p-1$.

If $m$ is odd, then $1=(-g)^m=-g^m$ and so $g^m=-1=g^{\frac{p-1}{2}}$. Therefore, $m \equiv \frac{p-1}{2} \bmod p-1$ and so $m=\frac{p-1}{2}$, because $m \le p-1$. But this cannot happen because $m$ is odd and $\frac{p-1}{2}$ is even.

If $g$ is a primitive root, then $g\ne -g$.

Indeed, $g=-g$ would imply $2g=0$ and so $g=0$.

The sum of all primitive roots is zero.

Both $g$ and $-g$ appear in the sum.

• Hm, from here I guess you could group all the primitive roots $g$ with primitive roots $-g$ and get the sum to $0$ but how do you know this fact? – SS' Apr 10 '18 at 2:02
• Hm so $(-g)^{\frac{p-1}{2}} = (-1)^{\frac{p-1}{2}} \cdot g^{\frac{p-1}{2}} = -1$ if $p \equiv 1\ mod 4$ – SS' Apr 10 '18 at 2:08
• I think I follow the rest of the proof from here, but just to make sure, is it correct to say that since for every primitive root $g$, there is a primitive root $-g$, the sum therefore $= 0$? Thanks! – SS' Apr 10 '18 at 2:12
• Tried to think about why $-g \neq g$ but the best I got is that they're elements from a complete set of residues, so hence incongruent. – SS' Apr 10 '18 at 2:21
• @SS, see the details in my edited answer. Perhaps we can clear the comments? – lhf Apr 10 '18 at 2:27

An advanced way is to think of the Cyclotomic polynomial. $\Phi_{p-1}(x),$ which has primitive $p-1$th roots of unity as roots.

But you can show that in general: $$\Phi_{4m}(x)=\Phi_{2m}(x^2)$$

This can be seen by using the rule:

$$\Phi_n(x)=\prod_{d\mid n}\left(x^d-1\right)^{\mu(n/d)}$$

But when $n/d$ is divisible by $4$, $\mu(n/d)=0$ so:

$$\Phi_{4m}(x)=\prod_{d\mid 2m}\left(x^{2d}-1\right)^{\mu(2m/d)}=\Phi_{2m}(x^2)$$

This means that $\Phi_{4m}(x)$ has, as the sum of roots, zero.

This same argument shows that:

$$\Phi_{mq^2}(x)=\Phi_{mq}(x^q)$$

So for a prime $p\equiv 1\pmod{q^2}$ for any $q>1$ then the sum of the generators modulo $p$ is zero.

So it is true for $p=19,$ for example, which has generators $2,2^5=13,2^7\equiv14,2^{11}\equiv15,2^{13}\equiv3,2^{17}\equiv10$, and $$2+13+14+15+3+10=57$$ is divisible by $19.$

This leads to two conjectures:

The sum of the generators modulo $p$ is $0$ if and only if $\mu(p-1)=0,$ that is , if $p-1$ is divisible by a prime squared.

and

Define $Q$ to be the set or primes whose generators do not add up to $0.$ Then: $$q(x)=\left|\{p\in Q\mid p\leq x \}\right|$$ then $$\frac{q(x)}{\pi(x)}\to \prod_p\left(1-\frac{1}{p(p-1)}\right)$$