Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q15


Background

All theorems, corollaries, and definitions listed in the book's order:

Theorems and Corollaries in Elementary Number Theory
All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 4)

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

< Chapter 4.2, Q14 Chapter 4.2, Q16 >