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
    @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
    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.