Find all natural numbers $n$ for which $1^{\phi (n)} + 2^{\phi (n)} +... + n^{\phi (n)}$ is coprime with $n$.
Source: Balkan BMO Shortlist 2016 N1
Tags: coprime, phi function, number theory
Find all natural numbers $n$ for which $1^{\phi (n)} + 2^{\phi (n)} +... + n^{\phi (n)}$ is coprime with $n$.