Use mathematical induction to prove that if x is an odd integer, then for every integer n ≥ 0,
$x^{2^n}$ ≡ 1 (mod $2^{n + 1}$)
*Reposting due to me not reading the problem carefully. It is in fact $x^{2^n}$ so it does make sense. *
So for this proof I know that if x is odd then each term is going to be even or divisible by 2. And there will be n + 1 terms in this factorization. This indicates that $x^{2^n}$ - 1 is divisible by $2^{n + 1}$. Or the modulus statement $x^{2^n}$ ≡ 1 (mod $2^{n + 1}$)
However, I do not know how to really prove that n ≥ 0 for all odd integers by induction.I know that I should start with the formula with a specific n as a base. And then I have to end with the formula with n + 1 for induction. I'm not sure how to connect these two and get there.
As always, thank you for any and all help.
Proceed by induction on $n$.
For $n=1$, $$x^{2^1}-1 = x^2-1 = (x+1)(x-1)$$ which is a multiple of $2^{1+1}=4$, since $x+1$ and $x-1$ are both even.
Thus, the base case is verified.
Next, suppose the claim holds for a fixed integer $n \ge 1$.
By the inductive hypothesis, we have $2^{n+1}{\,\mid\,}\left(x^{2^n}-1\right)$. \begin{align*} \text{Then}\;\;& 2^{n+1}{\,\mid\,}\left(x^{2^n}-1\right)\\[4pt] \implies\;&\left(2^{n+1}\right)^2{\,\mid\,}\left(x^{2^n}-1\right)^2\\[4pt] \implies\;&2^{2n+2}{\,\mid\,}\left(x^{2^n}-1\right)^2\\[4pt] \implies\;&2^{n+2}{\,\mid\,}\left(x^{2^n}-1\right)^2\\[20pt] \text{Also}\;\;& 2^{n+1}{\,\mid\,}\left(x^{2^n}-1\right)\\[4pt] \implies\;&2\left(2^{n+1}\right){\,\mid\,}2\left(x^{2^n}-1\right)\\[4pt] \implies\;&2^{n+2}{\,\mid\,}2\left(x^{2^n}-1\right)\\[4pt] \end{align*} hence $$2^{n+2}{\,\mid\,}\left(\left(x^{2^n}-1\right)^2 + 2\left(x^{2^n}-1\right)\right)$$ But identically, we have $$\left(x^{2^n}-1\right)^2 + 2\left(x^{2^n}-1\right) =x^{2^{n+1}}-1$$ hence $$2^{n+2}{\,\mid\,}\left(x^{2^{n+1}}-1\right)$$ which completes the induction.