Number Theory
Number Theory #2
08/23/11 03:20 PM
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.
Comments
Number Theory #1
08/08/11 10:08 PM
I've started reading through An Introduction to Number Theory, by Harold Stark, and working the problems. My habit so far has been to go downstairs before bedtime, do some cardio, then open the text and work a problem or two, including the theorems proven in the text. I try to do them before seeing how they are done in the book. So far, I've been going to bed frustrated by my slowness to solve some of the problems. But sleeping on it must be doing some good, since inspiration has come in the morning. As I'm only in chapter one, this could prove to be a very long voyage. If I had to do this under deadline for a class, I'd be in trouble (although miscellaneous exercise 9 was trivial).
Misc. Ex. #7: Show that if p ∤ n for all primes p ≤ ∛n, then n is either a prime or a product of two primes.
If p is not prime, then it is a composite number of the form f1 * f2 * … * fk. From the problem statement, f1 > ∛n, therefore f1 * f1 * f1 > n. So if n is prime, it is the product of at most two primes, f1 and f2, where f1 <= f2.
Misc Ex. #8: Let p and q be consecutive odd primes from the list 2, 3, 5, 7, …. Show that p + q has at least three, not necessarily unique, prime divisors. Example: 7 + 11 = 18 = 2 * 3 * 3.
Since p and q are odd primes, p = 2m + 1; q = 2n + 1. p < q ⇒ m < n.
Then p + q = 2m + 1 + 2n + 1 = 2(m + n + 1).
So 2 is one divisor of p + q.
Suppose m + n + 1 is even. Then m + n + 1 = 2r, and p + q = 2*2*r. Since the smallest possible p is 3, the smallest m is 1 and, likewise, the smallest n is 2; so the smallest m + n + 1 is 4. This shows r >= 2.
Suppose m + n + 1 is odd. For the theorem to be true, m + n + 1 must be composite. Assume it's the prime P'. Since m < n,
⇒ m + m + 1 < m + n + 1 < n + n + 1
⇒ 2m + 1 < m + n + 1 < 2n + 1
⇒ p < P' < q.
But, p and q are consecutive primes, so P' cannot be prime. Therefore, when m + n + 1 is odd it is composite.
Misc Ex. #9: Note that
152 = 225, 352 = 1225, 852 = 7225, 1052 = 11025
(the underlined portions are for emphasis only). Find a rule for squaring an integer ending in 5 and prove that it works.
Let n = (m * 10) + 5. Then
⇒ n2 = ((m * 10) + 5) * ((m * 10) + 5)
⇒ (10m * 10m) + 10m*5 + 10m*5 + 25
⇒ 100m2 + 100m + 25
⇒ 100m(m + 1) + 25
Check: 123452 = 100*1234*1235 + 25 = 152399000 + 25 = 152399025 = 123452
On to chapter 2.
Misc. Ex. #7: Show that if p ∤ n for all primes p ≤ ∛n, then n is either a prime or a product of two primes.
If p is not prime, then it is a composite number of the form f1 * f2 * … * fk. From the problem statement, f1 > ∛n, therefore f1 * f1 * f1 > n. So if n is prime, it is the product of at most two primes, f1 and f2, where f1 <= f2.
Misc Ex. #8: Let p and q be consecutive odd primes from the list 2, 3, 5, 7, …. Show that p + q has at least three, not necessarily unique, prime divisors. Example: 7 + 11 = 18 = 2 * 3 * 3.
Since p and q are odd primes, p = 2m + 1; q = 2n + 1. p < q ⇒ m < n.
Then p + q = 2m + 1 + 2n + 1 = 2(m + n + 1).
So 2 is one divisor of p + q.
Suppose m + n + 1 is even. Then m + n + 1 = 2r, and p + q = 2*2*r. Since the smallest possible p is 3, the smallest m is 1 and, likewise, the smallest n is 2; so the smallest m + n + 1 is 4. This shows r >= 2.
Suppose m + n + 1 is odd. For the theorem to be true, m + n + 1 must be composite. Assume it's the prime P'. Since m < n,
⇒ m + m + 1 < m + n + 1 < n + n + 1
⇒ 2m + 1 < m + n + 1 < 2n + 1
⇒ p < P' < q.
But, p and q are consecutive primes, so P' cannot be prime. Therefore, when m + n + 1 is odd it is composite.
Misc Ex. #9: Note that
152 = 225, 352 = 1225, 852 = 7225, 1052 = 11025
(the underlined portions are for emphasis only). Find a rule for squaring an integer ending in 5 and prove that it works.
Let n = (m * 10) + 5. Then
⇒ n2 = ((m * 10) + 5) * ((m * 10) + 5)
⇒ (10m * 10m) + 10m*5 + 10m*5 + 25
⇒ 100m2 + 100m + 25
⇒ 100m(m + 1) + 25
Check: 123452 = 100*1234*1235 + 25 = 152399000 + 25 = 152399025 = 123452
On to chapter 2.