Euler's theorem for powers of 2 According to Euler's theorem,
$$x^{\varphi({2^k})} \equiv 1 \mod 2^k$$
for each $k>0$ and each odd $x$. Obviously, number of positive integers less than or equal to $2^k$ that are relatively prime to $2^k$ is 
$$\varphi({2^k}) = 2^{k-1}$$
so it follows that
$$x^{{2^{k-1}}} \equiv 1 \mod 2^k$$
This is fine, but it seems like even
$$x^{{2^{k-2}}} \equiv 1 \mod 2^k$$
holds, at least my computer didn't find any counterexample.
Can you prove or disprove it?

This is basically the same as Will's answer, but the key to all this is the simple equation
$x^{2^{m}}-1 = (x^{2^{m-1}}-1)(x^{2^{m-1}}+1)$ for $m \geq 1.$ When $x$ is an odd integer, both factors on the right side of the equation are even integers, but also, every odd integer is congruent to $\pm 1$ (mod 4), so at least one factor on the right side is divisible by $4$ (and the other factor is congruent to $2$ (mod $4$)). Hence the left hand side is divisible by $8$ whenever $x$ is odd and $m \geq 2.$ And, furthermore, the power of $2$ dividing $x^{2^{m}}-1$ is at least one higher than the power of $2$ dividing $x^{2^{m-1}}-1.$ When $m \geq 1,$ then, it follows by induction that $x^{2^{m}}-1$ is divisible by $2^{m+2}.$
