Erdős Problem #436

Erdős Problem 436 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/436

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/436.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/436.tex.

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? Asked by Lehmer and Lehmer [LeLe62], who note that for example $\Lambda(2,2)=9$ - indeed, $9$ is always a quadratic residue, and if $10$ isn't then either $2$ or $5$ is, and hence at least one of $1,2$ or $4,5$ or $9,10$ is a consecutive pair of quadratic residues (and similarly there are infinitely many $p$ for which there are no consecutive quadratic residues below $9,10$). A similar argument of Dunton [Du65] proves $\Lambda(3,2)=77$, and Bierstedt and Mills [BiMi63] proved $\Lambda(4,2)=1224$. Lehmer and Lehmer proved that $\Lambda(k,3)=\infty$ for all even $k$ and $\Lambda(k,4)=\infty$ for all $k\leq 1048909$. Lehmer, Lehmer, and Mills [LLM63] proved $\Lambda(5,2)=7888$ and $\Lambda(6,2)=202124$. Brillhart, Lehmer, and Lehmer [BLL64] proved $\Lambda(7,2)=1649375$. Lehmer, Lehmer, Mills, and Selfridge [LLMS62] proved that $\Lambda(3,3)=23532$. Graham [Gr64g] proved that $\Lambda(k,l)=\infty$ for all $k\geq 2$ and $l\geq 4$. Hildebrand [Hi91] resolved the first question, proving that $\Lambda(k,2)$ is finite for all $k$: in other words, for any $k\geq 2$, if $p$ is sufficiently large then there exists a pair of consecutive $k$th power residues modulo $p$ in $[1,O_k(1)]$. The remaining questions are to examine whether $\Lambda(k,3)$ is finite for all odd $k\geq 5$, and the growth rate of $\Lambda(k,2)$ and $\Lambda(k,3)$ as functions of $k$. References [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.

FORMAL RESTATEMENT

Fix integers $k\ge 2$ and $m\ge 2$. For an odd prime $p$, write $\mathbb F_p^*=(\mathbb Z/p\mathbb Z)^*$. Define the set of nonzero $k$th power residues modulo $p$ by \[ \mathcal R_k(p):=\{x^k\bmod p : x\in\mathbb F_p^*\}\subseteq\{1,2,\dots,p-1\}. \] Define $r(k,m,p)$ to be the least integer $r\in\{1,2,\dots,p-m\}$ such that \[ \{r,r+1,\dots,r+m-1\}\subseteq \mathcal R_k(p). \] If no such $r$ exists, set $r(k,m,p)=\infty$. Then \[ \Lambda(k,m):=\limsup_{p\to\infty} r(k,m,p)\in[1,\infty]. \] Questions: 1) Is $\Lambda(k,2)<\infty$ for all $k\ge 2$? 2) Is $\Lambda(k,3)<\infty$ for all odd $k$? 3) What are the sizes/growth of $\Lambda(k,2),\Lambda(k,3)$ as functions of $k$?

Stress points: definition excludes $0$; otherwise $r(k,2,p)$ would trivially be $0$ because $0$ and $1$ are always $k$th powers.

QUICK LITERATURE/CONTEXT CHECK

I do not use results beyond those already named in the problem statement. The statement reports many exact values for small $k$ and $m=2$, and that Hildebrand proved $\Lambda(k,2)<\infty$ for all $k$.

ATTACK PLAN

Proof track (for special cases): 1) Prove the classical elementary bound $r(2,2,p)\le 9$ for all sufficiently large primes $p$ using residue multiplication. 2) Prove basic structural facts about $k$th powers in $\mathbb F_p^*$ (size of $\mathcal R_k(p)$).

Disproof track: Try to construct (for fixed $k,m$) infinitely many primes $p$ with no short run of $m$ consecutive $k$th power residues below some threshold.

I carry out $1$ and $2$ fully, and do computations for small primes to sanity-check definitions.

WORK

FAST REALITY CHECK (computation of $r(k,m,p)$ for small primes). Using the nonzero-residue definition above, I computed $r(k,m,p)$ for primes $p\le 2000$ or $5000$.

k=2 m=2 primes<= 2000: worst_r=9 at p=43; missing_runs=3
k=3 m=2 primes<= 5000: worst_r=36 at p=2161; missing_runs=3
k=4 m=2 primes<= 5000: worst_r=81 at p=1013; missing_runs=6
k=2 m=3 primes<= 5000: worst_r=49 at p=1303; missing_runs=6
k=3 m=3 primes<= 5000: worst_r=245 at p=2143; missing_runs=13

Here "missing_runs" counts primes with $r(k,m,p)=\infty$ in the searched range (these are small primes where $\mathcal R_k(p)$ is too sparse to contain an $m$-run).

Lemma 436.1 (elementary bound for consecutive quadratic residues). For every prime $p\ge 7$, there exists a pair of consecutive nonzero quadratic residues modulo $p$ among one of the three pairs $(1,2)$, $(4,5)$, or $(9,10)$. In particular, \[ r(2,2,p)\le 9\quad\text{for all primes }p\ge 7. \]

Proof. Let $Q\subseteq\mathbb F_p^*$ denote the set of nonzero quadratic residues modulo $p$. Then $Q$ is a subgroup of $\mathbb F_p^*$ of index $2$ (because the map $x\mapsto x^2$ is a group homomorphism with kernel $\{\pm 1\}$). In particular: - $1\in Q$ because $1\equiv 1^2$. - $4\in Q$ because $4\equiv 2^2$. - $9\in Q$ because $9\equiv 3^2$.

If $10\in Q$, then $(9,10)$ is a consecutive pair of quadratic residues and we are done. Assume instead that $10\notin Q$. Suppose for contradiction that both $2\notin Q$ and $5\notin Q$. Since $Q$ has index $2$, the complement $\mathbb F_p^*\setminus Q$ is a coset of $Q$, hence the product of two nonresidues lies in $Q$. Therefore $2\cdot 5=10$ would belong to $Q$, contradicting $10\notin Q$. Thus at least one of $2$ or $5$ is in $Q$.

- If $2\in Q$, then $(1,2)$ is a consecutive pair of residues. - If $5\in Q$, then $(4,5)$ is a consecutive pair of residues.

In all cases, one of the pairs $(1,2),(4,5),(9,10)$ consists of consecutive quadratic residues, which implies $r(2,2,p)\le 9$. $\Box$

Lemma 436.2 (count of nonzero $k$th power residues). Let $p$ be an odd prime and $k\ge 1$ an integer. Then \[ |\mathcal R_k(p)| = \frac{p-1}{\gcd(k,p-1)}. \]

Proof. The multiplicative group $\mathbb F_p^*$ is cyclic of order $p-1$. Consider the group homomorphism $\varphi:\mathbb F_p^*\to\mathbb F_p^*$ given by $\varphi(x)=x^k$. Then $\mathrm{im}(\varphi)=\mathcal R_k(p)$ by definition. By the first isomorphism theorem, \[|\mathrm{im}(\varphi)| = \frac{|\mathbb F_p^*|}{|\ker(\varphi)|} = \frac{p-1}{|\{x\in\mathbb F_p^*: x^k=1\}|}. \] Since $\mathbb F_p^*$ is cyclic of order $p-1$, the equation $x^k=1$ has exactly $\gcd(k,p-1)$ solutions (it is the unique subgroup of order $\gcd(k,p-1)$). Therefore $|\ker(\varphi)|=\gcd(k,p-1)$, giving the claimed formula. $\Box$

VERIFICATION

- The definition of $k$th power residue excludes $0$; otherwise Lemma 436.1 would be vacuous. This matches the example in the statement where $\Lambda(2,2)=9$. - Lemma 436.1: The only group fact used is that nonresidues form a coset of residues, hence product of two nonresidues is a residue; this is correct for an index-2 subgroup. - Lemma 436.2: Standard cyclic-group calculation; no hidden assumptions. - Small primes: For $p=3$ and $p=5$, there is no pair of consecutive nonzero quadratic residues, consistent with the computation reporting "missing runs".

FINAL

UNRESOLVED

(i) Strongest proved partial result: (a) For all primes $p\ge 7$, $r(2,2,p)\le 9$ (Lemma 436.1), giving an elementary upper bound consistent with $\Lambda(2,2)=9$ stated in the problem text. (b) For general $k$, the number of nonzero $k$th power residues modulo $p$ equals $(p-1)/\gcd(k,p-1)$ (Lemma 436.2).

(ii) First gap (crisp): Prove or disprove that $\Lambda(k,3)<\infty$ for all odd $k\ge 5$ (equivalently: is there a uniform bound $B(k)$ such that for all sufficiently large primes $p$ there is a run of three consecutive nonzero $k$th powers among $\{1,2,\dots,B(k)\}$?).

(iii) Top 3 next moves: 1. Computation: for fixed odd $k\ge 5$, compute $r(k,3,p)$ for primes up to much larger bounds to look for growth or apparent boundedness; identify candidate worst primes. 2. Analytic step: attempt to bound the number of solutions to $x^k\equiv n\pmod p$ in short intervals uniformly in $n$ using character sums (this is the natural bridge to the known results cited in the problem statement). 3. Structural step: relate $k$th power residues to multiplicative subgroups and study additive patterns (runs of consecutive integers) inside multiplicative subgroups.

(iv) What a minimal counterexample would likely look like: for some fixed odd $k\ge 5$, an infinite sequence of primes $p_j\to\infty$ such that for each $p_j$ every triple of consecutive integers $\{r,r+1,r+2\}$ with $1\le r\le B$ contains at least one non-$k$th-power residue, for all candidate bounds $B$; in other words, $r(k,3,p_j)\to\infty$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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? Asked by Lehmer and Lehmer [LeLe62], who note that for example $\Lambda(2,2)=9$ - indeed, $9$ is always a quadratic residue, and if $10$ isn't then either $2$ or $5$ is, and hence at least one of $1,2$ or $4,5$ or $9,10$ is a consecutive pair of quadratic residues (and similarly there are infinitely many $p$ for which there are no consecutive quadratic residues below $9,10$). A similar argument of Dunton [Du65] proves $\Lambda(3,2)=77$, and Bierstedt and Mills [BiMi63] proved $\Lambda(4,2)=1224$. Lehmer and Lehmer proved that $\Lambda(k,3)=\infty$ for all even $k$ and $\Lambda(k,4)=\infty$ for all $k\leq 1048909$. Lehmer, Lehmer, and Mills [LLM63] proved $\Lambda(5,2)=7888$ and $\Lambda(6,2)=202124$. Brillhart, Lehmer, and Lehmer [BLL64] proved $\Lambda(7,2)=1649375$. Lehmer, Lehmer, Mills, and Selfridge [LLMS62] proved that $\Lambda(3,3)=23532$. Graham [Gr64g] proved that $\Lambda(k,l)=\infty$ for all $k\geq 2$ and $l\geq 4$. Hildebrand [Hi91] resolved the first question, proving that $\Lambda(k,2)$ is finite for all $k$: in other words, for any $k\geq 2$, if $p$ is sufficiently large then there exists a pair of consecutive $k$th power residues modulo $p$ in $[1,O_k(1)]$. The remaining questions are to examine whether $\Lambda(k,3)$ is finite for all odd $k\geq 5$, and the growth rate of $\Lambda(k,2)$ and $\Lambda(k,3)$ as functions of $k$. References [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.

FORMAL RESTATEMENT

Fix integers $k\ge 2$ and $m\ge 2$. For an odd prime $p$, write $\mathbb F_p^*=(\mathbb Z/p\mathbb Z)^*$. Define the set of nonzero $k$th power residues modulo $p$ by \[ \mathcal R_k(p):=\{x^k\bmod p : x\in\mathbb F_p^*\}\subseteq\{1,2,\dots,p-1\}. \] Define $r(k,m,p)$ to be the least integer $r\in\{1,2,\dots,p-m\}$ such that \[ \{r,r+1,\dots,r+m-1\}\subseteq \mathcal R_k(p). \] If no such $r$ exists, set $r(k,m,p)=\infty$. Then \[ \Lambda(k,m):=\limsup_{p\to\infty} r(k,m,p)\in[1,\infty]. \] Questions: 1) Is $\Lambda(k,2)<\infty$ for all $k\ge 2$? 2) Is $\Lambda(k,3)<\infty$ for all odd $k$? 3) What are the sizes/growth of $\Lambda(k,2),\Lambda(k,3)$ as functions of $k$?

Stress points: definition excludes $0$; otherwise $r(k,2,p)$ would trivially be $0$ because $0$ and $1$ are always $k$th powers.

QUICK LITERATURE/CONTEXT CHECK

I do not use results beyond those already named in the problem statement. The statement reports many exact values for small $k$ and $m=2$, and that Hildebrand proved $\Lambda(k,2)<\infty$ for all $k$.

ATTACK PLAN

Proof track (for special cases): 1) Prove the classical elementary bound $r(2,2,p)\le 9$ for all sufficiently large primes $p$ using residue multiplication. 2) Prove basic structural facts about $k$th powers in $\mathbb F_p^*$ (size of $\mathcal R_k(p)$).

Disproof track: Try to construct (for fixed $k,m$) infinitely many primes $p$ with no short run of $m$ consecutive $k$th power residues below some threshold.

I carry out $1$ and $2$ fully, and do computations for small primes to sanity-check definitions.

WORK

FAST REALITY CHECK (computation of $r(k,m,p)$ for small primes). Using the nonzero-residue definition above, I computed $r(k,m,p)$ for primes $p\le 2000$ or $5000$.

k=2 m=2 primes<= 2000: worst_r=9 at p=43; missing_runs=3
k=3 m=2 primes<= 5000: worst_r=36 at p=2161; missing_runs=3
k=4 m=2 primes<= 5000: worst_r=81 at p=1013; missing_runs=6
k=2 m=3 primes<= 5000: worst_r=49 at p=1303; missing_runs=6
k=3 m=3 primes<= 5000: worst_r=245 at p=2143; missing_runs=13

Here "missing_runs" counts primes with $r(k,m,p)=\infty$ in the searched range (these are small primes where $\mathcal R_k(p)$ is too sparse to contain an $m$-run).

Lemma 436.1 (elementary bound for consecutive quadratic residues). For every prime $p\ge 7$, there exists a pair of consecutive nonzero quadratic residues modulo $p$ among one of the three pairs $(1,2)$, $(4,5)$, or $(9,10)$. In particular, \[ r(2,2,p)\le 9\quad\text{for all primes }p\ge 7. \]

Proof. Let $Q\subseteq\mathbb F_p^*$ denote the set of nonzero quadratic residues modulo $p$. Then $Q$ is a subgroup of $\mathbb F_p^*$ of index $2$ (because the map $x\mapsto x^2$ is a group homomorphism with kernel $\{\pm 1\}$). In particular: - $1\in Q$ because $1\equiv 1^2$. - $4\in Q$ because $4\equiv 2^2$. - $9\in Q$ because $9\equiv 3^2$.

If $10\in Q$, then $(9,10)$ is a consecutive pair of quadratic residues and we are done. Assume instead that $10\notin Q$. Suppose for contradiction that both $2\notin Q$ and $5\notin Q$. Since $Q$ has index $2$, the complement $\mathbb F_p^*\setminus Q$ is a coset of $Q$, hence the product of two nonresidues lies in $Q$. Therefore $2\cdot 5=10$ would belong to $Q$, contradicting $10\notin Q$. Thus at least one of $2$ or $5$ is in $Q$.

- If $2\in Q$, then $(1,2)$ is a consecutive pair of residues. - If $5\in Q$, then $(4,5)$ is a consecutive pair of residues.

In all cases, one of the pairs $(1,2),(4,5),(9,10)$ consists of consecutive quadratic residues, which implies $r(2,2,p)\le 9$. $\Box$

Lemma 436.2 (count of nonzero $k$th power residues). Let $p$ be an odd prime and $k\ge 1$ an integer. Then \[ |\mathcal R_k(p)| = \frac{p-1}{\gcd(k,p-1)}. \]

Proof. The multiplicative group $\mathbb F_p^*$ is cyclic of order $p-1$. Consider the group homomorphism $\varphi:\mathbb F_p^*\to\mathbb F_p^*$ given by $\varphi(x)=x^k$. Then $\mathrm{im}(\varphi)=\mathcal R_k(p)$ by definition. By the first isomorphism theorem, \[|\mathrm{im}(\varphi)| = \frac{|\mathbb F_p^*|}{|\ker(\varphi)|} = \frac{p-1}{|\{x\in\mathbb F_p^*: x^k=1\}|}. \] Since $\mathbb F_p^*$ is cyclic of order $p-1$, the equation $x^k=1$ has exactly $\gcd(k,p-1)$ solutions (it is the unique subgroup of order $\gcd(k,p-1)$). Therefore $|\ker(\varphi)|=\gcd(k,p-1)$, giving the claimed formula. $\Box$

VERIFICATION

- The definition of $k$th power residue excludes $0$; otherwise Lemma 436.1 would be vacuous. This matches the example in the statement where $\Lambda(2,2)=9$. - Lemma 436.1: The only group fact used is that nonresidues form a coset of residues, hence product of two nonresidues is a residue; this is correct for an index-2 subgroup. - Lemma 436.2: Standard cyclic-group calculation; no hidden assumptions. - Small primes: For $p=3$ and $p=5$, there is no pair of consecutive nonzero quadratic residues, consistent with the computation reporting "missing runs".

FINAL

UNRESOLVED

(i) Strongest proved partial result: (a) For all primes $p\ge 7$, $r(2,2,p)\le 9$ (Lemma 436.1), giving an elementary upper bound consistent with $\Lambda(2,2)=9$ stated in the problem text. (b) For general $k$, the number of nonzero $k$th power residues modulo $p$ equals $(p-1)/\gcd(k,p-1)$ (Lemma 436.2).

(ii) First gap (crisp): Prove or disprove that $\Lambda(k,3)<\infty$ for all odd $k\ge 5$ (equivalently: is there a uniform bound $B(k)$ such that for all sufficiently large primes $p$ there is a run of three consecutive nonzero $k$th powers among $\{1,2,\dots,B(k)\}$?).

(iii) Top 3 next moves: 1. Computation: for fixed odd $k\ge 5$, compute $r(k,3,p)$ for primes up to much larger bounds to look for growth or apparent boundedness; identify candidate worst primes. 2. Analytic step: attempt to bound the number of solutions to $x^k\equiv n\pmod p$ in short intervals uniformly in $n$ using character sums (this is the natural bridge to the known results cited in the problem statement). 3. Structural step: relate $k$th power residues to multiplicative subgroups and study additive patterns (runs of consecutive integers) inside multiplicative subgroups.

(iv) What a minimal counterexample would likely look like: for some fixed odd $k\ge 5$, an infinite sequence of primes $p_j\to\infty$ such that for each $p_j$ every triple of consecutive integers $\{r,r+1,r+2\}$ with $1\le r\le B$ contains at least one non-$k$th-power residue, for all candidate bounds $B$; in other words, $r(k,3,p_j)\to\infty$.