3 Distinct proofs on lower bound of Euler's totient function

Definition.

\(\phi(n)\) : Number of natural numbers in \(1..n\), which are relatively prime to \(n\).

\(\sigma(n)\) : Sum of divisors of \(n\), including \(1\) and \(n\) itself.

claim.

$$n > 1 \Rightarrow \phi(n) > \frac{n}{4\log n}$$

---

This section is intentionally left blank.

Special thanks: H. Cho, W. Song.

---

Solution 1. (Official)

\(n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}\).

$$ \phi(n) = n \prod_{i = 1}^{k} \left( 1 - \frac{1}{p_{i}} \right) = n \left( 1 - \frac{1}{p_{1}} \right) \cdots \left( 1 - \frac{1}{p_{k}} \right) $$

$$ = n \frac{\color{red}{ \prod_{i = 1}^{k} \left( 1 - \frac{1}{p_{i}^2} \right)}}{\color{blue}{ \prod_{i = 1}^{k} \left( 1 + \frac{1}{p_{i}} \right)}} > n\frac{\color{red}{ \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k^2} \right) }}{\color{blue}{ \prod_{i = 1}^{k} \left( 1 + \frac{1}{p_{i}} \right) }} $$

By expanding blue term, we acquire the sum of reciprocal of distinct integers. ( \(\because \forall p_{i}\) are distinct )

Hence, the blue term is less than \(\color{blue}{1 + \frac{1}{2} + \cdots \frac{1}{n}} \), which is definitely smaller than \( \color{blue}{1 + \log n < 2\log n} \).  \(( \because \prod p_{i} \le n )\)

The red term can be reduced by the following telescoping step.

$$ \color{red}{ \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k^2} \right) = \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k} \right)\left( 1 + \frac{1}{k} \right) = \frac{1}{2} } $$

Therefore,

$$ \phi(n) > n\frac{\color{red}{ \prod_{k = 2}^{\infty} \left( 1 - \frac{1}{k^2} \right) }}{\color{blue}{ \prod_{i = 1}^{k} \left( 1 + \frac{1}{p_{i}} \right) }} > n\frac{\color{red}{1/2}}{\color{blue}{2\log n}} = \frac{n}{4\log n} \blacksquare $$

Solution 2. (TAMREF. Yun.)

\(n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}\).

Lemma. \(\sigma(n) < n ( 1 + \log n )\).

pf) $$\sigma(n) = \sum_{d | n} d = \sum_{d | n} \frac{n}{d} = n \sum_{d |n } \frac{1}{d} \le n \sum_{d \le n} \frac{1}{d} \le n (1 + \log n). \blacksquare$$

$$ \frac{\phi (n) \sigma(n)}{n} = \prod_{i = 1}^{k} \left( 1 - \frac{1}{p_i} \right) \cdot \frac{p_{i}^{e_{i}+1}-1}{p_{i}-1} = \prod_{i = 1}^{k} \frac{p_{i}^{e_{i} + 1} - 1}{p_{i}} = \prod_{i = 1}^{k} \left( p_{i}^{e_{i}} - \frac{1}{p_{i}} \right) $$

$$ = \prod_{i = 1}^{k} \color{red}{p_{i}^{e_{i}}} \left(1 - \frac{1}{p_{i}^{e_{i}+1}}\right)= \color{red}{n} \prod_{i=1}^{k} \left( 1 - \color{blue}{\frac{1}{p_{i}^{e_{i}+1}}} \right) \ge n \prod_{i=1}^{k} \left( 1 - \color{blue}{\frac{1}{p_{i}^{2}}} \right)$$

Since \((1-x_{1})(1-x_{2})\cdots (1-x_{n}) > 1-x_{1}-x_{2}-\cdots x_{n}\) for \(x_{i} < 1\),

$$ \frac{\phi (n) \sigma (n)}{n} \ge n \prod_{i=1}^{k} \left( 1 - \frac{1}{p_{i}^{2}} \right) > n \left( 1 - \sum_{i=1}^{k} \frac{1}{p_{i}^2} \right) > n \left( 1 - \sum_{p} \frac{1}{p^2} \right) $$

From the following inequality (we can tighten the bound up to \(0.4522\) by googling) and the Lemma,

$$ \sum_{p} \frac{1}{p^2} < \sum_{k \text{ : odd}} \frac{1}{k^2} + \frac{1}{2^2} - \frac{1}{1^2} = \frac{3}{4}\zeta (2) - \frac{3}{4} = \frac{\pi^2}{8} - \frac{3}{4} \sim 0.4837 $$ 

$$ \phi(n) > \frac{n^2 \cdot (1-0.4837)}{\sigma(n)} > \frac{0.5162n}{(1+\log n)} > \frac{0.2581n}{\log n} > \frac{n}{4\log n}. \blacksquare $$

Solution 3. (Hatalova, Salat)

\(n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k} \quad (p_1 < p_2 < \cdots p_k) \).

claim) \(4\log n > \frac{n}{\phi(n)} = \prod_{i=1}^{k} \frac{p_{i}}{p_{i}-1}\)

pf.

$$4\log n \ge 4(\log p_1 + \log p_2 + \cdots \log p_k) \ge 4k\log 2 \ge 2\log 2 (k + 1) = (2\log 2) \frac{2}{1} \cdot \frac{3}{2} \cdots \frac{k+1}{k}$$

Since \(p_k \ge k+1\) and \(f(x) = \frac{x}{x-1}\) is decreasing on \(x > 1\), the inequality \(\frac{i+1}{i} \ge \frac{p_{i}}{p_{i}-1}\) holds.

$$ \therefore 4\log n \ge 2\log 2 \prod_{i=1}^{k} \frac{i+1}{i} \ge 2\log 2 \prod_{i=1}^{k} \frac{p_{i}}{p_{i}-1} = 2\log 2 \frac{n}{\phi(n)} \gtrsim \frac{1.39n}{\phi(n)} $$

$$ \therefore \phi(n) \ge \frac{1.39n}{4\log n} > 0.346\frac{n}{\log n} > \frac{n}{4\log n} \blacksquare $$