# congruence modulo 2^n

It holds for $n=3$; I'll let you prove that. Suppose it holds up to $n-1$. Note that $x^{2^{n-2}}-1=(x^{2^{n-3}}-1)(x^{2^{n-3}}+1)$; and by the induction hypothesis, $x^{2^{n-3}}-1$ is divisible by $2^{n-1}$, and since $x$ is odd, $x^{2^{n-3}}+1$ is divisible by 2 so $(x^{2^{n-3}}-1)(x^{2^{n-3}}+1)=x^{2^{n-2}}-1$ is divisible by $2^n$.