Erdős Problem #676
Editorial depth: Reviewed explanatory article — evidence qualified.
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.
The question in plain language
Can every sufficiently large positive integer be written as a multiple of a prime square, plus a remainder smaller than that prime?
Erdős Problem #676 asks whether all integers beyond some cutoff admit
This asks for every sufficiently large \(N\), not just almost all. The maintained catalogue says OPEN, although sieve arguments show the desired representation is common.
A small example
Ten is representable: \(10=1\cdot3^2+1\), with \(p=3\) and remainder \(1<3\). Twenty-four is also representable: \(24=6\cdot2^2+0\).
But \(N=6\) is not. The only eligible prime is \(2\) (because \(p^2\leq N\)), and the remainder when dividing 6 by \(4\) is 2, not strictly less than 2. Similarly, \(N=14\) fails for both eligible primes: its remainders modulo \(4\) and \(9\) are 2 and 5, respectively. These are small finite counterexamples to an assertion about every positive integer; they do not refute eventual representability.
What is known
There is an exact and efficient modular reformulation. Given a prime \(p\) with \(p^2\leq N\), the division algorithm gives
The coefficient is at least one, and the desired remainder restriction is exactly
Therefore a positive integer \(N\) is an exception if and only if
This is the complete finite witness test, with no approximations. It also clarifies why a single modulus cannot settle the global existence statement.
An exact elementary enumeration using this criterion finds 86 exceptions among the integers from 1 through 400, beginning
These finite data can test code or refute a proposed small cutoff. They cannot show that exceptions continue indefinitely.
The sieve boundary. The maintained catalogue attributes to the sieve of Eratosthenes that almost all integers have the representation. It also quotes a Brun–Selberg sieve estimate: the number of exceptions in \([1,X]\) is at most
for some positive constant \(c\). Even if rigorously established, that upper bound allows an unbounded number of exceptions. It is not a proof that all sufficiently large integers are representable.
The source records Erdős's suspicion that infinitely many exceptions exist. It discusses two different questions: dropping the requirement that \(p\) is prime and allowing a larger remainder of size \(c_Np\). Results for those variants do not automatically resolve this exact prime-and-remainder statement.
GCL's current state
The authenticated source return on original issue #1947 records the modular equivalence and small exact examples. Its disposition is BOUNDED_TASK_DESIGNED. The original Erdős [Er79], [Er79d], [Er80] passages and full original sieve proof pages remain uninspected.
One unofficial web mirror applies a SOLVED label without a verifiable theorem source; that claim has not been adopted. The authoritative maintained catalogue and frozen GCL source both say OPEN.
This manuscript is an unaccepted draft, not a mathematical solution or a source-locked theorem certification.
What remains
An efficient bounded mathematical investigation is to reproduce the exact exception count for a finite range with a verified prime sieve, then rigorously derive a source-backed quantitative upper bound on the number of exceptions. A different, potentially decisive route would construct infinitely many integers for which every eligible prime fails the remainder test, proving the eventual-representation claim false.
The hard step is simultaneous control across all primes \(p\leq\sqrt N\), not the easy modular equivalence for one prime. Finite computation can falsify attempted lemmas but cannot establish infinitude or eventual absence.
The 1979–1980 source passages and original sieve bound need precise theorem/page review. Protected publication, deployed mathematical rendering and a separate V2 admission also remain outstanding.
Sources and claim boundaries
-
Maintained Erdős Problem #676, OPEN status and sieve remarks.
-
Revision history #676, April 2026 wording.
-
GCL original issue-bound source report, exact modular criterion and finite checks.
-
Erdős [Er79], [Er79d], [Er80, p.107] and the original sieve proofs: not directly inspected.
Boundary: exact finite arithmetic and correctly attributed prior sieve claims; no all-large-N proof, infinite exceptional family, protected merge, deployed browser MathJax validation or V2 editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1947 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.