10
$\begingroup$

If I am not mistaken here in OEIS says that

$n\cdot \phi(n)=m\cdot \phi(m)$ is possible only if $n=m$.

$\phi(n)$ denotes Euler's totient function.

Is there a proof of this fact?

$\endgroup$
  • $\begingroup$ Yes, there is. The linked Luca & Munagi paper has it as part of Theorem 2 on page 3. $\endgroup$ – Lisa Nov 17 '15 at 23:13
  • 1
    $\begingroup$ @Lisa I don't understand. The only related fact I can find in that paper is that $a(n,n) = n \phi(n)$. Is $a(n,n)$ easily shown to never take the same value twice? $\endgroup$ – A.P. Nov 18 '15 at 0:07
  • $\begingroup$ $\phi(n)/n$ is injective as well. $\endgroup$ – lhf Nov 19 '15 at 12:23
8
$\begingroup$

Suppose $n$ is the smallest number such that a number $m\ne n$ exists with

$$n\ \phi(n)=m\ \phi(m)$$

Let $p$ be the largest prime factor of $n$ and $q$ be the largest prime factor of $m$. Then, $p<q$ is impossible because $n\ \phi(n)$ would not be divisivle by $q$. $p>q$ is impossible because $m\ \phi(m)$ would not be divisible by $p$. So, we have $p=q$.

The valuation of $p$ in $n\ \phi(n)$ is uniquely determined by the valuation of $p$ in $n$, so the valuations of $p$ in $n\ \phi(n)$ and $m\ \phi(m)$ must coincide.

Therefore we have $\frac{n}{p}\phi(\frac{n}{p})=\frac{m}{p}\phi(\frac{m}{p})$

contradicting the assumption that $n$ is the smallest number, such that an $m$ exists with $n\ \phi(n)=m\ \phi(m)$.

Hence $n=1$, but $1=m\ \phi(m)$ has the only solution $m=1$.

$\endgroup$
  • 1
    $\begingroup$ You might consider submitting this proof to the OEIS sequence mentioned in the question! $\endgroup$ – Charles Nov 18 '15 at 0:45
  • $\begingroup$ I feel very stupid, but if $p<q$, I see that $q$ cannot divide $n$. But why can't it divide $\phi(n)$? $\endgroup$ – Jason DeVito May 19 '18 at 14:29
  • $\begingroup$ @JasonDeVito The prime factors of $\phi(n)$ cannot exceed the largest prime factor of $n$ $\endgroup$ – Peter May 19 '18 at 18:11

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.