Number Theory #1
08/08/11 10:08 PM Filed in: Number Theory
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.
blog comments powered by Disqus