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?
 A: You have it. For any odd $x$ we get $ x^2 \equiv 1 \pmod 8,$ which is where it starts.  Note that we can write any odd $x$ as $4m \pm 1,  $ then we get
$$  x^2 = (4m \pm 1)^2 = 16 m^2 \pm 8m + 1 \equiv 1 \pmod 8.  $$ After that there should be no trouble applying induction.
Sure, just to save typing, take $A = 2^{k-2}.$ Then we begin with
$$  x^A \equiv 1 \pmod {4A}, $$
or
$$ x^A = 1 + 4 A t.   $$ Then
$$ x^{2A} = (x^A)^2 = 1 + 8 A t + 16 A^2 t^2 \equiv 1 \pmod {8A}.  $$
A: 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$.
A: 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}.$
A: We can look at this from another view.    
Let's first rewrite the question as: is it true, that $2^k | x^{2^{k-2}}-1 $?    
Next we recall, that $\small x^2-1 = (x+1)(x-1)$ and thus $\small x^{2^a}-1=(x^{2^{a-1}}+1)(x^{2^{a-1}}-1)$      
So we can now rewrite the question for some top-exponent $ \small b=k-2$
$$ M_b=x^{2^b}-1 = (x^{2^{b-1}}+1)(x^{2^{b-2}}+1)(x^{2^{b-3}}+1)\cdots(x^{2^0}+1)(x^{2^0}-1)$$    
This are b+1 factors by simply counting of parentheses. Now x must be odd such that each parenthese is even. Then each parenthese contains at least the primefactor 2 to the power of 1, so we know already: at least $2^{b+1} $ divides $M_b$.   
But, the odd $x$ is either $4y+1$ or $4y+3$, thus one of the two last factors, $(x+1)$ or $(x-1)$ must be divisible by $2^2$ because they form either $\small ((4y+1)+1)((4y+1)-1)$ or $\small ((4y+3)+1)((4y+3)-1)$.     
So one of those two parentheses adds (at least) one more primefactor 2, and it follows that (at least) $2^{b+2}$ divides $M_b$ and we have, that indeed
$$2^k | (x^ {2^{k-2}}-1 )$$
