On 11/20/2015 8:05 PM, David Wilson wrote:

Is

1. Is phi(n) + sigma(n) - 2n >= 0 for all n > 1?

2. Is phi(n) + sigma(n) - 2n = 5 for any n?

That the answer to (1) is yes is part of an exercise (4.2.21) in Niven, Zuckerman & Montgomery's "An Introduction to the Theory of Numbers", 5th ed. The following solution is not the simplest, but it will also allow an answer to (2). Let f(n) = phi(n) + sigma(n) - 2n. In particular, f(1) = 0; we'll consider what happens to f when new prime factors are included in n. Let p be any prime and consider f(pn) in two cases. If p does not divide n, then phi(pn) = (p - 1)phi(n) and sigma(pn) = (p + 1)sigma(n) (by the formulas in Rich's message), so f(pn) = phi(pn) + sigma(pn) - 2pn = (p - 1)phi(n) + (p + 1)sigma(n) - 2pn = p f(n) + sigma(n) - phi(n) >= p f(n), since sigma(n) >= n >= phi(n), with equality only if n = 1. If p divides n, f(pn) = phi(pn) + sigma(pn) - 2pn >= p phi(n) + (p sigma(n) + 1) - 2pn = p f(n) + 1, because phi(pn) = p phi(n) by the explicit formula and because sigma(pn) includes pd for every divisor d of n, as well as 1. This establishes (1) and a bit more: f(n) = 0 for n a prime or 1, and f(n) > 0 for all other n. It also shows f(pn) >= f(n) with equality only when n = 1; using this it is possible to show that the answer to (2) is no. Since phi(n) is even for n > 2, f(n) is odd only if sigma(n) is odd and n > 2; namely when n = k^2 or 2k^2, k > 1. The result then follows by examining f(n) for the following cases: a) For n = p^2 (for odd prime p) or n = 2^k for k <= 3. Here f(n) < 5. [In fact, f(p^2) = 1 and f(2^k) = 2^(k - 1) - 1 for k >= 1.] b) For n = 2p^2 or p^4 (for odd prime p), n = p^2 q^2 (for distinct odd primes p,q), or n = 2^4. Here f(n) > 5. [One computes f(2p^2) = 2p + 3, f(p^4) = p^2 + p + 1, and f(p^2 q^2) = (p + q)^2 + p + q + 1.] Every square or double square is either covered by a) or is a multiple of a number covered by b), so that shows f(n) is never 5. -- Fred W. Helenius fredh@ix.netcom.com