Elementary Number Theory Problems 2.3 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.

Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)

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 - 3)

RanblogRan

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:

Elementary Number Theory (Paperback)

Get it now:

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.

Limited-Time Offer: 50% Off Discount Forever!

[This is for the early supporters. You will have 50% Off forever! This offer will last until I finish 10 premium articles.]

All Problems in 2.3 (p. 24)

1. If $a \mid b$, show that $(-a) \mid b$, $a \mid (-b)$, and $(-a) \mid (-b)$.
2. Given integers $a, b, c, d$, verify the following:
   (a) lf $a \mid b$, then $a \mid bc$.
   (b) If $a \mid b$ and $a \mid c$, then $a^2 \mid bc$.
   (c) $a \mid b$ if and only if $ac \mid bc$, where $c \neq 0$.
   (d) If $a \mid b$ and $c \mid d$, then $ac \mid bd$.
3. Prove or disprove: If $a \mid (b + c)$, then either $a \mid b$ or $a \mid c$.
4. For $n \geq 1$, use mathematical induction to establish each of the following divisibility statements:
   (a) $8 \mid 5^{2n} + 7$. [Hint: $5^{2(k+1)} + 7 = 5^{2}(5^{2k} + 7) + (7 - 5^{2} \cdot 7)$.]
   (b) $15 \mid 2^{4n} - 1$.
   (c) $5 \mid 3^{3n+1} + 2^{n+1}$.
   (d) $21 \mid 4^{n+1} + 5^{2n-1}$.
   (e) $24 \mid 2 \cdot 7^n + 3 \cdot 5^n - 5$.
5. Prove that for any integer $a$, one of the integers $a$, $a+ 2$, $a + 4$ is divisible by 3.
6. For an arbitrary integer $a$, verify the following:
   (a) $2 \mid a(a + 1)$, and $3 \mid a(a + 1)(a + 2)$.
   (b) $3 \mid a(2a^{2}+7)$.
   (c) If $a$ is odd, then $32 \mid (a^{2} + 3)(a^{2} + 7)$.
7. Prove that if $a$ and $b$ are both odd integers, then $16 \mid a^{4} + b^{4} - 2$.
8. Prove the following:
   (a) The sum of the squares of two odd integers cannot be a perfect square.
   (b) The product of four consecutive integers is 1 less than a perfect square.
9. Establish that the difference of two consecutive cubes is never divisible by 2.
10. For a nonzero integer $a$, show that $gcd(a, 0) = \lvert a \rvert$, $gcd(a, a)= \lvert a \rvert$, and $gcd(a, 1) = 1$.
11. If a and b are integers, not both of which are zero, verify that
    $$gcd(a, b) = gcd(-a, b) = gcd(a, -b) = gcd(-a, -b)$$
12. Prove that, for a positive integer $n$ and any integer $a$, $gcd(a, a + n)$ divides $n$; hence, $gcd(a, a + 1) = 1$.
13. Given integers $a$ and $b$, prove the following:
    (a) There exist integers $x$ and $y$ for which $c = ax + by$ if and only if $gcd(a, b) \mid c.$
    (b) If there exist integers $x$ and $y$ for which $ax + by = gcd(a, b)$, then $gcd(x, y) = 1$.
14. For any integer $a$, show the following:
    (a) $gcd(2a + 1, 9a + 4) = 1$.
    (b) $gcd(5a + 2, 7a+ 3) = 1$.
    (c) If $a$ is odd, then $gcd(3a, 3a + 2) = 1$.
15. If $a$ and $b$ are integers, not both of which are zero, prove that $gcd(2a - 3b, 4a - 5b)$ divides $b$; hence, $gcd(2a + 3, 4a + 5) = 1$.
16. Given an odd integer $a$, establish that
    $$a^{2} + (a + 2)^{2} + (a + 4)^{2} + 1$$
    is divisible by 12.
17. Prove that the expression $(3n)!/(3!)^n$ is an integer for all $n \geq 0$.
18. Prove: The product of any three consecutive integers is divisible by 6; the product of any four consecutive integers is divisible by 24; the product of any five consecutive integers is divisible by 120.
    [Hint: See Corollary 2 to Theorem 2.4.]
19. Establish each of the assertions below:
    (a) If $a$ is an arbitrary integer, then $6 \mid a(a^2 + 11)$.
    (b) If $a$ is an odd integer, then $24 \mid a(a^2 - 1)$. [Hint: The square of an odd integer is of the form $8k + 1$.]
    (c) If $a$ and $b$ are odd integers, then $8 \mid (a^2 - b^2)$.
    (d) If $a$ is an integer not divisible by $2$ or $3$, then $24 \mid (a^2+23)$.
    (e) If $a$ is an arbitrary integer, then $360 \mid a^2(a^2 - 1)(a^2 - 4)$.
20. Confirm the following properties of the greatest common divisor: (a) If $gcd(a, b) = 1$, and $gcd(a, c) = 1$, then $gcd(a, bc)= 1$.
    [Hint: Because $1 = ax + by= au + cv$ for some $x$, $y$, $u$, $v$, $1 =(ax+ by)(au + cv) = a(aux + cvx + byu) + bc(yv)$.]
    (b) If $gcd(a, b) = 1$, and $c \mid a$, then $gcd(b, c) = 1$.
    (c) If $gcd(a, b) = 1$, then $gcd(ac, b) = gcd(c, b)$.
    (d) If $gcd(a, b) = 1$, and $c \mid a+ b$, then $gcd(a, c) = gcd(b, c) = 1$.
    [Hint: Let $d = gcd(a, c)$. Then $d \mid a$, $d \mid c$ implies that $d \mid (a+ b) - a$, or $d \mid b$.]
    (e) If $gcd(a, b) = 1$, $d \mid ac$, and $d \mid bc$, then $d \mid c$.
    (f) If $gcd(a, b) = 1$, then $gcd(a^2 , b^2 ) = 1$.
    [Hint: First show that $gcd(a, b^2 ) = gcd(a^2, b) = 1$.]
21. (a) Prove that if $d \mid n$, then $2^{d} - 1 \mid 2^{n} - 1$.
    [Hint: Use the identity $x^k - 1 = (x - 1)(x^{k - 1} + x^{k - 2} + · · · + x + 1)$.]
    (b) Verify that $2^35 - 1$ is divisible by 31 and 127.
22. Let $t_{n}$ denote the $n$th triangular number. For what values of $n$ does $t_{n}$ divide the sum $t_{1} + t_{2} + · · · + t_{n}$?
    [Hint: See Problem 1(c), Section 1.1.]

My Solutions (Q1 - Q23)

Q1

If $a \mid b$, show that $(-a) \mid b$, $a \mid (-b)$, and $(-a) \mid (-b)$.

Because $a \mid b$, we have $b = ka$ for some integer $k$. Thus $b = (-k)(-a)$ implies $(-a) \mid b$.

Similarly, $-b = (-k)a$ implies $a \mid -b$.

Also, $-b = k(-a)$ implies $(-a) \mid (-b)$.

Q2

Given integers $a, b, c, d$, verify the following:

(a) lf $a \mid b$, then $a \mid bc$.
(b) If $a \mid b$ and $a \mid c$, then $a^2 \mid bc$.
(c) $a \mid b$ if and only if $ac \mid bc$, where $c \neq 0$.
(d) If $a \mid b$ and $c \mid d$, then $ac \mid bd$.

(a)

Because $a \mid b$, $b = ka$ for some integer $k$. Then $bc = kac = (kc)a$ where $kc$ is an integer. Therefore, $a \mid bc$.

(b)

Because $a \mid b$, $b = ka$ for some integer $k$. Because $a \mid c$, $c = ja$ for some integer $j$. Then we have $bc = (ka) \cdot (ja) = (kj)a^2$ where $kj$ is an integer. Therefore, $a^2 \mid bc$.

(c)

$\to$

Because $a \mid b$, $b = ka$ for some integer $k$. Then $bc = kac = k(ac)$. Therefore, $ac \mid bc$.

$ \gets $

Because $ac \mid bc$, $bc = m(ac)$ for some integer $m$. Since $c \neq 0$, we divide both sides by $c$, which is $b = ma$. This implies $a \mid b$.

(d)

Because $a \mid b$ and $c \mid d$, we have $b = ka$ and $d = mc$ for some integer $k$ and $m$. By multiplying $b$ and $c$, we have $bd = (ka) \cdot (mc) = (km) \ cdot (ac)$ where $kc$ is an integer. Therefore, $ac \mid bd$.

Q3

Prove or disprove: If $a \mid (b + c)$, then either $a \mid b$ or $a \mid c$.

Let $a = 3$, $b = 5$ and $c = 7$. We know $3 \mid (5 + 7) = 12$ but $3 \not \mid 5$ and $3 \not \mid 7$. Therefore, we disproved the statement.

Q4

For $n \geq 1$, use mathematical induction to establish each of the following divisibility statements:

(a) $8 \mid 5^{2n} + 7$. [Hint: $5^{2(k+1)} + 7 = 5^{2}(5^{2k} + 7) + (7 - 5^{2} \cdot 7)$.]
(b) $15 \mid 2^{4n} - 1$.
(c) $5 \mid 3^{3n+1} + 2^{n+1}$.
(d) $21 \mid 4^{n+1} + 5^{2n-1}$.
(e) $24 \mid 2 \cdot 7^n + 3 \cdot 5^n - 5$.

(a)

Let $P(n)$ be the statement that $8 \mid 5^{2n} + 7$ for $n \geq 1$.

Base Case:

Consider $n = 1$, we have $8 \mid 5^{2} + 7 = 32$.

Induction Hypothesis:

Assume $P(k)$ is true for some integer $k$, which means $5^{2k} + 7 = 8m$ for some integer $m$.

Consider $n = k + 1$:

Hence, the fact that $P(k)$ is true implies that $P(k+1)$ is true.

Conclusion:

By Theorem 1.2 First Principle of Finite Induction, $P(n)$ is true for $n \geq 1$.

(b)

Let $P(n)$ be the statement that $15 \mid 2^{4n} - 1$ for $n \geq 1$.

Base Case:

Consider $n = 1$, we have $15 \mid 2^{4} - 1 = 15$.

Induction Hypothesis:

Assume $P(k)$ is true for some integer $k$, which means $2^{4k} - 1 = 15m$ for some integer $m$.

Consider $n = k + 1$:

Hence, the fact that $P(k)$ is true implies that $P(k+1)$ is true.

Conclusion:

By Theorem 1.2 First Principle of Finite Induction, $P(n)$ is true for $n \geq 1$.

(c)

Let $P(n)$ be the statement that $5 \mid 3^{3n+1} + 2^{n+1}$ for $n \geq 1$.

Base Case:

Consider $n = 1$, we have $5 \mid 3^{4} + 2^{2} = 85$.

Induction Hypothesis:

Assume $P(k)$ is true for some integer $k$, which means $3^{3n+1} + 2^{n+1} = 5m$ for some integer $m$.

Consider $n = k + 1$:

Hence, the fact that $P(k)$ is true implies that $P(k+1)$ is true.

Conclusion:

By Theorem 1.2 First Principle of Finite Induction, $P(n)$ is true for $n \geq 1$.

(d)

Let $P(n)$ be the statement that $21 \mid 4^{n+1} + 5^{2n-1}$ for $n \geq 1$.

Base Case:

Consider $n = 1$, we have $21 \mid 4^{1+1} + 5^{2-1} = 16 + 5 = 21$.

Induction Hypothesis:

Assume $P(k)$ is true for some integer $k$, which means $4^{k+1} + 5^{2k-1} = 21m$ for some integer $m$.

Consider $n = k + 1$:

Hence, the fact that $P(k)$ is true implies that $P(k+1)$ is true.

Conclusion:

By Theorem 1.2 First Principle of Finite Induction, $P(n)$ is true for $n \geq 1$.

(e)

Let $P(n)$ be the statement that $24 \mid 2 \cdot 7^n + 3 \cdot 5^n - 5$ for $n \geq 1$.

Base Case:

Consider $n = 1$, we have $24 \mid 2 \cdot 7 + 3 \cdot 5 - 5 = 14 + 15 - 5 = 24$.

Induction Hypothesis:

Assume $P(k)$ is true for some integer $k$, which means $2 \cdot 7^k + 3 \cdot 5^k - 5 = 24m$ for some integer $m$.

Consider $n = k + 1$:

Because $7^{k}$ and $5^{k}$ are both odd integers, so $7^{k} + 5^{k}$ will be an even number. It means that $7^{k} + 5^{k} = 2l$ for some integer $l$.

Hence, the fact that $P(k)$ is true implies that $P(k+1)$ is true.

Conclusion:

By Theorem 1.2 First Principle of Finite Induction, $P(n)$ is true for $n \geq 1$.

Q5

Prove that for any integer $a$, one of the integers $a$, $a+ 2$, $a + 4$ is divisible by 3.

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

For $3k$:

$a$ is divisible by 3.

For $3k + 1$:

$a + 2 = 3k + 1 + 2 = 3k + 3 = 3(k+1)$ which is also divisible by 3.

For $3k + 2$:

$a + 4 = 3k + 2 + 4 = 3k + 6 = 3(k + 2)$ which is also divisible by 3.

Q6

For an arbitrary integer $a$, verify the following:

(a) $2 \mid a(a + 1)$, and $3 \mid a(a + 1)(a + 2)$.
(b) $3 \mid a(2a^{2}+7)$.
(c) If $a$ is odd, then $32 \mid (a^{2} + 3)(a^{2} + 7)$.

(a)

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

For $2k$:

$a(a + 1) = 2k(2k+1)$

So, $2 \mid a(a + 1)$.

For $2k + 1$:

$a(a + 1) = (2k + 1)(2k + 1 + 1) = (2k + 1)(2k + 2) = 2(2k+1)(k+1)$

So, $2 \mid a(a+1)$.

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

For $3m$:

$a(a + 1)(a + 2) = 3m(3m + 1)(3m + 2)$

So, $3 \mid a(a + 1)(a + 2)$.

For $3m + 1$:

So, $3 \mid a(a + 1)(a + 2)$.

For $3m + 2$:

So, $3 \mid a(a + 1)(a + 2)$.

Therefore, for arbitrary integer $a$, $2 \mid a(a + 1)$, and $3 \mid a(a + 1)(a + 2)$.

Q7

Prove that if $a$ and $b$ are both odd integers, then $16 \mid a^{4} + b^{4} - 2$.

By Theorem 2.1 Division Algorithm, we can write $a$ and $b$ in the form of $2k + 1$ and $2j + 1$ for some integer $k$ and $j$.

Because $16 \mid 16(k^{4} + j^{4}) + 32(k^{3} + j^{3})$, we only need to consider the terms $24k^{2} + 8k + 24j^{2} + 8j$.

Without loss of generality, we can only consider cases for $24k^{2} + 8k$.

If $k$ is an odd integer, by Theorem 2.1 Division Algorithm, we can write $k$ in the form of $2m$ and $2m + 1$ for some integer $m$.

For $2m$:

So, $16 \mid 24k^{2} + 8k$ if $k$ is an even integer.

For $2m+ 1$:

So, $16 \mid 24k^{2} + 8k$ if $k$ is an odd integer. Thus $16 \mid 24k^{2} + 8k + 24j^{2} + 8j$.

Therefore, if $a$ and $b$ are both odd integers, then $16 \mid a^{4} + b^{4} - 2$.

Q8

Prove the following:
(a) The sum of the squares of two odd integers cannot be a perfect square.
(b) The product of four consecutive integers is 1 less than a perfect square.

(a)

Let $a$ and $b$ be the two odd integers. We start to prove by contradiction. Assume $a^{2} + b^{2}  = m^{2}$ for some integer $m$.

Because $a$ and $b$ are odd, by Theorem 2.1 Division Algorithm, we can write $a$ and $b$ in the form of $2k + 1$ and $2j + 1$.

If $m$ is odd:

By Theorem 2.1 Division Algorithm, we can write $m$ in the form of $2n + 1$.

$m^{2} = (2n + 1)^{2} = 4n^{2} + 4n + 1 = 4(n^{2} + n) + 1$ which conflicts with the form above by Theorem 2.1 Division Algorithm.

If $m$ is even:

$m^{2} = (2n )^{2} = 4n^{2}$ which also conflicts with the form above by Theorem 2.1 Division Algorithm.

Therefore, the sum of the squares of two odd integers cannot be a perfect square.

(b)

In this question, I also want to explain what I think for some key steps. I think that will help you to better understand how I come up with this solution.

We let the second integer be $a$. Let the perfect square be $m^{2}$ for some integer $m$. The product of 4 consecutive integers will then be:

The value should be the same as the following if the statement is true.

(Thoughts: At this point, we know that we need to make the (1) becomes the product of two integers where their values must be close.

In order to do that, the best way to combine the terms will be calculating $a(a+1)$ and $(a-1)(a+2)$.)

Thus $(a - 1)(a)(a + 1)(a + 2) = (a^{2} + a)(a^{2} + a - 2)$.

(Thoughts: (a^{2} + a) and (a^{2} + a - 2) have a difference of 2, so we know we succeeded.)

$(a^{2} + a)(a^{2} + a - 2) = [(a^{2} + a - 1) + 1][(a^{2} + a - 1) - 1]$.

Therefore, we know $(a - 1)(a)(a + 1)(a + 2) + 1 = (a^{2} + a - 1)^{2}$, which proves the statement.

Q9

Establish that the difference of two consecutive cubes is never divisible by 2.

Let the first cube be $a^{3}$ for some integer $a$.

From Q6(a), we know $2 \mid a(a+1)$, which means the term $3a(a+1)$ is an even integer. So, $3a(a + 1) + 1$ will be an odd integer.

Therefore, the difference of two consecutive cubes is never divisible by 2.

Q10

For a nonzero integer $a$, show that $gcd(a, 0) = \lvert a \rvert$, $gcd(a, a)= \lvert a \rvert$, and $gcd(a, 1) = 1$.

Proof for $gcd(a, 0) = \lvert a \rvert$:

Because $a$ is a nonzero integer, so $\lvert a \rvert \gt 0$. Also, $\lvert a \rvert \mid a$ and $\lvert a \rvert \mid 0$.

Let $c$ be another common divisor. We know $c \mid a$. By Theorem 2.2(f), we have $\lvert c \rvert \leq \lvert a \rvert$. Since $c \leq \lvert c \rvert$, we have $c \leq \lvert a \rvert$.

Therefore, by the definition of GCD (Definition 2.2), $gcd(a, 0) = \lvert a \rvert$.

Proof for $gcd(a, a) = \lvert a \rvert$:

Similarly, $a$ is a nonzero integer, so $\lvert a \rvert \gt 0$. Also, $\lvert a \rvert \mid a$.

Let $c$ be another common divisor. We know $c \mid a$. By Theorem 2.2(f), we have $\lvert c \rvert \leq \lvert a \rvert$. Since $c \leq \lvert c \rvert$, we have $c \leq \lvert a \rvert$.

Therefore, by the definition of GCD (Definition 2.2), $gcd(a, a) = \lvert a \rvert$.

Proof for $gcd(a, 1) = 1$:

Similarly, we know $1 \gt 0$. Also, $1 \mid a$ and $1 \mid 1$.

Let $c$ be another common divisor. We know $c \mid a$ and $c \mid 1$. By Theorem 2.2(f), we have $\lvert c \rvert \leq 1$. The only possible integers for $c$ will only be $-1$, $0$, or $1$, which are all less than or equal to $1$. So, $c \leq 1$.

Therefore, by the definition of GCD (Definition 2.2), $gcd(a, 1) = 1.

Q11

If a and b are integers, not both of which are zero, verify that

Proof for $gcd(a,b) = gcd(-a,b)$:

Let $d = gcd(a,b)$ and $e = gcd(-a,b)$.

Because $d \mid a \to d \mid -a$ and $d \mid b$, $d$ is a common divisor of $-a$ and $b$. So, $d \leq e$.

On the other hand, $e \mid -a \to e \mid a$ and $e \mid b$, $e$ is a common divisor of $a$ and $b$. So, $e \leq d$.

Therefore, $d = e$ which is $gcd(a, b) = gcd(-a, b)$.

Proof for $gcd(-a,b) = gcd(a,-b)$:

Let $f = gcd(a, -b)$.

Because $e \mid -a \to e \mid a$ and $e \mid b \to e \mid -b$, $e$ is a common divisor of $a$ and $-b$. So, $e \leq f$.

On the other hand, $f \mid a \to f \mid -a$ and $f \mid -b \to f \mid b$, $f$ is a common divisor of $-a$ and $b$. So, $f \leq e$.

Therefore, $e = f$ which is $gcd(-a, b) = gcd(a, -b)$.

Proof for $gcd(a,-b) = gcd(-a, -b)$:

Let $g = gcd(-a, -b)$:

Because $f \mid a \to f \mid -a$ and $f \mid -b$, $f$ is a common divisor of $-a$ and $-b$. So, $f \leq g$.

On the other hand, $g \mid -a \to g \mid a$ and $g \mid -b$, $g$ is a common divisor of $a$ and $-b$. So, $g \leq f$.

Therefore, $f = g$ which is $gcd(a, -b) = gcd(-a, -b)$.

Thus we prove that:

Q12

Prove that, for a positive integer $n$ and any integer $a$, $gcd(a, a + n)$ divides $n$; hence, $gcd(a, a + 1) = 1$.

Let $d = gcd(a, a + n)$. We know $d \mid a$ and $d \mid a + n$. By Theorem 2.2(g), $d \mid a + n - a = n$. Thus $gcd(a, a + n) \mid n$.

Then we know $gcd(a, a + 1) \mid 1$. Also, by the Definition of GCD (Definition 2.2), $gcd(a, a + 1)$ is a positive integer.

Therefore, $gcd(a, a + 1) = 1$.

Q13

Given integers $a$ and $b$, prove the following:
(a) There exist integers $x$ and $y$ for which $c = ax + by$ if and only if $gcd(a, b) \mid c.$
(b) If there exist integers $x$ and $y$ for which $ax + by = gcd(a, b)$, then $gcd(x, y) = 1$.

(a)

$\to$

By Corollary of Theorem 2.3, the set $T = \{ax + by \ \vert \ x,y\ are\ integers\}$ is the set of all multiples of $gcd(a,b)$. So, $gcd(a,b) \mid c$.

$\gets$

Because $gcd(a,b) \mid c$, we know $c$ is a multiple of $gcd(a,b)$. By Corollary of Theorem 2.3,  $c$ lies in the set $T = \{ax + by \ \vert \ x,y\ are\ integers\}$. Therefore, there exist integers $x$ and $y$ for which $c = ax + by$.

(b)

Let $d = gcd(a,b)$ and $e = gcd(x,y)$.

We have:

where $\frac{a}{d}$ and $\frac{b}{d}$ are integers.

We know $e \mid x$ and $e \mid y$. By Theorem 2.2(g), $e \mid (\frac{a}{d})x + (\frac{b}{d})y = 1$.

By the Definition of GCD (Definition 2.2), $e$ is a positive integer.

Therefore, $gcd(x,y) = 1$.