Suppose two give the same remainder when divided by $2^n$ then there exist odd $a, b < 2n$ such that $b^b \equiv a^a$ mod $2^n$. WLOG $b > a$ and let $k = v_2(b - a)$. Note this gives $2^k | b - a \Rightarrow 2^k \leq b - a \leq (2n - 1) - 1 = 2n - 2 \leq 2^{n - 1}$ $\forall$ $n \in \mathbb{N}$ and so $k \leq n - 1 \Rightarrow k + 1 \leq n$. This means $b^b \equiv a^a$ mod $2^{k + 1}$. Since $\varphi(2^{k + 1}) = 2^k$ we have that $b^b \equiv b^a$ mod $2^{k + 1}$ as $2^k | b - a$ and $b$ is odd so it is indeed coprime with $2^{k + 1}$. Thus, $a^a \equiv b^b \equiv b^a$ mod $2^{k + 1} \Rightarrow 2^{k + 1} | b^a - a^a = (b - a)(b^{a - 1} + b^{a - 2}a + \dots + a^{a - 1})$. Since the right bracket is a sum of an odd number of odd terms as both $a$ and $b$ are odd we have that the right bracket is odd and so we must have $2^{k + 1} | b - a$ which is a contradiction as $v_2(b - a) = k$. Thus no $a, b$ exist so we are done.

Thanks,alchimist_,I like your solution!

We consider for a fixed $n$ the values of $a^a \mod 2^n$ for odd $a$. Assume for the sake of contradiction that we have $a^a \equiv b^b \mod 2^n$ for some odd $b < a$. We can interperet this as $ 2^n \vert a^a-b^b \Longleftrightarrow v_2(a^a-b^b) \geq n $ We note a couple properties of the p-adic valuation function: $ v_p(x) \neq v_p(y) \Rightarrow v_p(x+y) = min\{v_p(x), v_p(y)\} $ If $x$, $y$, $k$ odd then $v_2(x^k-y^k) = v_2(x-y)$ If $x$, $y$ odd and $k$ even then $v_2(x^k-y^k) = v_2(x+y) + v_2(x-y) + v_2(k) - 1$ by the LTE Lemma. Now consider: $ a^a - b^b = a^a - a^b + a^b - b^b = a^b(a^{a-b}-1) + a^b-b^b $ By the aforementioned properties we have $ v_2(a^a-b^b) = v_2(a^b(a^{a-b}-1) + a^b-b^b) = min\{ v_2(a^{a-b}-1), v_2(a^b-b^b) \} $ We have: $ v_2(a^b-b^b) = v_2(a-b) $ $ v_2(a^{a-b}-1) = v_2(a+1) + v_2(a-1) + v_2(a-b) - 1 $ We have $v_2(a+1) + v_2(a-1) - 1 > 0$, thus the two terms are unequal, with the latter clearly being larger, thus the value of the first is chosen. Thus: $ v_2(a^a - b^b) = v_2(a^b - b^b) = v_2(a-b) < n $ Because $a-b < 2^n$. This is a contradiction to our assumption and so we are done. (If i didn't make any typos)