Number theoryDifficulty 7.0National OlympiadProve itPhilippines
Problem:
Given n∈N, let σ(n) denote the sum of the divisors of n and φ(n) denote the number of positive integers m≤n for which gcd(m,n)=1. Show that for all n∈N, φ(n)1+σ(n)1≥n2 and determine when equality holds.
Solution
Solution:
We note that equality holds for n=1. We prove the inequality when n>1 and show that it is strict in this case.
By the AM-GM inequality, φ(n)1+σ(n)1≥φ(n)σ(n)2. Hence, we need only show that φ(n)σ(n)<n2, or equivalently, n2φ(n)σ(n)<1. We note that f(n):=n2φ(n)σ(n) is multiplicative, i.e., f(mn)=f(m)f(n) whenever gcd(m,n)=1, and so it suffices to show that f(n)<1 when n=pk for some prime p and some integer k≥1. However, f(pk)=(pk)2φ(pk)σ(pk)=pkφ(pk)⋅pkσ(pk)=pk(p−1)pk−1⋅pk1i=0∑kpi=pp−1⋅i=0∑kpk−i1=pp−1⋅i=0∑kpi1=pp−1⋅1−p11−pk+11<pp−1⋅1−p11=1 This completes the proof.
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 reproduced verbatim; metadata (topic, difficulty) added by this project.