Problem 436

If $p$ is a prime and $k,m\geq 2$ then let $r(k,m,p)$ be the minimal $r$ such that $r,r+1,\ldots,r+m-1$ are all $k$ th power residues modulo $p$ . Let

\Lambda(k,m)=\limsup_{p\to \infty} r(k,m,p).

Is it true that $\Lambda(k,2)$ is finite for all $k$ ? Is $\Lambda(k,3)$ finite for all odd $k$ ? How large are they?

Source: erdosproblems.com/436

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label (OPEN; page last edited 25 October 2025). The site's commentary credits Hildebrand (Michigan Math. J. 38 (1991)) with a yes to the first question: $\Lambda(k,2)$ is finite for every $k$ . It credits Lehmer, Lehmer, Mills and Selfridge (Math. Comp. 16 (1962)) with $\Lambda(3,3)=23532$ . It names two questions as remaining: whether $\Lambda(k,3)$ is finite for every odd $k\geq5$ , and how $\Lambda(k,2)$ and $\Lambda(k,3)$ grow with $k$ . Claim pages: Hildebrand 1991 (accepted, partial: the first question) and Lehmer, Lehmer, Mills and Selfridge 1962 (accepted, partial: the case $k=3$ of the second question).

BLL64: Brillhart, John and Lehmer, D. H. and Lehmer, Emma, Bounds for pairs of consecutive seventh and higher power residues. Math. Comp. (1964), 397-407.
BiMi63: Bierstedt, R. G. and Mills, W. H., On the bound for a pair of consecutive quartic residues of a prime. Proc. Amer. Math. Soc. (1963), 628-632.
Du65: Dunton, M., Bounds for pairs of cubic residues. Proc. Amer. Math. Soc. (1965), 330-332.
Gr64g: Graham, R. L., On quadruples of consecutive $k$ th power residues. Proc. Amer. Math. Soc. (1964), 196-197.
Hi91: Hildebrand, Adolf, On consecutive $k$ th power residues. II. Michigan Math. J. (1991), 241-253.
LLM63: Lehmer, D. H. and Lehmer, Emma and Mills, W. H., Pairs of consecutive power residues. Canadian J. Math. (1963), 172-177.
LLMS62: Lehmer, D. H. and Lehmer, E. and Mills, W. H. and Selfridge, J. L., Machine proof of a theorem on cubic residues. Math. Comp. (1962), 407-415.
LeLe62: Lehmer, D. H. and Lehmer, Emma, On runs of residues. Proc. Amer. Math. Soc. (1962), 102-106.

Problem 436

Status

Proof claims

Discussion