Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q15
My Solution for "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$.]"
Table of Contents
Background
All theorems, corollaries, and definitions listed in the book's order:
I will only use theorems or facts that are proved before this question. So, you will not see that I quote theorems or facts from the later chapters.
Question
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$.]
Solution
We can prove the statement by using mathematical induction.
Base Case:
For $n = 1$, we need to prove $a^{2} \equiv 1 \pmod {8}$ when $a$ is an odd integer.
By Theorem 2.1 Division Algorithm, we can write $a$ in the form $4q + 1$ or $4q + 3$ for some integer $q$.
For $4q + 1$, $a^{2} \equiv 16q^{2} + 8q + 1 \equiv 1 \pmod {8}$. For $4q + 3$, $a^{2} \equiv 16q^{2} + 24q + 9 \equiv 1 \pmod {8}$.
Induction Hypothesis:
Assume that if $a$ is an odd integer, $a^{2^{k}} \equiv 1 \pmod {2^{k + 2}}$ for some integer $k \geq 1$.
Consider the case for $k + 1$:
From the inductive hypothesis, we have $a ^{2^{k}} - 1 = m2^{k + 2}$ for some integer $m$. Then for $a ^{2^{k + 1}} \pmod {2^{k + 3}}$:
$$ \begin{equation} \begin{split} a ^{2^{k + 1}} & \equiv a^{2^{k} \cdot 2} \\ & \equiv (a^{2^{k}})^{2} \\ & \equiv (1 + m2^{k + 2})^{2} \\ & \equiv m^{2} \cdot 2^{2k + 4} + 2 \cdot m \cdot 2^{k + 2} + 1 \\ & \equiv m^{2} \cdot 2^{k + 3} \cdot 2^{k + 1} + m \cdot 2^{k+3} + 1 \\ & \equiv 1 \pmod {2^{k + 3}} \end{split} \nonumber \end{equation} $$Conclusion:
This proves the statement by induction.
Read More: All My Solutions for This Book
Related Pages
Ranblog Newsletter
Join the newsletter to receive the latest updates in your inbox.
%20-%20Q15){kind=link}