"Half-primitive root"?

Question

I've made a topic related to this (but containing a different question) and it got no responses, so I was wondering if I've stumbled on something new or if it's obvious and I'm just not seeing it at the moment.

Everyone knows that a primitive root is a number $a$ with $\gcd(a,p)=1$ (p is prime) such that the multiplicative order of $a$ relative to the modulus $p$ is $p-1$, hence $a^{p-1}\equiv 1$ and $a,a^2,...,a^{p-2},a^{p-1}$ are $\{1,2,3,4,...,p-1\}$ in some order.

However, what about half-primitive roots? I was investigating a simple problem:

Prove that $1^q+2^q+...+(p-1)^q$ is divisible by $p$ if $q$ is a positive integers not divisible by $p-1$.

I managed to prove this using primitive roots, but it was a bit too quick so I started looking at other approaches that don't rely on this "heavy machinery". And then I noticed that the problem is trivial if $q$ is odd (since $k^q+(p-k)^q\equiv 0\pmod p$ in this case and we're done by summing from $k=1$ to $k=(p-1)/2$). Therefore we only need to consider when $q$ is odd. In this case, I realized that a simple reduction reduces the problem to proving that $1^q+2^q+...+((p-1)/2)^q$. Then I realized that, for $p=4k+3$, the number $(p+1)/4$ is special in that it acts as a "half-primitive root", i.e.

(*): $(p+1)/4, ((p+1)/4)^2,...,((p+1)/4)^{(p-1)/2}$ is the same as $1^q,2^q,...,((p-1)/2)^q$ in some order for all even $q$'s that aren't divisible by $p-1$ (by definition). (it also satisfies $\text{ord}_p((p+1)/4)=(p-1)/2$, analogous to primitive roots)

So I wondered whether the concept of "half-primitive root" exists in number theory, and how useful it is? In particular, can you prove that fact (*) that I stated above?

Answer 1

A couple of observations that won't quite fit into a comment.

• A half-primitive root modulo a prime number $p$ is (unless I misunderstood) simply a generator of the group of quadratic residues modulo $p$. That group is cyclic as a subgroup of a cyclic group.
• The formula $(p+1)/4$ does not always work. For example, if $p=31$, then $(p+1)/4=8$. But as powers of $8$ you only get the residue classes $1$, $8$, $2$, $16$, $4$ and then back to $1$. Only five out of $p-1=30$, so much less than the wished for one half.
• It is possible to find half-primitive roots for some suitable moduli other than the usual powers of odd primes. For example powers of $5$ give you one half of the odd (=coprime) residue classes modulo $2^k$ for all $k>2$. Also if the modulus $n$ has only two prime factors $p$ and $q$ such that $\gcd(p-1,q-1)=2$, then there is a half-primitive root modulo $n$. For example with $n=45=3^2\cdot 5$ there are $\phi(n)=24$ residue classes modulo $45$ that are coprime to $45$. Here it is easy to check that twelve of them, exactly one half, are powers of two, namely $1,2,4,8,16,32,19,38$, $31$, $17$, $34$ and $23$.
• But if $n$ has at least three prime factors (or two prime factors congruent to $1\pmod 4$), it is easy to prove that no half-primitive roots exist.