Paperlane

no. 16 · Tuesday 17 November 2026

On the number of elite primes

Ali Taheri and Amir Saleh

math.NT · □ lean · 11 pp

Abstract

A prime $p$ is elite if all sufficiently large Fermat numbers $F_n=2^{2^n}+1$ are quadratic nonresidues modulo $p$. Let $E(x)$ be the number of elite primes up to $x$. The best published bounds are $E(x)\ll x/(\log x)^{3/2}$ unconditionally and $E(x)\ll x^{5/6}$ under the Generalized Riemann Hypothesis (GRH), both due to Just. Just and Pollack remarked, without a written proof, that sorting primes by the exact power of $2$ dividing $p-1$ should give $x/(\log x)^{2-\varepsilon}$ and $x^{3/4+\varepsilon}$. We give complete proofs of slightly sharper statements: $E(x)\le(16+o(1))x\log\log x/(\log x)^2$ unconditionally, and $E(x)\ll x^{3/4}(\log x)^{1/2}$ under GRH. We also recall, with short proofs, known facts about the period of $(F_n\bmod p)$ that go back to Aigner: every elite prime $p$ satisfies the defining condition from the index $v_2(\operatorname{ord}_p 2)$ onwards, and the period is even unless $p\in\{3,5\}$. Finally, we show under GRH that, when the moduli involved are at most $x^{1/3}$, the set of primes bounded by the sieve argument has size $\asymp x\log\log x/(\log x)^2$. This indicates that the remaining factor $\log\log x$ cannot be removed by this method alone. All theorems of the paper have been formalized in the Lean 4 proof assistant, with the Brun–Titchmarsh inequality and two standard consequences of GRH as explicit hypotheses.

comments
11 pages. Includes a Lean 4 formalization with three analytic inputs as explicit hypotheses
fields
Number Theory
pdf ↗ page arXiv:2611.19610 ↗