IMO Team Selection Test 2

We proceed by induction on $n$. For $n=1$, the only number in the sequence is $1^1$, so the given statement is trivially true.

For the induction step, we are to show that for $n\ge 1$, the numbers $1^1,3^3,5^5,\dots ,(2^{n+1}-1{)}^{2^{n+1}-1}$ are in different residue classes modulo $2^{n+1}$, given the induction hypothesis that $1^1,3^3,5^5,\dots ,(2^n-1{)}^{2^n-1}$ are in different residue classes modulo $2^n$.

So suppose that that is the case. We split the numbers $1^1,3^3,5^5,\dots ,(2^{n+1}-1{)}^{2^{n+1}-1}$ into two groups, namely $1^1,3^3,5^5,\dots ,(2^n-1{)}^{2^n-1}$, which we will call the lesser group, and $(2^n+1{)}^{2^n+1},(2^n+3{)}^{2^n+3},\dots ,(2^{n+1}-1{)}^{2^{n+1}-1}$, which we will call the greater group. First note that the numbers in the lesser group are also all in different residue classes modulo $2^{n+1}$.

Note that because $\phi (2^{n+1})=2^n$, we have $a^k\equiv a^{\ell }(\mathrm{mod}{2}^{n+1})$ for $k,\ell ,a$ such that $k\equiv \ell (\mathrm{mod}{2}^n)$ and $a$ is odd. We will use this observation to compare the residue classes of the greater group to those of the lesser group.

Write the numbers in the greater group as $(2^n+m{)}^{2^n+m}$ for $1\le m\le 2^n-1$ and odd. Expanding $(2^n+m{)}^{2^n+m}$ using Newton's binomial, we note that any term with at least two factors $2^n$ is congruent to $0$ modulo $2^{n+1}$. We thus find modulo $2^{n+1}$ that $$\begin{array}{rl}(2^n+m{)}^{2^n+m}& \equiv m^{2^n+m}+(2^n+m)m^{2^n+m-1}{2}^n+2^{2n}(\cdots )\\ & \equiv m^{2^n+m}+(2^n+m)m^{2^n+m-1}{2}^n\\ & \equiv m^m+(2^{2n}+2^m)m^{m-1}\\ & \equiv m^m+2^n\cdot m^m\\ & \equiv m^m+2^n,\end{array}\text{\hspace{1em}(7)}$$ where we have used in the last step that $m^m$ is odd; writing $m^m$ as $2a+1$ shows that $2^n(2a+1)=2^{n+1}a+2^n\equiv 2^n(\mathrm{mod}{2}^{n+1})$.

Since the numbers $m^m$ from the lesser group are different modulo $2^{n+1}$, the numbers from the greater group therefore are also different modulo $2^{n+1}$. Moreover, from (7) it follows that the numbers from the lesser group are different from those from the greater group modulo $2^{n+1}$. Indeed, suppose for a contradiction that $(2^n+m{)}^{2^n+m}\equiv k^k(\mathrm{mod}{2}^{n+1})$ with $1\le k,m\le 2^{n-1}$, then it follows from (7) that $m^m\equiv m^m+2^n\equiv k^k(\mathrm{mod}{2}^n)$. So because of the induction hypothesis, it follows that $m=k$. But in that case we have $(2^n+m{)}^{2^n+m}\equiv m^m+2^n\not\equiv m^m(\mathrm{mod}{2}^{n+1})$ and we obtain the desired contradiction.

So we conclude that no number from the lesser group and greater group has the same residue class as any other number from these two groups. This completes the induction step, and by induction it therefore follows that the given statement is true for all positive integers $n$. $\square$