Massive expression mod $2^{2013}$ Find $$1^1+3^3+5^5 + \cdots +(2^{2012}-1)^{(2^{2012}-1)}$$ modulo $2^{2013}$. By checking small cases I am pretty sure that it is $2^{2012}$. I tried applying induction but you "lose" powers of two at each step. So instead I used binomial theorem to reduce it to $$\sum_{i=1,i  \text{ odd}}^{2^{2011}-1} i^i-i^{2^{2012}-i}$$ again it looks very much like induction, but I can't make it work. Any help please. 
EDIT: Also 
$\phi({2^{2013}})=2^{2012}$ so really, by euler's theorem the above becomes $\sum_{i=1,i  \text{ odd}}^{2^{2011}-1} i^i-i^{-i}$
 A: I think induction does work to show that for $k\ge2$,
$$
\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} \equiv 2^k \pmod{2^{k+1}}.
$$
One fact we'll use is that for $n\ge3$, we actually have $a^{2^{n-2}}\equiv1\pmod {2^n}$ for any odd $a$; this is one power of $2$ stronger than Euler's theorem.
Checking the $k=2$ case is easy. Suppose that it holds for some particular $k$. Then
\begin{align*}
\sum_{i=1}^{2^k} (2i-1)^{2i-1} &= \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=2^{k-1}+1}^{2^k} (2i-1)^{2i-1} \\
&= \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=1}^{2^{k-1}} (2^k+2i-1)^{2^k+2i-1} \\
&\equiv \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=1}^{2^{k-1}} (2^k+2i-1)^{2i-1} \pmod{2^{k+2}}
\end{align*}
by the above fact. Now note that $(2^k+j)^m \equiv j^m + m2^kj^{m-1} \pmod{2^{k+2}}$ by the binomial theorem (since $k\ge2$); in particular, only $j\pmod4$ matters, so if $j$ and $m$ are odd then $(2^k+j)^m \equiv j^m + m2^k \pmod{2^{k+2}}$. Therefore
\begin{align*}
\sum_{i=1}^{2^k} (2i-1)^{2i-1} &\equiv \sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + \sum_{i=1}^{2^{k-1}} \big( (2i-1)^{2i-1} + (2i-1)2^k \big) \\
&= 2\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} + 2^{2k-2} 2^k \\
&= 2\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1} \pmod{2^{k+2}}
\end{align*}
(again since $k\ge2$). The induction hypothesis that $\sum_{i=1}^{2^{k-1}} (2i-1)^{2i-1}\equiv 2^k\pmod {2^{k+1}}$ now implies that $\sum_{i=1}^{2^k} (2i-1)^{2i-1} \equiv 2^{k+1}\pmod {2^{k+2}}$ as desired.
