Elementary Number Theory Problems 2.4 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 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)$.

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

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

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)

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

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

(b)

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

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

(c)

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

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

(d)

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

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

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

Therefore, by Theorem 2.7:

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:

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

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

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 = 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$.