Problem 1598

Solution:
Let's prove the statement by induction.

The base case $n=1$ is trivial.

Let's prove the inductive step. Given that $1^{1}, 3^{3}, 5^{5}, \ldots,\left(2^{n}-1\right)^{2^{n}-1}$ have different residues $(\bmod\ 2^{n})$, we want to show that $1^{1}, 3^{3}, 5^{5}, \ldots,\left(2^{n+1}-1\right)^{2^{n+1}-1}$ give different results mod $2^{n+1}$.

Let's split the $2^{n}$ elements in two sets $A$ and $B$, where
$$A=\left\{1^{1}, 3^{3}, 5^{5}, \ldots,\left(2^{n}-1\right)^{2^{n}-1}\right\}$$
and
$$B=\left\{\left(2^{n}+1\right)^{2^{n}+1},\left(2^{n}+3\right)^{2^{n}+3},\left(2^{n}+5\right)^{2^{n}+5}, \ldots,\left(2^{n}+\left(2^{n}-1\right)\right)^{2^{n}+\left(2^{n}-1\right)}\right\}.$$

Let's closely examine the elements in $B \bmod 2^{n+1}$. By Euler-Fermat (we can use it in this case because $\operatorname{gcd}\left(2^{n}+k, 2^{n+1}\right)=1$) and the binomial expansion, we have:
$$\left(2^{n}+k\right)^{2^{n}+k} \equiv \left(2^{n}+k\right)^{k} \equiv \sum_{s=0}^{k}\binom{k}{s} \cdot 2^{n s} \cdot k^{k-s} \equiv 2^{n} \cdot k^{k}+k^{k} \equiv 2^{n}+k^{k} \quad\left(\bmod 2^{n+1}\right)$$

In other words,
$$B \equiv \left\{1^{1}+2^{n}, 3^{3}+2^{n}, 5^{5}+2^{n}, \ldots,\left(2^{n}-1\right)^{2^{n}-1}+2^{n}\right\}\ (\bmod\ 2^{n+1})$$

Now, by the inductive hypothesis, the elements in $A$ are distinct $(\bmod\ 2^{n})$ and so are the elements in $B$. Finally, since the elements in $B\ (\bmod\ 2^{n+1})$ are simply obtained by adding $2^{n}$ to the elements in $A$, the $2^{n}$ numbers give different remainders $(\bmod\ 2^{n+1})$, concluding the inductive step.

Hence, the initial statement is true for all $n \in \mathbb{N}$.