2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.