Number Theory #1

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 pn, 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.
Comments