Competition problem — Number theory

Library / /175 of 520

Number theory Difficulty 5.9 AIME, harder Prove it

8. Let $n>1, f(n)$ denote the sum of all positive integers not exceeding $n$ and coprime with $n$ . Prove: If $f(n)=f(m)$ , then $m=n$ .

Solution

8. We need to deduce $m=n$ from $m \varphi(m)=n \varphi(n)$ . Let $m=p_{1}^{a_{1}} \cdots p_{r_{r}^{r}}^{\varepsilon}, n=p_{1}^{\sigma_{1}} \cdots p_{r}^{\beta}, p_{1}>$ $p_{2}>\cdots>p_{r}$ , and use equation (5) to prove sequentially: $\alpha_{1}=\beta_{1}, \alpha_{2}=\beta_{2}, \cdots$ .

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.