Maths Olympiad Prep

Library / /118 of 128

Number theory Difficulty 7.0 National Olympiad Prove it Philippines

Problem:

Given nNn \in \mathbb{N}, let σ(n)\sigma(n) denote the sum of the divisors of nn and φ(n)\varphi(n) denote the number of positive integers mnm \leq n for which gcd(m,n)=1\operatorname{gcd}(m, n)=1. Show that for all nNn \in \mathbb{N},
1φ(n)+1σ(n)2n \frac{1}{\varphi(n)}+\frac{1}{\sigma(n)} \geq \frac{2}{n}
and determine when equality holds.

Solution

Solution:

We note that equality holds for n=1n=1. We prove the inequality when n>1n>1 and show that it is strict in this case.

By the AM-GM inequality, 1φ(n)+1σ(n)2φ(n)σ(n)\frac{1}{\varphi(n)}+\frac{1}{\sigma(n)} \geq \frac{2}{\sqrt{\varphi(n) \sigma(n)}}. Hence, we need only show that φ(n)σ(n)<n2\varphi(n) \sigma(n)<n^{2}, or equivalently, φ(n)σ(n)n2<1\frac{\varphi(n) \sigma(n)}{n^{2}}<1. We note that f(n):=φ(n)σ(n)n2f(n):=\frac{\varphi(n) \sigma(n)}{n^{2}} is multiplicative, i.e., f(mn)=f(m)f(n)f(m n)=f(m) f(n) whenever gcd(m,n)=1\operatorname{gcd}(m, n)=1, and so it suffices to show that f(n)<1f(n)<1 when n=pkn=p^{k} for some prime pp and some integer k1k \geq 1. However,
f(pk)=φ(pk)σ(pk)(pk)2=φ(pk)pkσ(pk)pk=(p1)pk1pk1pki=0kpi=p1pi=0k1pki=p1pi=0k1pi=p1p11pk+111p<p1p111p=1 \begin{aligned} f\left(p^{k}\right) & =\frac{\varphi\left(p^{k}\right) \sigma\left(p^{k}\right)}{\left(p^{k}\right)^{2}}=\frac{\varphi\left(p^{k}\right)}{p^{k}} \cdot \frac{\sigma\left(p^{k}\right)}{p^{k}}=\frac{(p-1) p^{k-1}}{p^{k}} \cdot \frac{1}{p^{k}} \sum_{i=0}^{k} p^{i} \\ & =\frac{p-1}{p} \cdot \sum_{i=0}^{k} \frac{1}{p^{k-i}}=\frac{p-1}{p} \cdot \sum_{i=0}^{k} \frac{1}{p^{i}}=\frac{p-1}{p} \cdot \frac{1-\frac{1}{p^{k+1}}}{1-\frac{1}{p}} \\ & <\frac{p-1}{p} \cdot \frac{1}{1-\frac{1}{p}}=1 \end{aligned}
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.