# Solve $\phi(n) = 123456789$ or prove there is no such $n$

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.$
• Indeed, $\phi(n)$ is even for $n>2$. – Gerry Myerson Apr 20 '15 at 13:04