Skip to content

Erdős Problem #1073

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

For which composite numbers \(u\) is there an integer \(n\ge0\) such that

\[ u\mid n!+1? \]

Let \(A(x)\) count those composite \(u\) with \(u<x\). Erdős Problem #1073 asks whether this counting function grows more slowly than every fixed positive power of \(x\):

\[ A(x)\le x^{o(1)}. \]

In plain language, are composite divisors of numbers of the form \(n!+1\) exceptionally sparse when we require the divisor \(u\) itself to be the modulus?

A small example

The smallest two examples are immediate:

\[ 4!+1=25,\qquad5!+1=121. \]

Thus \(u=25\) and \(u=121\) both qualify, and neither is prime. The number \(169\) qualifies because \(169\mid12!+1\).

A direct modular scan of every composite \(u\le1000\) finds exactly seven qualifying moduli:

\[ 25,\ 121,\ 169,\ 437,\ 551,\ 667,\ 721. \]

Their smallest witness indices are respectively \(4,5,12,18,18,18,6\). Therefore \(A(1001)=7\). These finite results agree with the catalogue's published initial terms.

What is known

The source question was raised by Erdős in discussions with Hardy and Subbarao, and is associated with their 2002 paper and Guy's collection, problem A2. The maintained catalogue calls the proposed subpolynomial growth open.

A useful elementary observation makes bounded checking exact: if \(n\ge u\), then \(u\) is a factor of \(n!\), so

\[ n!+1\equiv1\pmod u. \]

Therefore a successful witness for \(u\) must satisfy \(n<u\). To test one composite modulus, it is enough to compute at most \(u\) successive factorial residues; no unbounded search is needed. This exact finite search property says nothing by itself about how \(A(x)\) grows for arbitrarily large \(x\).

GCL's current state

Authenticated source audit #2344 checks the strict boundary \(u<x\), the distinction from the neighboring prime question #1072, and the frozen Lean definition. That formal statement contains an unproved general growth claim.

The seven-modulus finite table was generated by exact modular multiplication. The original Hardy–Subbarao source pages and the exact exponent conventions have not yet been independently reviewed.

What remains

One would need a uniform mathematical upper bound on the count of qualifying composites, not merely a longer list. A bounded successor can reproduce the first thousand cases using both modular residues and independent arbitrary-precision factorial arithmetic, then check the original printed statement. The current manuscript records the finite evidence without treating it as an asymptotic proof.

Sources and claim boundaries

  • Erdős Problem #1073, maintained open problem and sequence reference A256519.
  • Hardy and Subbarao, A modified problem of Pillai and some related questions (2002), pp. 554–559; primary proof review pending.
  • Frozen Lean definition.
  • Authenticated GCL return #2344. The seven examples are computationally verified, not a new asymptotic theorem. This remains an unaccepted editorial draft.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2344 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction