Competition problem — Number theory

Library / /267 of 520

Number theory Difficulty 6.1 National olympiad Prove it

3. Prove: (i) $\varphi(m n)=(m, n) \varphi([m, n])$ ;
(ii) $\varphi(m n) \varphi((m, n))=(m, n) \varphi(m) \varphi(n)$ ;
(iii) When $(m, n)>1$ , then $\varphi(m n)>\varphi(m) \varphi(n)$ .

Solution

3. (i) By Theorem 1 (i). $[m, n]$ and $m n$ have the same prime factors. (ii) Using formula (5) of Theorem 1. (ii) 1 (

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.