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