0
$\begingroup$

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

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

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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