He resuelto, pero estoy interesado a ver si hay otra manera, porque la mía es asistida por ordenador. Utilizando el hecho de que si $p \mid n$$ p-1 \mid \phi(n) $, creo que el conjunto de divisores de 123456789: $$1,3, 9, 3607, 3803, 10821, 11409, 32463, 34227, 13717421, 41152263, 123456789$$ From this set only $1+1$ is prime, so $n = 2^$. But $\phi( 2^a ) = 2^{a-1}$, but $123456789$ is not even, therefore such $$ n no existe.
He utilizado una secuencia de comandos para encontrar los divisores, me pregunto si hay un no demasiado complicado para conseguir el mismo resultado sin "externo" de la ayuda. Gracias!
EDICIÓN: Editado mi prueba, me olvidé $\phi$ no es completamente multiplicativa.