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

  • Thread starter Math100
  • Start date
In summary, the statement ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## is true for any value of ##n##. This means that when any number ##a## is raised to the power of ##2^n##, it will always be congruent to ##1## modulo ##2^{n+2}##. This can be proven using mathematical induction, as well as properties of modular arithmetic. Additionally, this statement has important implications in computer science and cryptography, as it relates to the concept of primitive roots and the security of certain encryption algorithms.
  • #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 ##.
 
Last edited by a moderator:
  • Like
Likes Delta2
Physics news on Phys.org
  • #2
Math100 said:
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}~##
 
  • #3
SammyS said:
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).##
 
  • Like
Likes SammyS
  • #4
Math100 said:
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.
Math100 said:
(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.

Math100 said:
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.)
 
  • Like
Likes Math100
  • #5
What I meant to express/write using Latex commands is ## a^{2^n} ##.
 
  • #6
Math100 said:
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)}.
 
  • Like
Likes SammyS and Math100
  • #7
Thank you, now I know.
 

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

1. What does the notation "##a^{({2}^{n})}\equiv 1\pmod {2^{n+2}}##" mean?

The notation means that the expression "##a^{({2}^{n})}##" is congruent to 1 modulo "##2^{n+2}##", which means that when divided by "##2^{n+2}##", the remainder is 1.

2. What is the significance of the number ##2^{n+2}## in the expression?

The number ##2^{n+2}## represents the power of 2 that the expression is being taken modulo. In this case, it is 4 more than the power of 2 being raised to, which is important for proving the statement.

3. How does this statement apply to any value of ##n##?

The statement applies to any value of ##n## because the expression "##a^{({2}^{n})}##" is being taken modulo a power of 2, which is always a multiple of 2. Therefore, the statement will hold true for any value of ##n##.

4. What is the proof for this statement?

The proof for this statement involves using mathematical induction. The base case, where ##n=1##, can be easily shown to be true. Then, assuming the statement is true for ##n=k##, it can be shown that it is also true for ##n=k+1##. This completes the inductive step and proves the statement for all values of ##n##.

5. Can this statement be generalized to other numbers besides 2?

Yes, this statement can be generalized to any number, as long as the base of the exponent and the modulo number are relatively prime. This means that they do not share any common factors other than 1. For example, the statement "##a^{({3}^{n})}\equiv 1\pmod {3^{n+2}}##" would also hold true for any value of ##n##.

Back
Top