Problem 418

Are there infinitely many positive integers not of the form $n-\phi(n)$ ?

Source: erdosproblems.com/418

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site labels the problem PROVED (LEAN): Browkin and Schinzel's 1995 theorem answers yes, and the Lean qualification corresponds to the formal proof that formal-conjectures' 418.lean records, a Lean 4 development held outside this corpus and not audited here; see the claim page (Browkin and Schinzel, 1994).

BaLu04: Banks, William D. and Luca, Florian, Noncototients and nonaliquots. arXiv:math/0409231 (2004).
BaLu05: Banks, William D. and Luca, Florian, Nonaliquots and Robbins numbers. Colloq. Math. 103 (2005), 27-32.
BrSc95: Browkin, J. and Schinzel, A., On integers not of the form $n-\phi(n)$ . Colloq. Math. (1995), 55-58.
ChZh11: Chen, Yong-Gao and Zhao, Qing-Qing, Nonaliquot numbers. Publ. Math. Debrecen (2011), 439-442.
FlLu00: Flammenkamp, A. and Luca, F., Infinite families of noncototients. Colloq. Math. 86 (2000), 37-41.
Er73b: Erdős, P., Über die Zahlen der Form $\sigma (n)-n$ und $n-\phi(n)$ . Elem. Math. (1973), 83-86.
Gu04: Guy, Richard K., Unsolved problems in number theory, third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp.; B36 "Euler's totient function", printed p. 139: the noncototients, the $n$ for which $x-\phi(x)=n$ has no solution, the Sierpiński and Erdős conjecture that there are infinitely many, and the [BrSc95] proof that none of $2^k\cdot509203$ , $k=1,2,\ldots$ , is of the form $x-\phi(x)$ . Library home: Guy 2004.
PoPo16: Pollack, Paul and Pomerance, Carl, Some problems of Erdős on the sum-of-divisors function. Trans. Amer. Math. Soc. Ser. B (2016), 1-26.

Problem 418

Status

Proof claims

Discussion