16
$\begingroup$

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?

  • 0
    Is $\phi(x)$ Euler's totient function?2011-09-28
  • 0
    Yes, sorry. I will add that.2011-09-28
  • 0
    Interesting question! I think I recall it is true2011-09-28
  • 2
    $n\phi(n) = \phi(n^2)$, which might help.2011-09-28
  • 1
    @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.2011-09-28
  • 0
    @Greg: Ah, I see you're correct. I was remembering that $\mathbb{Q}(\zeta_a)\cong\mathbb{Q}(\zeta_b)$ only under those conditions, but clearly that is stronger than $\phi(a)=\phi(b)$.2011-09-28

2 Answers 2

11

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.

  • 0
    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.2011-09-28
  • 0
    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.2011-09-29
8

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.