Given \(n \in \mathbb{N}\), let \(\sigma (n)\) denote the sum of the divisors of \(n\) and \(\phi (n)\) denote the number of integers \(n \geq m\) for which \(\gcd(m,n) = 1\). Show that for all \(n \in \mathbb{N}\), \[\large \frac{1}{\sigma (n)} + \frac{1}{\phi (n)} \geq \frac{2}{n}\] and determine when equality holds.
Problem
Source: Philippine Mathematical Olympiad, 2017
Tags: inequalities, number theory, function
31.12.2017 13:53
Denote $\alpha_p=v_p(n)$. We have \begin{align*} \frac{1}{\sigma (n)} &= \prod_{p \text{ prime,}p\mid n} \frac{p-1}{p^{\alpha_p+1}-1} \\ &\geqslant \prod_{p \text{ prime,}p\mid n} \frac{p-1}{p^{\alpha_p+1}} \\ &= \prod_{p \text{ prime,}p\mid n} \frac{1-\frac{1}{p}}{p^{\alpha_p}} \\ &= \frac{\phi(n)}{n^2}. \end{align*}Thus, $$\frac{1}{\sigma (n)} + \frac{1}{\phi (n)} \geqslant \frac{\phi(n)}{n^2} + \frac{1}{\phi (n)} \geqslant \frac{2}{n}$$by AM-GM.
31.12.2017 14:58
small mistake in the stement it should be $n\geq m$
31.12.2017 22:42
Does this work? I tried using strong induction. The inequality is obviously true for $n = 1, 2, 3$. Now, for $n>3$, suppose the inequality is true for all positive integers $<n$: 1. If $n = p^k$, where $p$ is a prime and $k$ is a positive integer, then by AM-GM it is easy to verify that the inequality is true (like in the solution above.) 2. If $n$ is a multiple of more than 1 primes, then $\exists m,k$ \in $\mathbb{N}$, such that $n = mk$, $gcd(m,k) = 1$ and $m, k \neq 1$. We have to prove that $\frac{1}{\sigma (mk)} + \frac{1}{\phi (mk)} \geq \frac{2}{mk} \Leftrightarrow \sigma (mk) + \phi (mk) \geq \frac{2 \sigma (mk) \phi (mk)}{mk}$. But, since $\sigma$ and $\phi$ are multiplicative functions, we have that $\sigma (mk) = \sigma (m) \sigma (k)$. The same holds for $\phi$. So the inequality is equivalent to: $2(\sigma (mk) + \phi (mk)) \geq \frac{2 \sigma (m) \phi (m)}{m} \frac{2 \sigma (k) \phi (k)}{k}$. However, by the induction hypothesis, we have that: $\frac{1}{\sigma (m)} + \frac{1}{\phi (m)} \geq \frac{2}{m} \Leftrightarrow \sigma (m) + \phi (m) \geq \frac{2 \sigma (m) \phi (m)}{m}$. The same holds for $k$. As a result, $\frac{2 \sigma (m) \phi (m)}{m} \frac{2 \sigma (k) \phi (k)}{k} \leq (\sigma (m) + \phi (m))(\sigma (k) + \phi (k))$ It suffices to show that $(\sigma (m) + \phi (m))(\sigma (k) + \phi (k)) \leq 2(\sigma (mk) + \phi (mk)) \Leftrightarrow \sigma (m) \phi (k) + \sigma (k) \phi (m) \leq \sigma(m) \sigma(k) + \phi (m) \phi (k)$ $\Leftrightarrow \sigma (m) (\sigma (k) - \phi (k)) \geq \phi (m) (\sigma (k) - \phi (k))$ Obviously, $\sigma (k) > k$ and $\phi (k) < k$, so $\sigma (k) > \phi (k)$, which means that the above inequality is true so the induction step is complete. It is easy to see that the equality does not hold for powers of primes. If it were true in the second case, we would have $\sigma (k) = \phi (k) \Leftrightarrow k = 1$, a contradiction. So the equality only holds for $n = 1$
31.12.2017 23:01
Lemma: $\sigma(n)\varphi(n) \le n^2$. Proof: Let $n= \prod\limits_{i=1}^kp_i^{e_i}$. $$\sigma(n)\varphi(n) =\prod_{i=1}^k \frac{p_i^{e_i+1}-1}{p_i-1} \cdot (p_i-1)p_i^{e_i-1}\le \prod_{i=1}^k p_i^{e_i+1}\cdot p_i^{e_i-1} = n^2.$$ Then by AM-GM, $$\frac{1}{\sigma(n)} + \frac{1}{\varphi(n)}\ge \frac{2}{\sqrt{\sigma(n)\varphi(n)}} \ge \frac{2}{n}$$as desired.
20.01.2018 20:04
A bit of a pedantic note: the condition in the definition of $\varphi(n)$ is actually $m \le n$. It may seem to be the same as $n \ge m$, but in the context of the sentence, you want to consider the integers $m$, not $n$, so this ordering makes more sense. Anyway, bobthesmartypants' solution is pretty much the official one. Note that the inequality in the middle is strict when the product is nonempty, so $1$ is the only possible equality case, and is easily verified as such.
31.05.2018 14:09
Equality iff $n=1$ as $n\ge 2\implies n^2>\sigma(n)\varphi(n)$
20.06.2022 20:49
Suppose $n>1$. Then: \begin{align*} \frac1{\sigma(n)}+\frac1{\phi(n)}&=\prod_{\tau(p)=2,p\mid n}\frac{p-1}{p^{v_p(n)+1}-1}+\prod_{\tau(p)=2,p\mid n}\frac1{p^{v_p(n)-1}(p-1)}\\ &\ge2\sqrt{\prod_{\tau(p)=2,p\mid n}\frac{p-1}{p^{v_p(n)+1}-1}\cdot\frac1{p^{v_p(n)-1}(p-1)}}\\ &>2\sqrt{\prod_{\tau(p)=2,p\mid n}\frac{p-1}{p^{v_p(n)+1}}\frac1{p^{v_p(n)-1}(p-1)}}\\ &=2\sqrt{\prod_{\tau(p)=2,p\mid n}\frac1{p^{2v_p(n)}}}\\ &=2\sqrt{\frac1{n^2}}\\ &=\frac2n.\\ \end{align*}For $n=1$, equality holds.
29.08.2023 17:34
First of all let $n=\prod_{i=1}^{k}p_i^{\alpha_i}$, moreover notice that: $$\sigma(n)=\prod_{i=1}^{k}\frac{p_i^{\alpha_i+1}-1}{p_i-1}\Longrightarrow\frac{1}{\sigma(n)}=\prod_{i=1}^{k}\frac{p_i-1}{p_i^{\alpha_i-1}-1}$$$$\phi(n)=\prod_{i=1}^{k}p_i^{\alpha_i-1}(p_i-1)\Longrightarrow\frac{1}{\phi(n)}=\prod_{i=1}^{k}\frac{1}{p_i^{\alpha_i-1}(p_i-1)}$$Thus the inequality is equivalent to $\prod_{i=1}^{k}\frac{p_i-1}{p_i^{\alpha_i-1}-1}+\prod_{i=1}^{k}\frac{1}{p_i^{\alpha_i-1}(p_i-1)}\ge\frac{2}{n}$ Furthermore, notice that: $$\prod_{i=1}^{k}\frac{p_i-1}{p_i^{\alpha_i-1}-1}+\prod_{i=1}^{k}\frac{1}{p_i^{\alpha_i-1}(p_i-1)}\overset{\text{AM-GM}}{\ge}2\sqrt{\prod_{i=1}^{k}\frac{p_i-1}{p_i^{\alpha_i-1}-1}\cdot\prod_{i=1}^{k}\frac{1}{p_i^{\alpha_i-1}(p_i-1)}}=2\sqrt{\prod_{i=1}^{k}\frac{1}{(p_i^{\alpha_i+1}-1)p_i^{\alpha_i-1}}}=2\sqrt{\prod_{i=1}^{k}\frac{1}{p_i^{2\alpha_i}-p_i^{\alpha_i-1}}}>2\sqrt{\prod_{i=1}^{k}\frac{1}{p_i^{2\alpha_i}}}=2\sqrt{\frac{1}{\prod_{i=1}^{k}p_i^{2\alpha_i}}}=2\sqrt{\frac{1}{n^2}}=\frac{2}{n}$$ Therefore $\frac{1}{\sigma (n)} + \frac{1}{\phi (n)}\ge\frac{2}{n}$ with equality only at $n=1$ $\blacksquare$.