Euler's theorem for powers of 2

Question

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?

Answer 1

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}. $$

Answer 2

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$.

Answer 3

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 )$$

Answer 4

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}.$