Why is $f(x) = x\phi(x)$ injective, i.e. $x\phi(x) = y\phi(y)\Rightarrow x = y$

Question

I noticed that $f(x) = x\phi(x)$ seems to be one-to-one, where $\phi(x)$ is Euler's Phi function.

In particular, I'm writing some numerical python code and the line I have looks something like

sorted([n*phi(n) for n in range(1,1000)])

and there are no duplicates in the list.

First, is it one-to-one?

Second, if it is, is there a simple proof sketch?

Answer 1

To prove that $x\phi(x)=y\phi(y)$ implies $x=y$, show that the largest prime dividing $xy$ must divide both $x$ and $y$ to the same power, then induct.

Answer 2

One can prove this by induction on the number of primes dividing $x.$

Let's begin with the case of two numbers $p^n$ and $q^m$ such $p$ and $q$ are prime and

$$p^n\phi(p^n) = q^m\phi(q^m). \mbox{ (1)}$$

Then $p$ is the largest prime dividing the left hand side of $(1)$ and $q$ is the largest prime dividing the right hand side of $(1)$. It follows $p = q.$ And so as,

$$q^m\phi(q^m) = q^{2m-1}(q-1),$$

It must be the case that $2m -1 = 2n -1.$ Hence, $n = m.$ It follows that the function $x \mapsto x\phi(x)$ is injective on the set of positive non-units divisible by at most $1$ prime.

Next assume that the function $x \mapsto x\phi(x)$ is injective on the set $S_k$ of positive non-units divisible by at most $k$ primes. Let $x,y$ be positive non-units divisible by at most $k +1$ primes such that $x\phi(x) = y\phi(y).$ Then $x = x_0p^n$ and $y= y_0q^m$ where $x_0,y_0 \in S_k,$ $p$ and $q$ are the largest primes dividing $x$ and $y,$ respectively, and $(x_0,p) = 1 =(y_0, q).$ Hence, $p$ and $q$ are the largest primes dividing $x\phi(x)$ and $y\phi(y);$ it follows $p =q.$

Hence,

\begin{align*} x_0\phi(x_0)q^{2n -1}(q-1) & = x_0\phi(x_0)q^n\phi(q^n) \\&= x_0q^n\phi(x_0q^n) \\&= x\phi(x) \\&= y\phi(y) \\&= y_0\phi(y_0)q^{2m -1}(q-1). \end{align*}

As any prime dividing $x_0$ or $y_0$ is strictly less than $q,$ the prime $q$ does not divide $x_0\phi(x_0)$ or $y_0\phi(y_0).$ It follows that the exponent of $q$ on both sides of the equality is $2m -1 = 2n -1.$ Hence, $n = m.$ Dividing both sides by $q^n\phi(q^n).$ We obtain $x_0\phi(x_0) = y_0\phi(y_0)$ which implies $x_0 = y_0$ by the induction hypothesis. It follows

$$x = x_0p^n = y_0q^m = y,$$

and the claim follows by induction.

Answer 3

Let $x, y$ be integers $ > 1 $ such that $ x \varphi(x) = y \varphi(y) $. We'll try to show $ x = y $.

Let's write the prime factorisations of $ x, y $ as $ x = p_1 ^{\alpha_1} \ldots p_k ^{\alpha_k} $ $ ( p_1 < \ldots < p_k ; \text{ each } \alpha_i > 0 ) $, and $ y = q_1 ^{\beta_1} \ldots q_l ^{\beta_l} $ $ ( q_1 < \ldots < q_l ; \text{ each } \beta_j > 0 ) $. Now $ x\varphi(x) = y\varphi(y) $ becomes $ ( p_1 ^{\alpha_1} \varphi(p_1 ^{\alpha_1}) ) \ldots ( p_k ^{\alpha_k} \varphi(p_k ^{\alpha_k}) ) $ $ = ( q_1 ^{\beta_1} \varphi(q_1 ^{\beta_1}) ) \ldots ( q_l ^{\beta_l} \varphi(q_l ^{\beta_l}) ) $.

Now notice the exponent of $ p_k $ in the prime factorisation of LHS is $ \alpha_k + ( \alpha_k - 1 ) $ $ = 2 \alpha_k - 1 $ [ Because for $ i < k $ neither $ p_i ^{\alpha_i} $ nor $ \varphi(p_i ^{\alpha_i}) ( = p_i ^{\alpha_i - 1} (p_i - 1)) $ carries a prime factor $ p_k $, we need only consider $ p_k ^{\alpha_k} \varphi(p_k ^{\alpha_k}) $, which gives exponent $ 2 \alpha_k - 1 $ ]. Similarly the exponent of $ q_l $ in the prime factorisation of RHS is $ 2 \beta_l - 1 $.

Looking at LHS = RHS and using uniqueness of prime factorisation, we get $ \{ p_k = q_l ; \, 2 \alpha_k - 1 = 2 \beta_l - 1 \} $, i.e. $ \{ p_k = q_l ; \, \alpha_k = \beta_l \} $. So we can cancel $ p_k ^{\alpha_k} \varphi(p_k ^{\alpha_k}) $ in LHS with $ q_l ^{\beta_l} \varphi(q_l ^{\beta_l}) $ in RHS, and now continuing similarly onto the remaining factors gives $ \{ l=k; p_k = q_l, \alpha_k = \beta_l ; $ $ \ldots ; p_1 = q_1, \alpha_1 = \beta_1 \} $, i.e. that $ x = y $, as needed.