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

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

Prove the assertions below:
(a) If $a$ is an odd integer, then $a^{2} \equiv 1 \pmod 8$.
(b) For any integer $a$, $a^{3} \equiv 0, 1,$ or $6 \pmod 7$.
(c) For any integer $a$, $a^{4} \equiv 0$ or $1 \pmod 5$.
(d) If the integer $a$ is not divisible by $2$ or $3$, then $a^{2} \equiv 1 \pmod {24}$.

Solution

(a)

By Theorem 2.1 Division Algorithm, we can write $a$ in the form $4k + r$ where $0 \leq r \lt 4$. Since $a$ is an odd integer, $a$ is either in the form $4k + 1$ or $4k + 3$.

For $a = 4k + 1$, $a^{2} \equiv (4k + 1)^{2} \equiv 16k^{2} + 8k + 1 \equiv 1 \pmod 8$.
For $a = 4k + 3$, $a^{2} \equiv (4k + 3)^{2} \equiv 16k^{2} + 24k + 9 \equiv 8(2k^{2} + 3k + 1) + 1 \equiv 1 \pmod 8$.

(b)

By Theorem 2.1 Division Algorithm, we can write $a$ in the form $7k + r$ where $0 \leq r \lt 7$.

When $r = 0$, $7k^{3} \equiv 0 \pmod 7$.

For $1 \leq r \lt 7$, we know all the terms in the binomial expansion of $(7k + r)^{3}$ will contain $(7k)$ except for the last term. That means, except for the last term, all the terms will be $\equiv 0 \pmod 7$. Thus, we only need to consider the last term, which means $a \equiv (7k + r)^{3} \equiv r^{3} \pmod 7$.

When $r = 1$, $r^{3} \equiv 1 \pmod 7$.
When $r = 2$, $r^{3} \equiv 8 \equiv 1 \pmod 7$.
When $r = 3$, $r^{3} \equiv 27 \equiv 6 \pmod 7$.
When $r = 4$, $r^{3} \equiv 64 \equiv 1 \pmod 7$.
When $r = 5$, $r^{3} \equiv 125 \equiv 6 \pmod 7$.
When $r = 6$, $r^{3} \equiv 216 \equiv 6 \pmod 7$.

Therefore, for any integer $a$, $a^{3} \equiv 0, 1,$ or $6 \pmod 7$.