Erdős #1209 · number theory

For the first two questions Erdős [Er80] wrote 'unless I overlook a trivial way of getting a counterexample these questions are quite hopeless'.

There is indeed a trivial counterexample (a variant of the construction in [429]): define $a_1=2$ and for $k\geq 2$ let $a_k>a_{k-1}$ be a prime such that $a_k+k\equiv 0\pmod{q_k}$, where $q_k$ is some prime not dividing $k$. This sequence can be made to grow arbitrarily fast. A similar construction with $\pmod{q_k^2}$ provides a counterexample to the squarefree question.

ebarschkis and GPT have proved that there are no $n$ such that $n+2^{2^k}$ is always prime: let $n\geq 3$ be any odd integer. If $k$ is chosen sufficiently large, and $p=n+2^{2^{k}}$ is prime, then the multiplicative order of $2^{2^k}\pmod{p}$, say $m$ is odd, and hence if $l$ is chosen such that $2^l\equiv 1\pmod{m}$ then $p\mid n+2^{2^{k+rl}}$ for all $r\geq 1$.

See also [429] and [1102].

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.