Number Theory #2
08/23/11 03:20 PM Filed in: Number Theory
This stuff is killing me. The solutions, so far, turn out to be simple. But finding them is a struggle.
2.1 #1: Show that if a, b, and c are pairwise relatively prime, then (a, b, c) = 1.
Since a, b, and c are pairwise relatively prime then (a, b) = 1, (b, c) = 1, and (a, c) = 1.
(a, b, c) = ((a, b), c) = (1, c) = 1
I suppose I have to show that (a, b, c) = ((a, b), c). Let (a, b) = d and (d, c) = e. e | d and d | a → e | a, since d = ke, a = ld → a = lke → e | a. Similarly, e | b. Since e | a, e | b, and e | c, e is a common denominator of (a, b, c). So it must be shown that it is the largest. But I don't know how to do this, except by using set theory. Let A be the set of the factors of a, that is, a is the product of the elements in A. Likewise sets B and C. There is at least one element in A, B, and C, since 1 is a factor. Then (a, b) is the product of the elements A ∩ B. Likewise, (a, b, c) is the product of the elements A ∩ B ∩ C. A ∩ B ∩ C → (A ∩ B) ∩ C, so (a, b, c) = ((a, b), c).
Another proof, which is probably closer in spirit to what the book has in mind, is to let (a, b, c) = d. Then d | a and d | b. Since (a, b) = 1, by Theorem 2.3 d | 1 and therefore d = 1.
2.1 #2: Use the Euclidean algorithm to find the greatest common divisor of:
2.1 #3: Express (17, 37) as a linear combination of 17 and 37.
(17, 37) = 1 → 17r + 37s = 1
37 = 2 * 17 + 3
17 = 5 * 3 + 2
3 = 2 * 1 + 1
1 = 3 - 2
= (37 - 2 * 17) - (17 - 5 * 3)
= (37 - 2 * 17) - (17 - (5 * (37 - 2 * 17)))
= (37 - 2 * 17) - (17 - 5 * 37 + 10 * 17)
= 37 - 2*17 - 17 + 5 * 37 - 10 * 17
= 6 * 37 - 13 * 17
2.1 #4, 5, and 6: These are all variations on problem #3 since (399, 703) = 19, (547, 623) = 1, and (398, 600) = 2. Since this is mechanical, I'd rather spend the time writing code to do the work.
(399, 703) = 19 = -7 * 399 + 4 * 703
(547, 623) = 1 = -41 * 547 + 36 * 623
(398, 600) = 2 = -101 * 398 + 67 * 600
2.1 #7: Find integers r and s such that 922r + 2163s = 7.
This is interesting, since (922, 2163) = 1. For this case, by the method in problems 3-6, one solution for 922r + 2163s = 1 is 922*556 - 2163*237 = 1. Then 7*(922*556 - 2163*237) = 7 → 922*3892 - 2163*1659 = 7.
2.1 #8: Are there integers r and s such that 1841r + 3647s = 1? Why?
(1841, 3647) = 7, so 1841r + 3647s = 7(263r + 521s) → every solution to 1841r + 3647s is a multiple of 7, which 1 is not.
2.1 #9: Show that if there is no prime p such that p | a and p | b, then (a, b) = 1.
Let (a, b) = d. If d is composite, then d is divisible by a prime, q. Then q | d → q | a and q | b (Theorem 1.3). But this contradicts the premise so d is not composite. d must be prime. But this too contradicts the premise, therefore d = 1.
2.1 #11: Are the integers 101, 209, 283, and 341 pairwise relatively prime? No, (209, 341) = 11.
2.1 #12: Show that if p is prime and a is an integer then either (a, p) = 1 or (a, p) = p.
Suppose a = 0. Then (0, p) = p, since p | 0.
Suppose 0 < a < p. Then (a, p) = 1, since p is prime (a ∤ p) and (p ∤ a) since p > a.
Suppose a = p, then (a, p) = p.
Suppose a > p. If a is prime, then (a, p) = 1, since by definition of primes, (p ∤ a). If a is composite and (p ∣ a), then (a, p) = p. If a is composite and (p ∤ a), then (a, p) = 1.
2.1 #13: Use Theorem 2.4(c) to show that a fraction m / n can always be reduced to lowest terms.
Let (m, n) = d. Then (m / d) / (n / d) = m / n and m / d <= m, n / d <= n. So we have to show that m / d and n / d are the lowest possible terms.
Assume q, such that m / q < m / d and n / q < n / d. Then md < mq → d < q. Since q | m and q | n, by Theorem 2.3 q | d → q <= d, which is a contradiction.
2.1 #1: Show that if a, b, and c are pairwise relatively prime, then (a, b, c) = 1.
Since a, b, and c are pairwise relatively prime then (a, b) = 1, (b, c) = 1, and (a, c) = 1.
(a, b, c) = ((a, b), c) = (1, c) = 1
I suppose I have to show that (a, b, c) = ((a, b), c). Let (a, b) = d and (d, c) = e. e | d and d | a → e | a, since d = ke, a = ld → a = lke → e | a. Similarly, e | b. Since e | a, e | b, and e | c, e is a common denominator of (a, b, c). So it must be shown that it is the largest. But I don't know how to do this, except by using set theory. Let A be the set of the factors of a, that is, a is the product of the elements in A. Likewise sets B and C. There is at least one element in A, B, and C, since 1 is a factor. Then (a, b) is the product of the elements A ∩ B. Likewise, (a, b, c) is the product of the elements A ∩ B ∩ C. A ∩ B ∩ C → (A ∩ B) ∩ C, so (a, b, c) = ((a, b), c).
Another proof, which is probably closer in spirit to what the book has in mind, is to let (a, b, c) = d. Then d | a and d | b. Since (a, b) = 1, by Theorem 2.3 d | 1 and therefore d = 1.
2.1 #2: Use the Euclidean algorithm to find the greatest common divisor of:
- 77 and 91 → 7
- 182 and 442 → 26
- 2311 and 3701 → 1
2.1 #3: Express (17, 37) as a linear combination of 17 and 37.
(17, 37) = 1 → 17r + 37s = 1
37 = 2 * 17 + 3
17 = 5 * 3 + 2
3 = 2 * 1 + 1
1 = 3 - 2
= (37 - 2 * 17) - (17 - 5 * 3)
= (37 - 2 * 17) - (17 - (5 * (37 - 2 * 17)))
= (37 - 2 * 17) - (17 - 5 * 37 + 10 * 17)
= 37 - 2*17 - 17 + 5 * 37 - 10 * 17
= 6 * 37 - 13 * 17
2.1 #4, 5, and 6: These are all variations on problem #3 since (399, 703) = 19, (547, 623) = 1, and (398, 600) = 2. Since this is mechanical, I'd rather spend the time writing code to do the work.
(399, 703) = 19 = -7 * 399 + 4 * 703
(547, 623) = 1 = -41 * 547 + 36 * 623
(398, 600) = 2 = -101 * 398 + 67 * 600
2.1 #7: Find integers r and s such that 922r + 2163s = 7.
This is interesting, since (922, 2163) = 1. For this case, by the method in problems 3-6, one solution for 922r + 2163s = 1 is 922*556 - 2163*237 = 1. Then 7*(922*556 - 2163*237) = 7 → 922*3892 - 2163*1659 = 7.
2.1 #8: Are there integers r and s such that 1841r + 3647s = 1? Why?
(1841, 3647) = 7, so 1841r + 3647s = 7(263r + 521s) → every solution to 1841r + 3647s is a multiple of 7, which 1 is not.
2.1 #9: Show that if there is no prime p such that p | a and p | b, then (a, b) = 1.
Let (a, b) = d. If d is composite, then d is divisible by a prime, q. Then q | d → q | a and q | b (Theorem 1.3). But this contradicts the premise so d is not composite. d must be prime. But this too contradicts the premise, therefore d = 1.
2.1 #11: Are the integers 101, 209, 283, and 341 pairwise relatively prime? No, (209, 341) = 11.
2.1 #12: Show that if p is prime and a is an integer then either (a, p) = 1 or (a, p) = p.
Suppose a = 0. Then (0, p) = p, since p | 0.
Suppose 0 < a < p. Then (a, p) = 1, since p is prime (a ∤ p) and (p ∤ a) since p > a.
Suppose a = p, then (a, p) = p.
Suppose a > p. If a is prime, then (a, p) = 1, since by definition of primes, (p ∤ a). If a is composite and (p ∣ a), then (a, p) = p. If a is composite and (p ∤ a), then (a, p) = 1.
2.1 #13: Use Theorem 2.4(c) to show that a fraction m / n can always be reduced to lowest terms.
Let (m, n) = d. Then (m / d) / (n / d) = m / n and m / d <= m, n / d <= n. So we have to show that m / d and n / d are the lowest possible terms.
Assume q, such that m / q < m / d and n / q < n / d. Then md < mq → d < q. Since q | m and q | n, by Theorem 2.3 q | d → q <= d, which is a contradiction.
blog comments powered by Disqus