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?

An $x$ such that $\phi(m)$ is the least positive integer $k$ for which $x^k \equiv 1 \mod m$ is called a primitive root mod $m$.  The positive integers that have primitive roots are
$2, 4, p^n$ and $2 p^n$ for odd primes $p$ and positive integers $n$.  In particular you are correct that there is no primitive root for $2^n$ if $n \ge 3$, and thus $x^{2^{n-2}} \equiv 1 \mod 2^n$ for all odd $x$ and all $n \ge 3$.
