MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $r \ge 3$ be a fixed integer. I'm interested in primes p such that no integer in the interval $(-\sqrt{p}, \sqrt{p})$, except $1$ (and $-1$ if $r$ is even), is an r-th root of unity modulo p.

The naive heuristic that $r$-th roots of unity should be "randomly distributed" suggests that there should be infinitely many such primes, and indeed they should have density 1 among all primes. Can this be made rigorous?

share|cite|improve this question
Suppose $r=3$, so that we are looking at roots of $x^2+x+1$. Then this seems like it should follow immediately from results on uniform distribution of solutions to quadratic congruences mod $p$; see – so-called friend Don Apr 11 '14 at 15:36
Yes, it definitely does, and $r=4,r=6$ as well. – Will Sawin Apr 11 '14 at 15:38
up vote 14 down vote accepted

OK, thinking a little more clearly about this... (hopefully) Say $p\le N$ fails to have the property you want. Then $p | n^r-1$ for some $|n| < \sqrt{p} \le \sqrt{N}$. There are only $O(\sqrt{N})$ integers of the form $n^r-1$ with $n$ in this range, and each has only $O(\log{N})$ prime factors. So there are only $O(\sqrt{N} \log{N})$ exceptional primes $p \leq N$, which is tiny compared to $\pi(N)$.

share|cite|improve this answer
Sweet! So this shows in fact that I could replace $(-\sqrt{p}, \sqrt{p})$ with any interval of the form $(-p^{\delta}, p^\delta)$ with $\delta < 1$ (which seems reasonable). – David Loeffler Apr 11 '14 at 16:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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