I've solved it, but I'm interested to see if there is another way, because mine is computer assisted. Using the fact that if $p \mid n$ then $ p-1 \mid \phi(n) $, I find the set of divisors for 123456789: $$1,3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421, 41152263, 123456789$$ From this set only $1+1$ is prime, so $n = 2^a$. But $\phi( 2^a ) = 2^{a-1}$, but $123456789$ is not even, therefore such $n$ does not exist.

I used a script to find the divisors, I'm wondering if there is a not too complicated way to get the same result without "external" help. Thanks!

EDIT: Edited my proof, I forgot $\phi$ is not completely multiplicative.


$\phi(n)$ is even for $n\ge 3$, and obviously $\phi(1),\phi(2) \neq 123456789.$

  • 2
    $\begingroup$ Well that was simple, that property is quite handy, thanks! $\endgroup$ – Xsy Apr 20 '15 at 12:43
  • 1
    $\begingroup$ Indeed, $\phi(n)$ is even for $n>2$. $\endgroup$ – Gerry Myerson Apr 20 '15 at 13:04

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.