Problem. Show that if $ n \not \in \mathbb{P} \cup \{1\}$ and $ \varphi(n) \mid n - 1$ then $ \sigma_1(n) > 2009$. Solution. Since $ 2 \mid \varphi(n)$ for all $ n \in \mathbb{N} \setminus \{0,1,2\}$ then it is true that $ \text{lpf}(n) > 2$. Again we have that $ \mu(n)^2 = 1$ since otherwise we'll have that $ p^2 \mid n$ for some $ p \in \mathbb{P}$ and $ p \mid \varphi(n) \mid n - 1$, that is a contradiction. Now the chain of inequalities $ 2^{11} > 2009 \ge \sigma_1(n) \ge 12^{\omega(n) - 3} \cdot 8 \cdot 6 \cdot 4 = 2^{2\omega(n)}3^{\omega(n) - 2} \ge 2^{\frac {7}{2}\omega(n) - 3}$ holds. It implies that $ \omega(n) \in \{2,3\}$. If $ \omega(n) = 2$ then there exist $ (p,q) \in \mathbb{P}^2$ such that $ p > q > 2$ and $ \frac {pq - 1}{(p - 1)(q - 1)} \in \mathbb{Z}$, but $ 1 = \frac {(p - 1)(q - 1)}{(p - 1)(q - 1)} < \frac {p(q - 1)}{(p - 1)(q - 1)} <$ $ \frac {pq - 1}{(p - 1)(q - 1)} < \frac {p}{p - 1}\frac {q}{q - 1} \le \frac {3 \cdot 5}{2 \cdot 4} < 2$, that is a contradiction. It remains the last case $ \omega(n) = 3$ that is false at the same way (for example see the easy and more general one IMO1992/1).[] Additional Note. This question is related to a famous unsolved problem in number theory, the Lehmer conjecture (i.e. it does not exist a positive composite integer $ n > 1$ such that $ \varphi(n) \mid n - 1$). It was first posed in 1932, and since then some progress was made, e.g. defining $ S: = \{n \in \mathbb{N} \setminus \left(\mathbb{P} \cup \{0,1\}\right): \varphi(n) \mid n - 1\}$ then $ |S \cap [1,x]| = O\left(x^{\frac {1}{2}}(\ln(x))^{\frac {3}{4}}\right)$ ( see here for a proof by Carl Pomerance ). For a more advanced lecture, you can also see here where it is proved that $ |S \cap [1,x]| = O\left(x^{\frac {1}{2}} (\ln(\ln(x)))^{\frac {3}{2} + e}(\ln(x))^{ - c}\right)$ for all $ e > 0$ and where $ c = 0,129398..$ is a fixed constant .