Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?

[Math100]

Homework Statement

Establish that if $a$ is an odd integer, then for any $n\geq 1$, $a^{({2}^{n})}\equiv 1\pmod {2^{n+2}}$.
[Hint: Proceed by induction on $n$.]

Relevant Equations

None.

Proof:

The proof is by induction.
(1) When $n=1$, the statement is $a^{({2}^{1})} \equiv 1 \pmod {8}$, which is true because $a$ is an odd integer.
(2) Now assume the statement is true for some integer $n=k\geq 1$, that is assume $a^{({2}^{k})}\equiv 1\pmod {2^{k+2}}$.
Then $a^{({2}^{k})}\equiv 2^{k+2}\cdot b+1$ for some $b\in\mathbb{Z}$.
Next, we will show that the statement for $n=k+1$ is true.
Observe that $a^{({2}^{k+1})}=(a^{({2}^{k})})^{2}=(2^{k+2}\cdot b+1)^{2}=b^{2}\cdot 2^{2k+4}+b\cdot 2^{k+3}+1$.
Note that $2^{2k+4}\equiv 0\pmod {2^{k+3}}$.
This establishes $a^{(2^{k+1})}\equiv 1\pmod {2^{k+3}}$, which implies that the statement is true for $n=k+1$.
The proof by induction is complete.
Therefore, $a^{({2}^{n})}\equiv 1\pmod {2^{n+2}}$ if $a$ is an odd integer for any $n\geq 1$.

 

[SammyS]

Homework Statement:: Establish that if $a$ is an odd integer, then for any $n\geq 1$, $a^{2}^{n}\equiv 1\pmod {2^{n+2}}$.
[Hint: Proceed by induction on $n$.]
Relevant Equations:: None.

Proof:

The proof is by induction.
(1) When $n=1$, the statement is $a^{2}\equiv 1\pmod {8}$, which is true because $a$ is an odd integer.
(2) Now assume the statement is true for some integer $n=k\geq 1$, that is assume $a^{2}^{k}\equiv 1\pmod {2^{k+2}}$.
Then $a^{2}^{k}\equiv 2^{k+2}\cdot b+1$ for some $b\in\mathbb{Z}$.
Next, we will show that the statement for $n=k+1$ is true.
Observe that $a^{2}^{k+1}=(a^{2}^{k})^{2}=(2^{k+2}\cdot b+1)^{2}=b^{2}\cdot 2^{2k+4}+b\cdot 2^{k+3}+1$.
Note that $2^{2k+4}\equiv 0\pmod {2^{k+3}}$.
This establishes $a^{2k+1}\equiv 1\pmod {2^{k+3}}$, which implies that the statement is true for $n=k+1$.
The proof by induction is complete.
Therefore, $a^{2n}\equiv 1\pmod {2^{n+2}}$ if $a$ is an odd integer for any $n\geq 1$.

So what's with all those yellow & red error messages?
Well, MathJax wants to know what you mean by the following: ## a^{2}^{n} ##.

Do you mean $\displaystyle a^{(2^n)}~$ or do you mean $\displaystyle {\left(a^2\right)}^{n}~$

 

[fresh_42]

So what's with all those yellow & red error messages?
Well, MathJax wants to know what you mean by the following: ## a^{2}^{n} ##.

Do you mean $\displaystyle a^{(2^n)}~$ or do you mean $\displaystyle {\left(a^2\right)}^{n}~$

Corrected. The smallest example to decide it was $(a,n)=(3,3).$

 

[fresh_42]

Homework Statement:: Establish that if $a$ is an odd integer, then for any $n\geq 1$, $a^{({2}^{n})}\equiv 1\pmod {2^{n+2}}$.
[Hint: Proceed by induction on $n$.]
Relevant Equations:: None.

Proof:

The proof is by induction.
(1) When $n=1$, the statement is $a^{({2}^{1})} \equiv 1 \pmod {8}$, which is true because $a$ is an odd integer.

Reference? Alternatively, a short line $(2n+1)^2-1=4\cdot n \cdot (n+1)$ would be of help here.

(2) Now assume the statement is true for some integer $n=k\geq 1$, that is assume $a^{({2}^{k})}\equiv 1\pmod {2^{k+2}}$.
Then $a^{({2}^{k})}\equiv 2^{k+2}\cdot b+1$ for some $b\in\mathbb{Z}$.

Damn it. This tiny word "then" led me to comment ...

Sure? Let's see:
\begin{align*}
a^{({2}^{k})}&=(2m+1)^{(2^k)}=1+\sum_{j=1}^{2^k}\binom{2^k}{j}(2m)^j=1+\sum_{j=1}^{2^k}\dfrac{2^jm^j(2^k)\cdot (2^k-1)\cdots (2^k-j+1)}{j!}\\
&= 1+ \dfrac{2m\cdot 2^k}{1}+\dfrac{2^2m^22^k(2^k-1)}{2}+ \dfrac{2^3m^32^k(2^k-1)(2^k-2)}{2\cdot 3}+\ldots
\end{align*}

I can only see $a^{({2}^{k})}\equiv 2^{k+1}\cdot b+1$ for some $b\in\mathbb{Z}$ so whatever is correct, it deserves a proof.

... until I finally noticed that "then" means "i.e." or "thus" or "that means". It was a transcription of the induction hypothesis and no conclusion! My fault, since whenever I see a "then" I automatically ask "why?". Remember that a proof is a text that is intended to convince people. Therefore, words matter.

At least, I now understand what has to be shown.

Next, we will show that the statement for $n=k+1$ is true.
Observe that $a^{({2}^{k+1})}=(a^{({2}^{k})})^{2}=(2^{k+2}\cdot b+1)^{2}=b^{2}\cdot 2^{2k+4}+b\cdot 2^{k+3}+1$.
Note that $2^{2k+4}\equiv 0\pmod {2^{k+3}}$.
This establishes $a^{(2^{k+1})}\equiv 1\pmod {2^{k+3}}$, which implies that the statement is true for $n=k+1$.
The proof by induction is complete.
Therefore, $a^{({2}^{n})}\equiv 1\pmod {2^{n+2}}$ if $a$ is an odd integer for any $n\geq 1$.

The rest looks good. It is also an interesting example that a proof by induction can be easier than a direct computation. (So my calculation has served at least this.)

 

[Math100]

What I meant to express/write using Latex commands is $a^{2^n}$.

 

[fresh_42]

What I meant to express/write using Latex commands is $a^{2^n}$.

Whenever there is more than one sign in the exponent, we have to use parathesis: a^{2^n}, and it is even better to use normal parenthesis to avoid any confusion: a^{(2^n)}.

 

[Math100]

Thank you, now I know.