Find a number $n \neq 2017$ such that $\phi(n) = \phi(2017)$, as above. I know the formula for a general $\phi$ function, but I cannot see how this is helpful here. Any help would be appreciated!

  • $\begingroup$ You could work out $\phi(2017)$ for a start? $\endgroup$ May 24 '20 at 4:47
  • $\begingroup$ @AnginaSeng Yes, I think I can figure this out, but I'm quite stuck after here.. $\endgroup$
    – RnHdw
    May 24 '20 at 4:48
  • $\begingroup$ if $p$ is odd then $\phi(2p)=\phi(2)\phi(p)=\phi(p)$ $\endgroup$
    – Kat
    May 24 '20 at 4:52

Hint: $2017$ is a prime number.

Solution: Fortunately, the totient function $\phi$ has the nice property that $\phi(p) = \phi(2p)$, where $p$ is prime. This is because $2p$ is relatively prime to all odd numbers less than it except $p$. There are $p$ even numbers less than $2p$, and discounting the fact that $\gcd(p, 2p) \neq 1$, we see that $$\phi(2p) = p - 1 = \phi(p)$$ You could have alternatively seen this from the multiplicative property of $\phi$, namely that $\phi(mn) = \phi(m)\phi(n)$. Hence, $\phi(4034) = \phi(2017)$, because $\phi(2) = 1$.

  • $\begingroup$ Thank you, I think I see that. So $\phi(2017) = 2016$. How does this fact help answering this question? $\endgroup$
    – RnHdw
    May 24 '20 at 4:47
  • $\begingroup$ @RnHdw See my edits. $\endgroup$
    – paulinho
    May 24 '20 at 4:56
  • 1
    $\begingroup$ I saw that $2017$ is prime but didn't think of $4034.$ I found $\phi(29\cdot 73)=(28)(72)=(2^5)(7)(9)=2016.$ $\endgroup$ May 24 '20 at 10:41

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.