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