# Prove by Induction if x is an odd integer, then for every integer n ≥ 0, $x^{2^n}$ ≡ 1 (mod $2^{n + 1}$)

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.

• Each term? What terms? Commented Feb 21, 2018 at 17:49
• "...if x is odd then each term is going to be even..." - each term of what exactly? Commented Feb 21, 2018 at 17:49
• Hint: The induction is on $n,$ and $x^{2^{n+1}}=\left(x^{2^n}\right)^2.$ Commented Feb 21, 2018 at 17:51
• More generally, if $u\equiv 1\pmod{2^{n+1}}$ show that $u^2\equiv 1\pmod{2^{n+2}}.$ Commented Feb 21, 2018 at 17:52
• I was thinking of the the terms of a factorization I guess which could be the wrong way to think of it. Commented Feb 21, 2018 at 17:56

For $\;x=2k+1\;$ an odd integer:

$$n=1: (2k+1)^{2^1}=4k^2+4k+1=4k(k+1)+1=1\pmod 4=2^2\;\checkmark$$

Suppose truth for all integers up to $\;n\;$ and we shall prove now for $\;n\;$ :

$$x^{2^{n+1}}=\left(x^{2^n}\right)^2\stackrel{\text{Ind. Hyp.}}=\left(1+m2^{n+1}\right)^2=1+m2^{n+2}+m2^{2n+2}\;,\;\;m\in\Bbb Z$$

Fill in details and end the proof.

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.