Erdős Problem 1058
Statement and scope.
Let $p<q$ be the first two primes greater than $n$. Are $n=1,2,3,4,5$ the only positive integers for which every prime factor of $n!+1$ belongs to $\{p,q\}$? The published answer is yes, by Luca. This write-up gives a partial reconstruction: it checks the small cases and proves that any putative example with $n\geq32$ must use both primes with positive exponents. Excluding those mixed products is unresolved in this write-up.
The five positive examples.
The values for $n=1,\ldots,5$ are respectively \[
n!+1=2,\quad3,\quad7,\quad25,\quad121.
\] Their prime factors belong respectively to $\{2,3\},\{3,5\},\{5,7\},\{5,7\},\{7,11\}$. For an arbitrary $n$, the proposed condition is equivalent, by unique factorization, to \[
n!+1=p^a q^b,\qquad a,b\in\mathbb Z_{\geq0}.
\tag{1}
\] Notice that zero exponents are allowed in the question.
Eliminating every pure prime power for large $n$.
Bertrand's postulate, applied twice, gives $q<4n$ for $n\geq2$. Suppose $n\geq32$ and $n!+1=\ell^a$, where $\ell$ is either $p$ or $q$. Then $\ell>n$, $\ell<4n$, and \[
\ell^a=n!+1<(n+1)^n.
\] Since $\ell\geq n+1$, we have $1\leq a<n$. Write $v_2(u)$ for the exponent of $2$ in $u$. For odd $\ell$, elementary factorization gives \[
v_2(\ell^a-1)=
\begin{cases}
v_2(\ell-1),&a\ \hbox{odd},\\
v_2(\ell-1)+v_2(\ell+1)+v_2(a)-1,&a\ \hbox{even}.
\end{cases}
\tag{2}
\] To see the second identity, write $a=2^t u$ with $u$ odd. Factoring the odd power leaves the valuation unchanged. Factor $\ell^{2^t}-1$ into $\ell-1,\ell+1$, and the $t-1$ factors $\ell^{2^j}+1$, each of the latter having valuation one. The first identity follows from the odd sum of $a$ odd terms. Exactly one of the consecutive even integers $\ell-1,\ell+1$ has valuation one. Thus in either case \[
v_2(\ell^a-1)
\leq\log_2(4n+1)+\log_2 n
<2\log_2 n+3.
\tag{3}
\] But Legendre's formula, or summing the binary digits of $n$, gives \[
v_2(n!)=n-s_2(n)\geq n-\lfloor\log_2 n\rfloor-1
\geq n-\log_2 n-1.
\tag{4}
\] For every real $n\geq32$, we have $n>3\log_2n+4$: it holds at $32$, and the derivative of $n-3\log_2n-4$ is positive there and thereafter. Consequently $4$ exceeds the upper bound $3$, contradicting $n!=\ell^a-1$. This eliminates $a=0$ or $b=0$ in $1$ for $n\geq32$.
An exact finite check.
For completeness, the following integer-only procedure checks any specified finite range. It does not require factoring $n!+1$: divide out just the two allowed primes.
F = 1
for n in range(1, 1001):
F *= n
p = least_prime_greater_than(n)
q = least_prime_greater_than(p)
R = F + 1
for ell in (p, q):
while R % ell == 0:
R //= ell
if R == 1:
record(n)
Trial division suffices to determine the small primes in this range. The exact check records only $1,2,3,4,5$. In particular it disposes of $6\leq n<32$, but a finite search cannot settle arbitrary $n$.
Remaining gap and attribution.
The mixed case $p^a q^b$, with $a,b\geq1$, is the substantive gap. The valuation calculation for one prime does not extend by separately adding the valuations of $p^a-1$ and $q^b-1$, and no such invalid step is used here. Luca's paper
On a conjecture of Erdős and Stewart (Mathematics of Computation 70 $2001$, 893--896) proves the full statement; its result is reported for context rather than substituted for the missing mixed-product proof. Source statement and reference checked 24 September 2026:
https://www.erdosproblems.com/1058. The numerical estimate below rates the proof supplied here, not the established status of the original problem.
Completion estimate.
COMPLETION: 25%