Erdős Problem #51
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
Euler's totient function \(\phi(n)\) counts the positive integers up to \(n\) that are relatively prime to \(n\). Many different integers have the same totient value. If a number \(a\) occurs as such a value, let \(n_a\) be the smallest positive integer with \(\phi(n_a)=a\).
Erdős Problem #51 asks whether there are infinitely many different totient values \(a\) for which the ratio of this smallest preimage to \(a\) becomes arbitrarily large, in the precise sense
for some infinite set \(A\) of totient values. This remains OPEN. The problem concerns the least preimage, not just the existence of integers with a large ratio \(n/\phi(n)\).
A small example
The smallest integer with totient value 8 is 15, since \(\phi(15)=8\). This gives \(n_8/8=15/8\). Similarly,
Their least preimages are respectively \(25\), \(35\) and \(51\). An independently checked enumeration of all \(1\le n\le100\) confirms these values, along with \(\phi(69)=44\) and the fact that 69 is its least preimage.
For any positive integer \(n\), Euler's product identity gives
Thus a large ratio requires the least preimage \(n_a\) to have a product of prime factors with a sufficiently large cumulative effect. It is not enough to construct some integer \(n\) with large \(n/\phi(n)\); another, smaller integer may have the same totient value.
What is known
The maintained problem record links this question to earlier work of Erdős and to Carmichael's conjecture about whether a totient value can have exactly one preimage. It reports an Erdős theorem that a single uniquely represented totient value, if one exists, would force infinitely many. That conditional result does not settle the question about divergent ratios of least preimages.
The historical reference [Er95] is Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165–186. Guy's Unsolved Problems in Number Theory discusses related totient questions (B36 and B39). The original source pages and the separate [Er98] citation have not been independently checked line by line here.
GCL's current state
Authenticated GCL source audit #1320 records the exact infinite-set quantifiers, a 21-value finite computation independently checked against direct coprimality counts, and a proposed larger but bounded totient sieve. The pinned Formal Conjectures source for #51 encodes a least preimage for each member of an infinite set, with convergence of the quotient to infinity. Its research theorem is unfilled, not a GCL proof certificate.
What remains
To answer Erdős's question, one must prove that some infinite sequence of totient values has least-preimage ratios tending to infinity, or rule out this possibility. The proposed bounded computation to \(10^6\) would check exact first occurrences and numerical ratios. It cannot decide an assertion about every sufficiently large member of an infinite set.
Sources and claim boundaries
- Erdős Problems #51: maintained OPEN problem and source bibliography.
- Erdős (1995), primary bibliographic record: original publication; exact problem page not independently reproduced in this article.
- GCL source return #1320: finite arithmetic and formal-predicate interpretation, not a solution.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1320 — 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.