Proof involving Euler's phi function: if $m\phi(m)=n\phi(n)$ then $m=n$

Question

How do you prove that if $m\phi(m)=n\phi(n)$ then $m=n$?

Here, $\phi$ is the Euler Phi function.

Answer 1

Hint. Assume that $n\phi(n)=m\phi(m)$. Let $p$ be the largest prime factor of $n$ and let $p^k$ be the highest power of $p$ dividing $n$. Since $\phi(n)=\prod_{p^k \| n} p^{k-1} (p-1)$ it follows that $p^{2k-1}$ is the highest power of $p$ dividing $n\phi(n)$. Now, $p$ is the largest prime factor of $n\phi(n)$ which implies that $p$ is also the largest prime factor of $m\phi(m)$, hence of $m$, and $p^k$ is also the highest power of $p$ dividing $m$.

Therefore $n_1\phi(n_1)=m_1\phi(m_1)$ where $n_1=n/p^k$ and $m_1=m/p^k$.

Answer 2

We can prove this by strong induction on $(m,n)$.

First consider a base case where $m = 1$ (or $n = 1$). Then $n \phi(n) = 1$, so $n = 1$.

Now for the induction step, suppose that $m\phi(m) = n\phi(n)$, and that the result is true for all $m' < m$, $n' < n$. Let $p$ be the largest prime dividing $mn$. Let $m = p^i m'$ and $n = p^j n'$, where $p$ does not divide $m'$ and $n'$. Since $\phi$ is multiplicative, $$ m \phi(m) = p^i m' \phi(p^i m') = p^i \phi(p^i) m' \phi(m') $$ Similarly for $n \phi(n)$, and thus $$ p^i \phi(p^i) m' \phi(m') = p^j \phi(p^j) n' \phi(n'). $$ Now, $p$ does not divide either $\phi(m')$ or $\phi(n')$, because $m'$ and $n'$ have only primes less than $p$ (since we chose $p$ to be the highest prime dividing $mn$). It also cannot be that $i = 0$ or that $j = 0$, as then $p$ would divide one side but not the other. Therefore, $\phi(p^i) = p^{i-1} (p-1)$ and $\phi(p^j) = p^{j-1} (p-1)$; we get $$ p^{2i-1} (p-1) m' \phi(m') = p^{2j-1} (p-1) n' \phi(n') $$ By considering the number of factors of $p$ on each side, $i = j$, and thus, dividing, $$ m' \phi(m') = n' \phi(n'). $$ By induction hypothesis, $m' = n'$. Since $i = j$ and $m' = n'$, $m = p^i m' = p^j n' = n$, and we are done.