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

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

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

• This stands true in case the same primes divide m and n – naveen dankal Sep 11 '16 at 7:27

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