## N1.

Find all natural numbers $n$ for which $1^{\phi(n)}+2^{\phi(n)}+\ldots+n^{\phi(n)}$ is coprime with $n$.


Solution. Consider the given expression $(\bmod p)$ where $p \mid n$ is a prime number. $p|n \Rightarrow p-1| \phi(n)$, thus for any $k$ that is not divisible by $p$, one has $k^{\phi(n)} \equiv 1(\bmod p)$. There are $n-\frac{n}{p}$ numbers among $1,2, \ldots, n$ that are not divisible by $p$. Therefore

$$
1^{\phi(n)}+2^{\phi(n)}+\ldots+n^{\phi(n)} \equiv-\frac{n}{p} \quad(\bmod p)
$$

If the given expression is coprime with $n$, it is not divisible by $p$, so $p \nmid \frac{n}{p} \Rightarrow p^{2} \backslash n$. This is valid for all prime divisors $p$ of $n$, thus $n$ must be square-free. On the other hand, if $n$ is square-free, one has

$p^{2} \Varangle n \Rightarrow p \nmid \frac{n}{p}$, hence the given expression is not divisible by $p$. Since this is valid for all prime divisors $p$ of $n$, the given two numbers are indeed coprime.

The answer is square-free integers.
