COLLOQU IUM MATHEMAT ICUM VOL. LXVIII 1995 FASC. 1 ON INTEGERS NOT OF THE FORM n − ϕ(n) BY

exist infinitely many positive integers not of the form n − ϕ(n), where ϕ is the Euler function. We answer this question in the affirmative by proving Theorem. None of the numbers 2k · 509203 (k = 1, 2,...) is of the form n − ϕ(n). Lemma 1. The number 1018406 is not of the form n − ϕ(n). P r o o f. Suppose that (1) 1018406 = n − ϕ(n) and let (2) n = j∏ i=1 qαii (q1 < q2 <... < qj primes). If for any i ≤ j we have αi> 1 it follows that qi | 2 ·509203, and since 509203 is a prime, either qi = 2 or qi = 509203. In the former case n − ϕ(n) ≡ 0 6≡ 1018406 (mod 4), in the latter case n − ϕ(n)> 1018406, hence (3) αi = 1 (1 ≤ i ≤ j). Since n> 2 we have ϕ(n) ≡ 0 (mod 2), hence n ≡ 0 (mod 2). However, n/2 cannot be a prime since 1018405 is composite. Hence ϕ(n) ≡ 0 (mod 4) and n ≡ 2 (mod 4). Moreover, n ≡ 1 (mod 3) would imply ϕ(n) ≡ n − 1018406 ≡ 2 (mod 3), which is impossible, since ϕ(n) ≡ 0 (mod 3) if at least one qi ≡ 1 (mod 3), 1 (mod 3) otherwise. Hence n ≡ 2 (mod 12) or n ≡ 6 (mod 12) and (4) n − ϕ(n)> 1 2 n