Maths Olympiad Prep

Library / /275 of 520

Number theory Difficulty 6.1 National olympiad Prove it

8. Let x1x \geqslant 1. Prove:
(i) nxφ(n)=12nxμ(n)[xn]2+12\sum_{n \leqslant x} \varphi(n)=\frac{1}{2} \sum_{n \leqslant x} \mu(n)\left[\frac{x}{n}\right]^{2}+\frac{1}{2};
(ii) nxφ(n)n=nxμ(n)n[xn]\sum_{n \leq x} \frac{\varphi(n)}{n}=\sum_{n \leq x} \frac{\mu(n)}{n}\left[\frac{x}{n}\right].

Solution

8. (i) Using the lower formula of (30) and formula (36); (ii) immediately deduce from φ(n)=ndnμ(d)/d\varphi(n)=n \sum_{d \mid n} \mu(d) / d.

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.