Maths Olympiad Prep

Library / /20 of 39

Number theory Difficulty 5.6 AIME, harder Prove it Ukraine

For every positive integer mm denote by σ(m)\sigma(m) the sum of all its divisors, and by ϕ(m)\phi(m) the number of positive integers less than mm and coprime with mm. Prove that there exists infinitely many such positive integer numbers nn for which ϕ(σ(n))>n\phi(\sigma(n)) > n.

Solution

Consider number n=2p1n = 2^{p-1}, where pp is a prime number. Then σ(n)=2p1\sigma(n) = 2^p - 1. Let's prove that ϕ(2p1)>2p1\phi(2^p - 1) > 2^{p-1} for infinitely many primes pp.

Let m=2p1=p1α1pkαkm = 2^p - 1 = p_1^{\alpha_1} \dots p_k^{\alpha_k}. Then
ϕ(m)=(2p1)p11p1pk1pk. \phi(m) = (2^p - 1) \frac{p_1 - 1}{p_1} \dots \frac{p_k - 1}{p_k}.
Notice that every pi>pp_i > p, i=1,,ki = 1, \dots, k. Really, as it follows from the little Fermat theorem, 2pi11(modpi)2^{p_i-1} \equiv 1 \pmod{p_i}, and 2p10(modpi)2^p - 1 \equiv 0 \pmod{p_i} as well, therefore (pi1)p(p_i - 1) \nmid p, because pp is a prime number.

Hence m=2p1=p1α1pkαk>pkm = 2^{p-1} = p_1^{\alpha_1} \dots p_k^{\alpha_k} > p^k and so kplogp2k \le p \log_p 2. I.e. kp2k \le \frac{p}{2} for sufficiently large pp.

Then
ϕ(2p1)2p12p12p(11p)p. \frac{\phi(2^p-1)}{2^{p-1}} \ge \frac{2^{p-1}}{2^p} \left(1 - \frac{1}{p}\right)^p.
But (11p)p1e\left(1 - \frac{1}{p}\right)^p \to \frac{1}{e} as pp \to \infty, therefore the number n=2p1n = 2^{p-1} satisfies the condition for sufficiently large pp.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.