Maths Olympiad Prep

Library / /402 of 520

Number theory Difficulty 6.6 National olympiad Prove it

9. (i) Prove: When n⩾2n \geqslant 2, σ(n)/n<n/φ(n)<(π2/6)σ(n)/n\sigma(n) / n < n / \varphi(n) < \left(\pi^{2} / 6\right) \sigma(n) / n;
(ii) There exists a positive constant AA, such that ∑n⩽xnφ(n)⩽Ax,x⩾1\sum_{n \leqslant x} \frac{n}{\varphi(n)} \leqslant A x, x \geqslant 1;
(iii) There exists a positive constant BB, such that ∑n⩽x1φ(n)⩽Bln⁡x,x⩾2\sum_{n \leqslant x} \frac{1}{\varphi(n)} \leqslant B \ln x, x \geqslant 2.

Solution

9. (i) σ(n)=∏p∣n(pa+1−1)/(p−1),n2φ(n)=n∏p∣npp−1\sigma(n)=\prod_{p \mid n}\left(p^{a+1}-1\right) /(p-1), \frac{n^{2}}{\varphi(n)}=n \prod_{p \mid n} \frac{p}{p-1}. Therefore,
n2/(σ(n)φ(n))=∏ρ∣n(1−1/pα+1);n^{2} /(\sigma(n) \varphi(n))=\prod_{\rho \mid n}\left(1-1 / p^{\alpha+1}\right) ;
(ii) Follows from (i) and part (ii) of problem 7;
(iii) Follows from (i) and part (ii) of problem 7.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.