- #1

Math100

- 780

- 220

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

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

Last edited by a moderator: