Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
2  
$n\phi(n) = \phi(n^2)$, which might help. –  Michael Lugo Sep 28 '11 at 4:22
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. –  Greg Martin Sep 28 '11 at 4:43
show 1 more comment

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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