Skip to content

Erdős Problem #418

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

For a positive integer \(n\), Euler's totient function \(\varphi(n)\) counts integers from \(1\) to \(n\) that are coprime to \(n\). The difference \(n-\varphi(n)\) therefore counts the integers in that range that are not coprime to \(n\). A positive integer \(m\) is called a cototient if \(m=n-\varphi(n)\) for at least one positive integer \(n\). If no such \(n\) exists, \(m\) is a noncototient.

Erdős Problem 418 asks whether infinitely many positive integers are noncototients. This is a qualitative existence question: it does not require a positive fraction of all integers to be noncototients, or a formula for every noncototient. In the historical formulation it was asked by Erdős and Sierpiński. The distinction between infinitely many and positive density is crucial because the latter remains a separate, more demanding question.

The noncototient problem must not be confused with the nonaliquot problem involving \(\sigma(n)-n\), where \(\sigma\) denotes the sum of positive divisors. That related function has its own theorems and density estimates. Here the map is exactly \(n-\varphi(n)\).

A small example

The small integer \(10\) is a noncototient. This can be checked exhaustively using a finite calculation, provided the input range is justified rather than chosen arbitrarily. If \(n\) is prime, \(\varphi(n)=n-1\) and \(n-\varphi(n)=1\), so no prime produces \(10\). If \(n>1\) is composite, let \(p\) be its smallest prime divisor. Since \(p\leq\sqrt{n}\) and all multiples of \(p\) are excluded by the totient, we have

\[ n-\varphi(n)\geq\frac{n}{p}\geq\sqrt{n}. \]

Thus if \(n-\varphi(n)=10\), then necessarily \(n\leq100\). A complete exact-integer check of \(n=1,\ldots,100\) finds no solution. The first small noncototients under \(30\) identified by this same justified scan include \(10\), \(26\), and \(29\). Since any witness for a specified \(m\) is either prime or at most \(m^2\), these are genuine finite certificates after the range is fully checked, not merely unexplained numerical searches.

For comparison, \(n=12\) satisfies \(\varphi(12)=4\), so \(12-\varphi(12)=8\); and \(n=25\) satisfies \(\varphi(25)=20\), so its cototient value is \(5\). The computation of \(\varphi\) can be independently verified by listing coprime residues or by the exact multiplicative formula

\[ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right). \]

Showing a single number such as \(10\) is missing does not establish that infinitely many distinct numbers are missing.

What is known

The original statement occurs in Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 83 of the historical scan. Their discussion credits Erdős and Sierpiński, distinguishes odd from even target integers, and does not resolve the infinitude question. The maintained Erdős Problems #418 page also cites an earlier Erdős source from 1974 and records the later solution.

The exact affirmative theorem was published by J. Browkin and A. Schinzel, On integers not of the form \(n-\varphi(n)\), Colloquium Mathematicum 68 (1995), 55–58, DOI 10.4064/cm-68-1-55-58. The publisher's abstract expressly states the stronger constructive conclusion: for every integer \(k\geq1\), the integer

\[ 2^k\cdot509203 \]

is a noncototient. These are pairwise distinct, so the originally posed infinitude question has a positive answer. This article attributes that result to the published paper, rather than pretending that a short small-integer check reproduces its proof.

The density of noncototients remains a different question. The maintained page says positive density is open. Its discussion distinguishes noncototients from nonaliquots, whose positive-density results come from the sum-of-divisors map and do not imply the corresponding cototient result.

GCL's current state

The original GCL issue #1688 pins the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its frozen informal status is proved and its formal-status metadata is Lean. The maintained page currently says PROVED (LEAN). These status labels are evidence about reported external developments, not a substitute for a GCL-certified proof.

The pinned FormalConjectures 418.lean has Git blob 3486236c5aa264eae9f8c4046cf6c780e1155f21. Its main theorem is marked as solved and links an external Lean proof in a separate repository, but the pinned source's own theorem body is literally by sorry. A conditional odd-number variant contains a nonplaceholder proof under a strengthened Goldbach assumption; the constructive \(2^k\cdot509203\) variant and positive-density question also have placeholders in this pinned snapshot. Neither metadata nor an external proof link implies that this GCL session replayed the external Lean development.

The authenticated original issue SOURCE RESULT/1 link is authenticated original RESULT/1. The V2 editorial admissions ledger alone decides whether the Compendium article is accepted.

What remains

For the original infinitude question, the substantive mathematical resolution is already available in the Browkin–Schinzel publication. The useful bounded next task is therefore source and formal concordance, not the invention of a different proof. Read the theorem and proof in the four-page 1995 paper and compare its exact domain, the exponent restriction \(k\geq1\), and the definition of a noncototient with both the maintained problem and the pinned Lean statements.

As an executable warm-up, implement the justified finite decision test for a single target \(m\). First prove the composite bound \(n\leq m^2\) above; then check every candidate \(n\) up to the bound using exact totients. Reproduce \(m=10\) and one ordinary cototient such as \(m=8\). The acceptance condition is a complete finite certificate with no unchecked \(n\), followed by a documented theorem-to-formal-statement comparison. Falsification includes a wrong prime/composite bound, a hidden \(n>m^2\) witness, or treating a Lean placeholder as a proof. Stop after this verification; the positive-density question remains research rather than editorial reproduction.

Sources and claim boundaries

Historical question: Erdős–Graham (1980), printed p. 83. Primary resolving publication: Browkin and Schinzel (1995), publisher record, DOI 10.4064/cm-68-1-55-58. Maintained status: Problem #418. Original audit: GCL issue #1688. Frozen catalogue and pinned FormalConjectures interface.

The small \(m=10\) result follows from an exact finite certificate and a proved bound. The infinite family is an external published theorem, not an independently reproduced proof. The reported external Lean formalization was not built or replayed here. No new proof, density theorem, or GCL mathematical certification is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1688 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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