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

Background

These are my solutions while I was studying number theory using this book. I will use the theorems and definitions mentioned in the book.

If you don't have the book and are not sure which theorem or definition I am using here, you can check this article, where I listed all theorems, corollaries, and definitions by following the book's order.

If you haven't heard of this book and are interested in learning number theory, I strongly recommend it since it is very friendly for beginners. You can check out the book by this link:

Also, for my solutions, I will only use theorems or facts that are proved before this chapter. So you will not see that I quote theorems or facts from the later chapters.

All Problems in 2.2 (p.19)

1. Prove that if $a$ and $b$ are integers, with $b \gt 0$, then there exist unique integers $q$ and $r$ satisfying $a = qb + r$, where $2b \leq r \lt 3b$.
2. Show that any integer of the form $6k + 5$ is also of the form $3j + 2$, but not conversely.
3. Use the Division Algorithm to establish the following:
   (a) The square of any integer is either of the form $3k$ or $3k + 1$.
   (b) The cube of any integer has one of the forms: $9k$, $9k + 1$, or $9k + 8$.
   (c) The fourth power of any integer is either of the form $5k$ or $5k + 1$.
4. Prove that $3a^2 - 1$ is never a perfect square. [Hint: Problem 3(a).]
5. For $n \geq 1$, prove that $n(n + 1)(2n + 1)/6$ is an integer. [Hint: By the Division Algorithm, $n$ has one of the forms $6k$, $6k + 1$, ... , $6k + 5$; establish the result in each of these six cases.]
6. Show that the cube of any integer is of the form $7k$ or $7k \pm 1$.
7. Obtain the following version of the Division Algorithm: For integers $a$ and $b$, with $b \neq 0 $, there exist unique integers $q$ and $r$ that satisfy $a = qb + r$, where $-\frac{1}{2} \lvert b \rvert \lt r \leq \frac{1}{2} \lvert b \rvert$. [Hint: First write $a = q'b + r'$, where $0 \leq r' \lt \lvert b \rvert$. When $0 \leq r' \leq \frac{1}{2} \lvert b \rvert$, let $r = r'$ and $q = q'$; when $\frac{1}{2} \lvert b \rvert \lt r' \lt \lvert b \rvert$, let $r = r' - \lvert b \rvert$ and $q = q' + 1$ if $b \gt 0$ or $q = q' - 1$ if $b \lt 0$.]
8. Prove that no integer in the following sequence is a perfect square: $11, 111, 1111, 11111, ...$ [Hint: A typical term $111 \cdots 111$ can be written as $111 \cdots 111 = 111 \cdots 108 + 3 = 4k + 3.]$
9. Verify that if an integer is simultaneously a square and a cube (as is the case with $64 = 8^2 = 4^3$ ), then it must be either of the form $7k$ or $7k + 1$.
10. For $n \geq 1$, establish that the integer $n(7n^2 + 5)$ is of the form $6k$.
11. If $n$ is an odd integer, show that $n^4 + 4n^2 + 11$ is of the form $16k$.

My Solutions (Q1 - Q11)

Q1

Prove that if $a$ and $b$ are integers, with $b \gt 0$, then there exist unique integers $q$ and $r$ satisfying $a = qb + r$, where $2b \leq r \lt 3b$.

By Theorem 2.1 Division Algorithm, there exist unique integers $q'$ and $r'$ satisfying $a = q'b + r'$ with $0 \leq r' \lt b$.

If we add $2b$ on the inequality, we have $2b \leq r' + 2b\lt 3b$.

From $a = q'b + r'$, we get $a = q'b + r' = q'b + r' + 2b - 2b = (q' - 2)b + r' + 2b$. Because $q'$ and $r'$ are unique, so $q' - 2$ and $r' + 2b$ are unique. Let $q = q'- 2$ and $r = r' + 2b$. Therefore, the statement is proved.

Q2

Show that any integer of the form $6k + 5$ is also of the form $3j + 2$, but not conversely.

$\to$

$6k + 5 = 3 \times (2k) + 3 + 2 = 3 \times (2k+1) + 2$. Let $j = 2k + 1$, so any integer of the form $6k + 5$ is also of the form $3j + 2$.

$\not \gets$

If $j$ is an even number, we can write $j = 2m$ for some integer $m$. Then $3j + 2 = 3 \times (2m) + 2 = 6m + 2 $. $6m + 2 \neq 6k + 5$ by Theorem 2.1 Division Algorithm no matter what $k$ and $m$ we choose. Therefore, any integer of the form $3j + 2$ is not of the form $6k + 5$.

Q3

Use the Division Algorithm to establish the following:

(a) The square of any integer is either of the form $3k$ or $3k + 1$.
(b) The cube of any integer has one of the forms: $9k$, $9k + 1$, or $9k + 8$.
(c) The fourth power of any integer is either of the form $5k$ or $5k + 1$.

(a)

By Theorem 2.1 Division Algorithm, we can write any integer in the form of $3m$, $3m + 1$ and $3m + 2$ for some integer $m$.

For $3m$:

$(3m)^{2} = 9m^2 = 3 \times (3m^2)$ which is of the form $3k$.

For $3m + 1$:

$(3m + 1)^2 = 9m^2 + 6m + 1 = 3 \times (3m^2 + 2m) + 1$ which is of the form $3k + 1$

For $3m + 2$:

$(3m + 2)^2 = 9m^2 + 12m + 4 = 3 \times (3m^2 + 4m + 1) + 1$ which is of the form $3k + 1$.

(b)

By Theorem 2.1 Division Algorithm, we can write any integer in the form of $3m$, $3m + 1$ and $3m + 2$ for some integer $m$.

For $3m$:

$(3m)^3 = 27m^3 = 9 \times (3m^3)$ which is of the form $9k$.

For $3m + 1$:

$(3m + 1)^3 = 27m^3 +27m^2 + 9m+ 1 = 9 \times (3m^3 + 3m^2 + m) + 1$ which is of the form $9k + 1$.

For $3m + 2$:

$(3m + 2)^3 = 27m^3 + 54m^2 + 36m+ 8 = 9 \times (3m^3 + 6m^2 + 4m) + 8$ which is of the form $9k + 8$.

(c)

By Theorem 2.1 Division Algorithm, we can write any integer in the form of $5m + r$, with $ 0 \leq r \lt 5$.

The fourth power of any integer can then be written into $(5m + r)^4$.

From Binomial Expansion, we know

We can see that all the terms are the multiple of 5 except for the last term. It means that all the terms can be written into $5k$ except for the last term. So we only need to consider the cases for the last term.

For $r = 0$:

$r^4 = 0$, $(5m + r)^4$ is of the form $5k$.

For $r = 1$:

$r^4 = 1$, $(5m + r)^4$ is of the form $5k + 1$.

For $r = 2$:

$r^4 = 16 = 15 + 1 = 5 \cdot (3) + 1$, $(5m + r)^4$ is of the form $5k + 1$.

For $r = 3$:

$r^4 = 81 = 80 + 1 = 5 \cdot (16) + 1$, $(5m + r)^4$ is of the form $5k + 1$.

For $r = 4$:

$r^4 = 256 = 255 + 1 = 5 \cdot (51) + 1$, $(5m + r)^4$ is of the form $5k + 1$.

Q4

Prove that $3a^2 - 1$ is never a perfect square. [Hint: Problem 3(a).]

If $3a^2 - 1$ is a perfect square, from 3(a), we know $3a^2 - 1$ can be written as $3k$ or $3k + 1$ for some integer $k$.

For $3k$:

We have $3a^2 - 1 = 3k$, so $3(a^2 - k) = 1$. It is impossible because this implies $3 \mid 1$.

For $3k + 1$:

We have $3a^2 - 1 = 3k + 1$, so $3(a^2 - k) = 2$. It is impossible because this implies $3 \mid 2$.

(I think this question should also mention $a$ is an integer.)

Q5

For $n \geq 1$, prove that $n(n + 1)(2n + 1)/6$ is an integer. [Hint: By the Division Algorithm, $n$ has one of the forms $6k$, $6k + 1$, ... , $6k + 5$; establish the result in each of these six cases.]

By Theorem 2.1 Division Algorithm, we can write $n$ in the form of $6k$, $6k + 1$, ..., $6k + 5$ for some integer $k$.

For $6k$:

which is an integer.

For $6k + 1$:

which is an integer.

For $6k + 2$:

which is an integer.

For $6k + 3$:

which is an integer.

For $6k + 4$:

For $6k + 5$:

Q6

Show that the cube of any integer is of the form $7k$ or $7k \pm 1$.

By Theorem 2.1 Division Algorithm, we can write any integer in the form of $7q + r$ where $0 \leq r \lt b$.

Thus the cube of any integer will be $(7q + r)^3$. By Binomial Expansion,

We can see that all the terms are multiple of 7 except for the last term. It means we can write all the terms into $7k$ for some integer $k$ except for the last term. Thus we only need to consider the cases for the last term.

For $r  = 0$:

$r^3 = 0 $, $(7q + r)^3$ is of the form $7k$.

For $r = 1$:

$r^3 = 1$, $(7q + r)^3$ is of the form $7k + 1$.

For $r = 2$:

$r^3 = 8 = 7 + 1$, $(7q + r)^3$ is of the form $7k + 1$.

For $r = 3$:

$r^3 = 27 = 7 \cdot (3) + 6$, $(7q + r)^3$ is of the form $7k + 6$. $7k + 6 = 7k +6 +7 - 7 =7(k+1) -1$, so it is also of the form $7k - 1$.

For $r = 4$:

$r^3 = 64 = 7 \cdot (9) + 1$, $(7q + r)^3$ is of the form $7k + 1$.

For $r = 5$:

$r^3 = 125 = 7 \cdot (17) + 6$, $(7q + r)^3$ is of the form $7k + 6$ which is also of the form $7k - 1$.

For $r = 6$:

$r^3 = 216 = 7 \cdot (30) + 6$, $(7q + r)^3$ is of the form $7k + 6$ which is also of the form $7k - 1$.

Q7

Obtain the following version of the Division Algorithm: For integers $a$ and $b$, with $b \neq 0 $, there exist unique integers $q$ and $r$ that satisfy $a = qb + r$, where $-\frac{1}{2} \lvert b \rvert \lt r \leq \frac{1}{2} \lvert b \rvert$. [Hint: First write $a = q'b + r'$, where $0 \leq r' \lt \lvert b \rvert$. When $0 \leq r' \leq \frac{1}{2} \lvert b \rvert$, let $r = r'$ and $q = q'$; when $\frac{1}{2} \lvert b \rvert \lt r' \lt \lvert b \rvert$, let $r = r' - \lvert b \rvert$ and $q = q' + 1$ if $b \gt 0$ or $q = q' - 1$ if $b \lt 0$.]

Because $b \neq 0$, so $\lvert b \rvert \gt 0$. By using Theorem 2.1 Division Algorithm, there exist unique integers $q'$ and $r'$ satisfying $a = q' \lvert b \rvert + r'$, where $0 \leq r' \lt \lvert b \rvert$.

When $0 \leq r' \leq \frac{1}{2} \lvert b \rvert$:

• If $b \gt 0$, we have $a = q'b + r'$, so we let $r = r'$ and $q = q'$.
• If $b \lt 0$, then $a = q'(-b) + r' = -q'(b) + r'$. So we let $r = r'$ and $q = -q'$.

(I modified the Hint a bit, since I think this is more accurate. If you have other thoughts, please share yours in the comment section below.)

When $\frac{1}{2} \lvert b \rvert \lt r' \lt \lvert b \rvert$:

We have $-\frac{1}{2} \lvert b \rvert \lt r' - \lvert b \rvert \lt 0$. So,

• If $b \gt 0$, we have $a = (q' + 1)b + r' - b$, so we let $r = r' - b$ and $q = q' + 1$.
• If $b \lt 0$, we have $a = (q' + 1)(-b) + r' + b = -(q' + 1)b + (r' + b)$, so we let $r = r' + b$ and $q = -(q' + 1)$.

The Theorem 2.1 Division Algorithm also guarantees the uniqueness of the $q$ and $r$ in different cases. Therefore, we obtained the required version of the Division Algorithm.

Q8

Prove that no integer in the following sequence is a perfect square:

[Hint: A typical term $111 \cdots 111$ can be written as

Using the hint, a typical term $111 \cdots 111$ can be written as $111 \cdots 111 = 111 \cdots 108 + 3 = 4k + 3$ for some integer $k$.

Assume there exist a term that is a perfect square. It means $4k + 3 = m^{2}$ for some integer $m$.

If $m$ is odd:

$m = 2q$ for some integer $q$. So, $4k + 3 = (2q)^2 = 4q^2$ which is impossible by Theorem 2.1 Division Algorithm.

If $m$ is even:

$m = 2q + 1$ for some integer $q$. So, $4k + 3 = (2q + 1)^2 = 4q^2 + 4q + 1 = 4(q^2 + q) + 1$ which is also impossible by Theorem 2.1 Division Algorithm.

Therefore, there is no integer in the sequence is a perfect square.

Q9

Verify that if an integer is simultaneously a square and a cube (as is the case with $64 = 8^2 = 4^3$ ), then it must be either of the form $7k$ or $7k + 1$.

From Q6 above, we know the cube of any integer is of the form $7k$ or $7k \pm 1$. We know $7k - 1$ is also of the form $7k + 6$ from my solution in Q6.

By Theorem 2.1 Division Algorithm, an integer is of the form $7q + r$ for some integer $q$ and $r$ with $0 \leq r \lt q$.

We know $(7q + r)^2 = 49q^2 + 14qr + r^2 = 7(7q^2 + 2qr) + r^2$ which is of the form $7m + r^2$ for some integer $m$ . So we only need to consider the $r^2$ term.

For $r = 0$:

$r^2 = 0$, so $(7q + r)^2$ is of the form $7k$.

For $r = 1$:

$r^2 = 1$, so $(7q + r)^2$ is of the form $7k + 1$.

For $r = 2$:

$r^2 = 4$, so $(7q + r)^2$ is of the form $7k + 4$.

For $r = 3$:

$r^2 = 9$, so $(7q + r)^2 = 7m + 9 = 7(m + 1) + 2$ which is of the form $7k + 2$ for some integer $k$.

For $r = 4$:

$r^2 = 16$, so $(7q + r)^2 = 7m + 16 = 7(m+2) + 2$ which is of the form $7k + 2$ for some integer $k$.

For $r = 5$:

$r^2 = 25$, so $(7q + r)^2 = 7m + 25 = 7(m+3) + 4$ which is of the form $7k + 4$ for some integer $k$.

For $r = 6$:

$r^2 = 36$ so $(7q + r)^2 = 7m + 36 = 7(m+5) + 1$ which is of the form $7k + 1$ for some integer $k$.

Therefore, the square of an integer is either of the form $7k$, $7k + 1$, $7k + 2$ or $7k + 4$.

Because the integer is simultaneously a square and a cube, so the integer must be either of the form $7k$ or $7k + 1$.

Q10

For $n \geq 1$, establish that the integer $n(7n^2 + 5)$ is of the form $6k$.

By Theorem 2.1 Division Algorithm, we can write $n$ in the form of $6q + r$ for some integer $q$ and $r$ with $0 \leq r \lt q$. Thus,

All the terms are divisible by 6 except for the last 2 terms, so we only need to verify whether the last two terms $7r^3 + 5r$ are divisible by 6.

For $r = 0$:

$7r^3 + 5r = 0$ which is divisible by 6.

For $r = 1$:

$7r^3 + 5r = 12 = 6 \times 2$.

For $r = 2$:

$7r^3 + 5r = 66 =6 \times 11$.

For $r = 3$:

$7r^3 + 5r = 204 = 6 \times 34$.

For $r = 4$:

$7r^3 + 5r = 468 = 6 \times 78$.

For $r = 5$:

$7r^3 + 5r = 900 = 6 \times 150$.

For $r = 6$:

$7r^3 + 5r = 1542 = 6 \times 257$.

Therefore, for $n \geq 1$, the integer $n(7n^2 + 5)$ is of the form $6k$.

Q11

If $n$ is an odd integer, show that $n^4 + 4n^2 + 11$ is of the form $16k$.

By Theorem 2.1 Division Algorithm, we let $n = 2k + 1$ for some integer $k$ because $n$ is an odd integer.

We can see that all the terms are multiple of 16 except for the last two terms $40k^2 + 24k$, so we only need to verify whether these two are divisible by 16.

If $k$ is an even integer, we write $k = 2q$ by Theorem 2.1 Division Algorithm. $40k^2 + 24k = 40(2q)^2 + 24(2q) = 160q^2 + 48q = 16(10q^2 + 3q)$.

If $k$ is a odd integer, we write $k = 2q + 1$ by Theorem 2.1 Division Algorithm.

Therefore, if $n$ is an odd integer, $n^4 + 4n^2 + 11$ is of the form $16k$.

Another Method is to split the term $40k^2$ and spot a fact from the equation.

From here we know $k(k+1)$ is a multiple of 2. Therefore, the last term will become $24(2a) = 48a$ for some integer $a$. We know $48$ is multiple of 16. Therefore, $n^4 + 4n^2 + 11$ is of the form $16k$.