---

Claim. For every integer $k\ge2$ there is a constant $c_k>0$ with

$$\sum_{p<x} n_k(p)\sim c_k\frac{x}{\log x},$$

where $n_k(p)$ is the least $k$th power nonresidue modulo $p$ for $p\equiv1\pmod k$ and $n_k(p)=0$ for the other primes. That convention is the one the precise Statement of Problem 980 adopts (see the Convention paragraph below).

Source. P. D. T. A. Elliott, A problem of Erdős concerning power residue sums, Acta Arith. 13 (1967), fasc. 2, 131–149 (card). The page's date is the editorial receipt date printed at the end of the paper, 1967-01-09; the paper's first page and the publisher's record both date the volume 1967, and the running header prints the fascicle as XIII.2.

What is proved. Theorem 1 of the paper is stronger than the claim: for every integer $k>0$ and every exponent $a<4e^{1-1/k}$,

$$\sum_{p<x} n_k(p)^a\sim C_{k,a}\frac{x}{\log x},$$

and when $k$ is an odd prime the constant is the series $C_{k,a}=\sum_{r\ge1}k^{-r}q_r^a$ over the primes $q_1<q_2<\cdots$. The claim is the case $a=1$, where $4e^{1-1/k}>1$ for every $k\ge1$. The proof combines a large-sieve count of the primes with a large least nonresidue (the step Erdős had identified as the obstacle for $k>2$) with Galois-theoretic lemmas on linear disjointness and on when a radical lies in a cyclotomic field, which control the density of primes for which a given prime $q$ is a $k$th power nonresidue. Elliott notes that Barban had stated the result without proof (The 'Large Sieve' method and its applications in the theory of numbers, Russian Math. Surveys 21 (1966), 49–104, at pp. 61–62).

Convention. Elliott defines $n_k(p)$ for $p\equiv1\pmod k$ and sets $n_k(p)=0$ for the other primes, the convention of the problem's precise Statement; Erdős's 1961 formulation and the site's statement do not restrict $p$. For prime $k$ the two readings agree, since a prime $p\not\equiv1\pmod k$ has every residue a $k$th power and no $k$th power nonresidue. For composite $k$ a prime $p\not\equiv1\pmod k$ with $\gcd(k,p-1)=d>1$ does have a least $k$th power nonresidue, equal to $n_d(p)$; the literal sum that includes these primes is the variant the problem page records under Formulation, and Elliott's theorem does not reach it. The site records the problem as proved by this paper without remarking on the convention.

Earlier case. Erdős proved the case $k=2$ in 1961, with the constant $c_2=\sum_{j\ge1}p_j/2^j$ over the primes $p_1<p_2<\cdots$, and conjectured the general case (card, equations (3) and (4); claim page); the constant $c_2$ is the number of Problem 251.

Acceptance. The paper is a refereed publication in Acta Arithmetica (refereed). The site's curator, Thomas Bloom, labels the problem proved and names this paper as the proof; the curator is independent of the author and of this project, and that credit is the reviewed evidence. No referee's report or other outside review is on record beyond the publication and that credit. This project has not checked the proof line by line and claims no verification tier for it.

Depends on. No page of this wiki.