# Roots of unity near 1 in Z / p Z

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?

-
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 imrn.oxfordjournals.org/content/2000/14/719.abstract – 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

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)$.
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