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

My solutions for Burton's Elementary Number Theory Problems 2.4 (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 this book 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.

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.4 (p.31 - p.32)

1. Find $gcd(143, 227)$, $gcd(306, 657)$, and $gcd(272, 1479)$
2. Use the Euclidean Algorithm to obtain integers x and y satisfying the following:
(a) $gcd(56, 72) = 56x + 72y$.
(b) $gcd(24, 138) = 24x + 138y$.
(c) $gcd(119, 272) = 119x + 272y$.
(d) $gcd(l769, 2378) = 1769x + 2378y$.
3. Prove that if $d$ is a common divisor of $a$ and $b$, then $d = gcd(a, b)$ if and only if $gcd(a/d, b/d) = 1$. [Hint: Use Theorem 2.7.]
4. Assuming that $gcd(a, b) = 1$, prove the following:
(a) $gcd(a + b, a - b) = 1$ or $2$. [Hint: Let $d = gcd(a + b, a - b)$ and show that $d \mid 2a$, $d \mid 2b$, and thus that $d \leq gcd(2a, 2b) = 2\ gcd(a, b)$.]
(b) $gcd(2a + b, a+ 2b) = 1$ or $3$.
(c) $gcd(a + b, a2 + b2) = 1$ or $2$. [Hint: $a^2 + b^2 =(a+ b)(a - b) + 2b^2$.]
(d) $gcd(a + b, a^2 - ab+ b^2) = 1$ or $3$.
[Hint: $a^2 - ab+ b^2 = (a+ b)^2 - 3ab$.]
5. For $n \geq 1$, and positive integers $a$, $b$, show the following:
(a) If $gcd(a, b) = 1$, then $gcd(a^n, b^n) = 1$.
[Hint: See Problem 20(a), Section 2.3.] (I changed it to "2.3." since the book has a typo here)
(b) The relation $a^n \mid b^n$ implies that $a \mid b$.
[Hint:Put $d = gcd(a,b)$ and write $a = rd$, $b = sd$, where $gcd(r,s) = 1$. By part (a), $gcd(r^n, s^n) = 1$. Show that $r = 1$, whence $a = d$.]
6. Prove that if $gcd(a, b) = 1$, then $gcd(a + b, ab)= 1$.
7. For nonzero integers $a$ and $b$, verify that the following conditions are equivalent:
(a) $a \mid b$.
(b) $gcd(a, b) = \lvert a \rvert$.
(c) $lcm(a, b) = \lvert b \rvert$.
8. Find $lcm(143, 227)$, $lcm(306, 657)$, and $lcm(272, 1479)$.
9. Prove that the greatest common divisor of two positive integers divides their least common multiple.
10. Given nonzero integers $a$ and $b$, establish the following facts concerning $lcm(a, b)$:
(a) $gcd(a, b) = lcm(a, b)$ if and only if $a = \pm b$.
(b) If $k \gt 0$, then $lcm(ka, kb)= k\ lcm(a, b)$.
(c) If $m$ is any common multiple of $a$ and $b$, then $lcm(a, b) \mid m$. [Hint: Put $t = lcm(a, b)$ and use the Division Algorithm to write $m = qt + r$, where $0 \leq r \lt t$. Show that $r$ is a common multiple of $a$ and $b$.]
11. Let $a$, $b$, $c$ be integers, no two of which are zero, and $d = gcd(a, b, c)$. Show that
$$d = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) = gcd(gcd(a, c), b)$$
12. Find integers $x$, $y$, $z$ satisfying $gcd(198, 288, 512) = 198x + 288y + 512z$
[Hint: Put $d = gcd(198, 288)$. Because $gcd(198, 288, 512) = gcd(d, 512)$, first find integers u and v for which $gcd(d, 512) =du+ 512v$.]

## My Solutions (Q1 - Q12)

### Q1

Find $gcd(143, 227)$, $gcd(306, 657)$, and $gcd(272, 1479)$.

$$$$\begin{split} 227 & = 1 \cdot 143 + 84 \\ 143 & = 1 \cdot 84+ 59 \\ 84 & = 1 \cdot 59 + 25 \\ 59 & = 2 \cdot 25 + 9 \\ 25 & = 2 \cdot 9 + 7 \\ 9 & = 1 \cdot 7 + 2 \\ 7 & = 3 \cdot 2 + 1 \\ 2 & = 2 \cdot 1+ 0 \end{split} \nonumber$$$$

Therefore, $gcd(143, 227)$ = 1.

$$$$\begin{split} 657 & = 2 \cdot 306 + 45 \\ 306 & = 6 \cdot 45 + 36\\ 45 & = 1 \cdot 36 + 9 \\ 36 & = 4 \cdot 9+ 0 \end{split} \nonumber$$$$

Therefore, $gcd(306, 657)$ = 9.

$$$$\begin{split} 1479 & = 5 \cdot 272+ 119 \\ 272 & = 2 \cdot 119 + 34 \\ 119 & = 3 \cdot 34+ 17 \\ 34 & = 2 \cdot 17+ 0 \end{split} \nonumber$$$$

Therefore, $gcd(272, 1479)$ = 17.

### Q2

Use the Euclidean Algorithm to obtain integers x and y satisfying the following:
(a) $gcd(56, 72) = 56x + 72y$.
(b) $gcd(24, 138) = 24x + 138y$.
(c) $gcd(119, 272) = 119x + 272y$.
(d) $gcd(l769, 2378) = 1769x + 2378y$.

#### (a)

$$$$\begin{split} 72 & = 1 \cdot 56 + 16 \\ 56 & = 3 \cdot 16 + 8 \\ 16 & = 2 \cdot 8 + 0 \\ \end{split} \nonumber$$$$

Therefore, $gcd(56, 72) = 8$. By using the extended Euclidean Algorithm:

$$$$\begin{split} 8 & = 56 - 16 \cdot 3 \\ & = 56 - (72-56) \cdot 3 \\ & = 56 \cdot (4) + 72 \cdot(-3) \end{split} \nonumber$$$$

We get one possible solution where $x = 4$ and $y = -3$.

#### (b)

$$$$\begin{split} 138 & = 5 \cdot 24 + 18 \\ 24 & = 1 \cdot 18 + 6 \\ 18 & = 3 \cdot 6 + 0 \end{split} \nonumber$$$$

Therefore, $gcd(24, 138) = 6$. By using the extended Euclidean Algorithm:

$$$$\begin{split} 6 & = 24 - 18 \\ & = 24 - (138 - 24 \cdot 5) \\ & = 24 \cdot 6 - 138 \\ & = 24 \cdot 6 + 138 \cdot (-1) \end{split} \nonumber$$$$

We get one possible solution where $x = 6$ and $y = -1$.

#### (c)

$$$$\begin{split} 272 & = 2 \cdot 119 + 34 \\ 119 & = 3 \cdot 34 + 17 \\ 34 & = 2 \cdot 17 + 0 \end{split} \nonumber$$$$

Therefore, $gcd(119,272) = 17$. By using the extended Euclidean Algorithm:

$$$$\begin{split} 17 & = 119 - 3 \cdot 34 \\ & = 119 - 3 \cdot (272 - 2 \cdot 119) \\ & = 119 \cdot 7 - 272 \cdot 3 \\ & = 119 \cdot 7 + 272 \cdot (-3) \end{split} \nonumber$$$$

We get one possible solution where $x = 7$ and $y = -3$.

#### (d)

$$$$\begin{split} 2378 & = 1 \cdot 1769 + 609 \\ 1769 & = 2 \cdot 609 + 551 \\ 609 & = 1 \cdot 551 + 58 \\ 551 & = 9 \cdot 58 + 29 \\ 58 & = 2 \cdot 29 + 0 \end{split} \nonumber$$$$

Therefore, $gcd(1769,2378) = 29$. By using the extended Euclidean Algorithm:

$$$$\begin{split} 29 & = 551 - 9 \cdot 58 \\ & = 551 - 9 \cdot (609 - 551)\\ & = 551 \cdot 10 - 609 \cdot 9 \\ & = (1769 - 2 \cdot 609) \cdot 10 - 609 \cdot 9 \\ & = 1769 \cdot 10 - 609 \cdot 29 \\ & = 1769 \cdot 10 - (2378 - 1769) \cdot 29 \\ & = 1769 \cdot 39 - 2378 \cdot 29 \\ & = 1769 \cdot 39 + 2378 \cdot (-29) \end{split} \nonumber$$$$

We get one possible solution where $x = 39$ and $y = -29$.

### Q3

Prove that if $d$ is a common divisor of $a$ and $b$, then $d = gcd(a, b)$ if and only if $gcd(a/d, b/d) = 1$. [Hint: Use Theorem 2.7.]

$\to$

If $d = gcd(a,b)$, $a = rd$ and $b = sd$ for some integer $r$ and $s$.

$$$$\begin{split} d & = gcd(a,b) \\ & = gcd(rd,sd) \end{split} \nonumber$$$$

By the Definition 2.2, we know $d$ is a positive integer, so $d \gt 0$.

Therefore, by Theorem 2.7:

$$$$\begin{split} d & = gcd(rd,sd) \\ & = d \cdot gcd(r,s) \\ \end{split} \nonumber$$$$

So, if we divide both sides by $d$, we have $gcd(r,s) = 1$, which means $gcd(a/d,b/d) = 1$.

$\gets$

Similarly, since $d \gt 0$, by using Theorem 2.7:

$$gcd(\frac{a}{d},\frac{b}{d}) = 1 \\ d \cdot gcd(\frac{a}{d},\frac{b}{d}) = d \\ gcd(d \cdot \frac{a}{d},d \cdot \frac{b}{d}) = d \\ gcd(a,b) = d$$

### Q4

Assuming that $gcd(a, b) = 1$, prove the following:

(a) $gcd(a + b, a - b) = 1$ or $2$. [Hint: Let $d = gcd(a + b, a - b)$ and show that $d \mid 2a$, $d \mid 2b$, and thus that $d \leq gcd(2a, 2b) = 2\ gcd(a, b)$.]
(b) $gcd(2a + b, a+ 2b) = 1$ or $3$.
(c) $gcd(a + b, a2 + b2) = 1$ or $2$. [Hint: $a^2 + b^2 =(a+ b)(a - b) + 2b^2$.]
(d) $gcd(a + b, a^2 - ab+ b^2) = 1$ or $3$.
[Hint: $a^2 - ab+ b^2 = (a+ b)^2 - 3ab$.]

#### (a)

Let $d = gcd(a+b, a-b)$, by Theorem 2.2 (g), we have $d \mid (a+b) + (a-b) = 2a$ and $d \mid (a+b) - (a-b) = 2b$.

Then, by Definition 2.2 (b):

$$d \leq gcd(2a, 2b)$$

Since $d \gt 0$ by Definition 2.2 and by Theorem 2.7:

$$d \leq gcd(2a, 2b) = 2 \times gcd(a,b)$$

Because $d$ is a positive integer, so $d = 1$ or $2$.

#### (b)

Let $d = gcd(2a + b, a + 2b)$, by Theorem 2.2 (g), we have $d \mid 2 \cdot (2a + b) - (a + 2b) = 3a$ and $d \mid 2 \cdot (a + 2b) - (2a + b) = 3b$.

Therefore, by Definition 2.2 (b), $d \leq gcd(3a, 3b)$.

Since $d \gt 0$ by Definition 2.2 and by Theorem 2.7:

$$d \leq gcd(3a, 3b) = 3 \times gcd(a,b)$$

$d = 1$, $2$ or $3$.

If $d = 2$, $d \mid 3a \to d \mid a$ by Euclid's Lemma (Theorem 2.5), because $gcd(2,3) = 1$. Similarly, $d \mid 3b \to d \mid b$.

But if $d = 2$, $d \mid a$ and $d \mid b$, then $gcd(a,b) \neq 1$, by contradiction, $d \neq 2$.

Therefore, $d = 1$ or $3$.

#### (c)

Let $d = gcd(a+b, a^2 + b^2)$.

Since $d \mid (a+b)$, so $d \mid (a+b)(a-b) = a^2 - b^2$.

As $d \mid a^2 + b^2$ and $d \mid a^{2} - b^{2}$, by Theorem 2.2 (g),

$d \mid (a^2 + b^2) + (a^{2} - b^{2}) = 2a^{2}$ and $d \mid (a^2 + b^2) - (a^{2} - b^{2}) = 2b^{2}$

So, $d \leq gcd(2a^{2}, 2b^{2})$ by Definition 2.2 (b).

We know $d > 0$ by Definition 2.2, then by Theorem 2.7:

$d \leq 2 \cdot gcd(a^{2}, b^{2})$

From Problems 2.3 Q20(f), we know "if $gcd(a,b) = 1$, then $gcd(a^{2}, b^{2})$."

Therefore, $d \leq 2 \cdot gcd(a^{2}, b^{2}) = 2 \cdot 1$, which means $d = 1$ or $2$.

#### (d)

Let $d = gcd(a+b, a^2 -ab + b^2)$. Because $d \mid a+b$, so $d \mid (a+b)^2$.

Because $a^2 - ab + b^2 = (a+b)^2 - 3ab$, so by Theorem 2.2 (g)

$d \mid a^2 - ab + b^2 - (a+b)^2 = (a+b)^2 - 3ab - (a+b)^2 = 3ab$

From Problem 2.3 Q20(d), we know "If $gcd(a,b) = 1$, and $c \mid a+b$, then $gcd(a,c) = gcd(b,c) = 1$."

Since $gcd(a,b) = 1$ and $d \mid a+b$, then $gcd(a,d) = gcd(b,d) = 1$.

By Euclid's Lemma, because $d \mid 3ab$ and $gcd(a,d) = 1$, so $d \mid 3b$.

Similarly, by applying Euclid's Lemma again, because $d \mid 3b$ and $gcd(b,d) = 1$, so $d \mid 3$.

By Definition 2.2, $d$ is a positive integer. Therefore, $d = 1$ or $3$.

### Q5

For $n \geq 1$, and positive integers $a$, $b$, show the following:

(a) If $gcd(a, b) = 1$, then $gcd(a^n, b^n) = 1$.
[Hint: See Problem 20(a), Section 2.3.] (I changed it to "2.3." since the book has a typo here)

(b) The relation $a^n \mid b^n$ implies that $a \mid b$.
[Hint:Put $d = gcd(a,b)$ and write $a = rd$, $b = sd$, where $gcd(r,s) = 1$. By part (a), $gcd(r^n, s^n) = 1$. Show that $r = 1$, whence $a = d$.]

#### (a)

Method 1, a simple proof provided by Dr. Koopa Koo:

Suppose $gcd(a^n, b^n)$ is not $1$. Let $p$ be the prime dividing $gcd(a^n, b^n)$. This means $p \mid a^n$. By Euclid's Lemma, $p \mid a$. Likewise, $p \mid b$ and this is a contradiction because $gcd(a, b) = 1$.

Method 2, my original proof which involves the hint and mathematical induction:

From Problems 2.3 Q20(a), we know that "If $gcd(a, b) = 1$, and $gcd(a, c) = 1$, then $gcd(a, bc)= 1$."

We can prove the statement by using mathematical induction.

Base Case:

For $n = 2$, we have proved it in Problems 2.3 Q20(f).

Induction Hypothesis:

Assume $gcd(a^k, b^k) = 1$ for some integer $k$.

Consider $n = k + 1$:

If $gcd(a^k, b^k) = 1$, then $gcd(a^k, b) = 1$. By Problems 2.3 Q20(a), we have $gcd(a^k, b^{k+1}) = 1$.

Similarly, we have $gcd(a^k, b^{k+1}) = gcd(b^{k+1},a^k) = 1$, so $gcd(b^{k+1}, a) = 1$. By applying Problems 2.3 Q20(a) again, we have $gcd(a^{k+1}, b^{k+1}) = 1$

Conclusion:

This proves the statement by induction.

#### (b)

Let $d = gcd(a,b)$, so we have $a = rd$ and $b = sd$ for some integer $r$ and $s$. By corollary 1 of Theorem 2.4, we have $gcd(r,s) = 1$. By part(a), we have $gcd(r^n, s^n) = 1$.

Since $a^n \mid b^n$, we have $r^n d^n \mid s^n d^n$, which implies $r^n \mid s^n$. Because $r^n \mid r^n$ and $r^n \mid s^n$, from Theorem 2.6, we have $r^n \mid gcd(r^n, s^n)$.

We then know $r^n \mid 1$, $r$ is an integer and $a$, $b$ are positive integers. So $r = 1$. It implies that $a = d$.

Therefore, $d \mid sd = b$ which means $a \mid b$.

### Q6

Prove that if $gcd(a, b) = 1$, then $gcd(a + b, ab)= 1$.

Let $d = gcd(a + b, ab)$. As $d \mid a + b$ and $d \mid ab$, we have $d \mid a(a + b) - ab = a^2 + ab - ab = a^2$ by Theorem 2.2 (g).

Similarly, $d \mid b(a + b) - ab = ab + b^2 - ab = b^2$.

Then we have $d \mid a^2$ and $d \mid b^2$. So, $d \leq gcd(a^2, b^2)$ by the Definition 2.2 (b).

Because $gcd(a,b) = 1$, from Problems 2.3 Q20(f), we have $gcd(a^2, b^2) = 1$.

Therefore, $d \leq 1$. By Definition 2.2 we know $d > 0$, so $d = 1$.

Subscribe