Beginning How To Prove It

I just finished working through the introduction of How To Prove It. The book presents a structured approach to reading and writing proofs, that is analogous to how we compose elements like if-then statements and do-while loops to write computer programs. I’m personally finding the book very promising, and highly recommend working through the introduction to get a taste of the kind of mental process this provokes.

Aside: I think the books that make the most impact on me are the ones with carefully designed exercises that really test how thorough you believe you are. This also goes to show that I really rely on exercises to force deep reading; another FIXME item for my flawed reading habits.

It looks like the only solutions and discussions on this book are over at Himanshu Gupta’s blog; I’ve found some real gems in the comment discussions there, so they’re now mandatory post-exercise readings for me.

Notes

Below are my notes while working through the introductory exercise:

Question 1

This questions builds on conjecture 2,

If n is not prime, then is not prime.

and its corresponding proof, which shows us how to construct the factors and of from the factors and of .

a. Factor into a product of two smaller positive integers.

b. Find an integer such that and divides .

This is equivalent to stating that , where . Let . Then,

Question 2

Make some conjecture about the values of for which is prime or is prime.

Let’s make a table.

n n prime? prime? prime?
1 2 1 N Y N
2 8 5 Y N Y
3 26 19 Y N Y
4 80 65 N N N
5 242 211 Y N Y
6 728 665 N N N
7 2186 2059 Y N Y

Conjectures:

  1. If is prime, then is prime.
  2. If is not prime, then is not prime.
  3. If , then is not prime.

Question 3

The proof of theorem 3 gives a method of finding a prime number different from any in a given list of prime numbers

  • Use this method to find a prime number different from 2, 3, 5 and 7.
  • Use this method to find a prime number different from 2, 5 and 11.

Theorem 3 proves that there is an infinite number of primes using 2 cases.

Given a list of primes , if , either:

  • is prime, and is hence not in the finite list , or
  • is a product of primes and . Since is not divisible by , or are not in the finite list .

So we have 2 ways of finding a prime that is not in the given list of primes:

  • , and is prime, so it is the prime we need.
  • , and is not prime, so and are the primes we need.

Using this, we have:

  • , 211 is a prime not in the list.
  • , 3 and 37 are primes not in the list.

The comments in Himanshu’s blog brought forth an interesting related conjecture; if are primes, then is always prime?

The numbers of the form are called Euclid numbers. The conjecture is false, as seen in the counter-example of the first composite Euclid number.

Question 4

Find 5 consecutive integers that are not prime.

This is a direct application of the theorem 4.

Required sequence: 722, 723, 724, 725, 726

Question 5

Use the table in figure 1 and the discussions on p.5 to find two more perfect numbers.

This is a direct application of the theorem proven by Euler,

If is prime, then is perfect.

Using this theorem, we have the following:

Question 6

The sequence 3, 5, 7 is a list of three prime numbers such that each pair of adjacent numbers in the list differ by 2. Are there any more such “triplet primes”?

Such a triplet can only occur among a triplet of odd numbers (since 2 is the only even prime number).

Among consecutive odd numbers, apart from 2, 3, 5 and 3, 5, 7, there is no such triplet. Every third odd number greater than 15 is a multiple of 3, so we can never get a sequence of 3 odd numbers such that they are all prime; at least one of them will have 3 as a factor.