Possible Duplicate:
Why is $f(x) = x\phi(x)$ one-to-one?

How would one show $x \phi (x) = y\phi (y)$ implies $x=y$, where $\phi$ is the Euler totient function?

I have thought of the obvious method of writing $x$ and $y$ in their prime factorization:

$x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ (primes arranged in ascending order)

$y=q_1^{b_1}q_2^{b_2}\cdots q_l^{b_l}$ (primes arranged in ascending order)

Then, $x \phi (x)=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}(p_1^{a_1}-p_1^{a_1-1})(p_2^{a_2}-p_2^{a_2-2})\cdots (p_k^{a_k}-p_k^{a_k-1})$

$y \phi (y)=q_1^{b_1}q_2^{b_2}\cdots q_k^{b_k}(q_1^{b_1}-q_1^{b_1-1})(q_2^{b_2}-q_2^{b_2-2})\cdots (q_l^{b_l}-q_l^{b_l-1})$

A hint in the book told us to prove that $p_k^{a_k}$ divides $y$. However, I do not have any idea how to do that. Also, even if I managed to prove that, I don't see how that may lead to the final result.

Sincere thanks for any help!


marked as duplicate by JavaMan, Hagen von Eitzen, user17762, rschwieb, martini Nov 7 '12 at 19:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Not sure, but $x\phi(x) = \phi(x^2)$ $\endgroup$ – Thomas Andrews Nov 7 '12 at 16:49
  • 2
    $\begingroup$ I would advise factoring your expression for $x \phi(x)$ a bit more, and thinking about where the largest prime factor might be. $\endgroup$ – Erick Wong Nov 7 '12 at 16:51

Here is a general sketch of how to proceed. Your equation is expressible as $$x^2\prod_{p_i}\left(1-\frac{1}{p_i}\right) = y^2\prod_{q_i}\left(1-\frac{1}{q_i}\right)$$ If you clear denominators and cancel a few things, then you end up with $$\left(\prod_{p_i}p_i^{2a_i - 1}\right)\left(\prod_{p_i}(p_i-1)\right)=\left(\prod_{q_i}q_i^{2b_i - 1}\right)\left(\prod_{q_i}(q_i-1)\right)$$ Show that the largest prime factor in the two expressions occurs in $$\left(\prod_{p_i}p_i^{2a_i - 1}\right)\ \ \text{and}\ \ \left(\prod_{q_i}q_i^{2b_i - 1}\right)$$ respectively. This allows you to conclude that the largest prime factor of $x$ and $y$ are equal. The result follows inductively.


Not the answer you're looking for? Browse other questions tagged or ask your own question.