Problem 1339

1. Base Case:
For $n = 2$, we need to check if $1^1 + 3^3$ is a multiple of $2^2 = 4$ but not a multiple of $2^3 = 8$.
$$1^1 + 3^3 = 1 + 27 = 28$$
Clearly, $28$ is divisible by $4$ but not by $8$. Thus, the base case holds.

2. Inductive Step:
Assume the statement is true for $n-1$, i.e.,
$$1^1 + 3^3 + \cdots + (2^{n-1} - 1)^{2^{n-1} - 1} \equiv 2^{n-1} \pmod{2^n}$$
We need to show that:
$$1^1 + 3^3 + \cdots + (2^n - 1)^{2^n - 1} \equiv 2^n \pmod{2^{n+1}}$$

3. Analyzing the New Term:
Consider the term $(2^n - 1)^{2^n - 1}$. For any odd $x$, we have:
$$\nu_2(x^{2^{n-1}} - 1) = \nu_2(x^2 - 1) + \nu_2(2^{n-2})$$
Since $x$ is odd, $x^2 - 1$ is divisible by $4$, so:
$$\nu_2(x^2 - 1) \geq 2$$
And:
$$\nu_2(2^{n-2}) = n-2$$
Thus:
$$\nu_2(x^{2^{n-1}} - 1) \geq 2 + (n-2) = n$$
Therefore, $x^{2^{n-1}} \equiv 1 \pmod{2^n}$.

4. Combining Terms:
Consider the sum:
$$1^1 + 3^3 + \cdots + (2^n - 1)^{2^n - 1}$$
By the inductive hypothesis:
$$1^1 + 3^3 + \cdots + (2^{n-1} - 1)^{2^{n-1} - 1} \equiv 2^{n-1} \pmod{2^n}$$
Adding the new term:
$$(2^n - 1)^{2^n - 1} \equiv 1 \pmod{2^n}$$
So:
$$1^1 + 3^3 + \cdots + (2^n - 1)^{2^n - 1} \equiv 2^{n-1} + 1 \pmod{2^n}$$

5. **Modulo $2^{n+1}$:**
We need to show that the sum is $2^n \pmod{2^{n+1}}$. Since:
$$2^{n-1} + 1 \equiv 2^n \pmod{2^{n+1}}$$
This completes the inductive step.

$\blacksquare$