6

Let $f: \mathbb{N} \to \mathbb{N}$ defined by

$$f(n) = n \varphi(n),$$

where $\varphi(n)$ is the Euler Totient function.

Prove that f is injective.

Ehsan M. Kermani
  • 9,228
Prithviraj Chowdhury
  • 71
  • 1
    Not sure if this helps, but $n\phi(n)=\phi(n^2)$... – Thomas Andrews Oct 25 '13 at 18:10
  • Yes,I did try to accomplish something with that,but couldn't. Thank you,nonetheless. I'll see if i can make anything of it. – Prithviraj Chowdhury Oct 25 '13 at 18:15
  • I noticed that this is tricky because of the prime decompositions of $n_1$ and $n_2$...noting what Thomas Andrews helps, but wouldn't $n_1$'s prime decomposition be $p_1^{k_1}...p_{m_1}^{k_{m_1}}$ and $n_2$'s would be $p_1^{k_1}...p_{m_2}^{k_{m_2}}$? – Eleven-Eleven Oct 25 '13 at 18:35
  • 2
    Hello, welcome to Math.SE. Thank you for your question! It is good practice on this site to add a bit of information on the context your question came up in, and to share your own work on it. It's also fine if you state that you're completely lost -- the information is helpful for answerers to gauge their answer on. For more information on asking a good question on this site, see here. – Lord_Farin Oct 25 '13 at 18:35
  • Duplicate of http://math.stackexchange.com/questions/68120/why-is-fx-x-phix-one-to-one. – lhf Oct 28 '13 at 12:44

1 Answers1

8

It helps that $f$ is a multiplicative function.

Suppose that $f(n_1) = f(n_2)$. Let $p$ be the largest prime factor of $n_1$ (the case $n_1 = 1$ is trivial), and let $p^k$ be the highest power of $p$ dividing $n_1$. Then $p^{2k-1} \mid f(n_1)$, and $p^{2k} \nmid f(n_1)$. Further, $p$ is the largest prime factor of $f(n_1)$. Thus $p$ is also the largest prime factor of $f(n_2)$, hence of $n_2$, and $p^k \mid n_2$, $p^{k+1}\nmid n_2$.

Thus, by the multiplicativity of $f$, we also have

$$f\left(\frac{n_1}{p^k}\right) = f\left(\frac{n_2}{p^k}\right).$$

Continuing, after having eliminated all prime factors of $n_1$, we have

$$f(1) = f\left(\frac{n_2}{n_1}\right),$$

hence $\frac{n_2}{n_1} = 1$, or $n_2 = n_1$.

Daniel Fischer
  • 206,697