# Why is $f(x) = x\phi(x)$ one-to-one?

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?

-
Is $\phi(x)$ Euler's totient function? –  Juan S Sep 28 '11 at 3:48
Yes, sorry. I will add that. –  James Sep 28 '11 at 3:51
Interesting question! I think I recall it is true –  Juan S Sep 28 '11 at 4:01
$n\phi(n) = \phi(n^2)$, which might help. –  Michael Lugo Sep 28 '11 at 4:22
@ZevChonoles: That's not correct: for example, $\phi(3)=\phi(4)=\phi(6)=2$; and the 31 numbers 241, 287, 305, 325, 369, 385, 429, 465, 482, 488, 495, 496, 525, 572, 574, 610, 616, 620, 650, 700, 732, 738, 744, 770, 792, 858, 900, 924, 930, 990, 1050 all have 240 as their $\phi$-value. –  Greg Martin Sep 28 '11 at 4:43

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.

-
I get that if I could show that if p divides $xy$ then the largest $p^a$ that divides $x$ divides $y$ with the same power, that would imply $x=y$, but I don't see an obvious way to do this. –  James Sep 28 '11 at 7:00
It's important in my suggested approach that we work with the largest prime $p$ dividing $xy$. In this case, $p$ cannot divide $\phi(x)$ or $\phi(y)$; hence the power of $p$ dividing $x$ and $y$ must be the same. –  Greg Martin Sep 29 '11 at 23:38

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.

-