Warming up to Euclid’s Prime Numbers Proof

Euclid did prove that there are infinitely many primes, and it is a proof that we can all

understand. But it is first a good idea to mess around with ways to try to generate primes and ways to test for primes.

In class we looked at the sequence of numbers (1 x 2 x 3 x 4…x m) + 1 for different values of m. (In other words, 1 x 2 + 1, 1 x 2 x 3 + 1, 1 x 2 x 3 x 4 + 1, etc.)

After the first few, the answer was not prime. [If you were not there, try it out.]

Then we revised this using only primes in the product:

2 x 3 + 1 = 7… prime

2 x 3 x 5 + 1 = 31… prime

2 x 3 x 5 x 7 + 1 = 211… prime

2x3x5x7x11+1 = 2311… prime

Looking better. I asked for your confidence that this process would lead to a prime.

We agreed that 2311 could not be evenly divisible by 2, 3, 5, 7, or 11. WHY NOT? Make sure you understand why not.

Can you tell, from how 2311 is built in this example, that 2311 is not divisible by 7, say?

What about whether or not it is divisible by 13? (Of course you can check, but that’s not the question. The question is can you tell from how we found 2311, as a product of primes less than 13.)

1. Check further: Calculate 2 x 3 x 5 x 7 x 11 x 13 + 1 and call it P. You can look P on a list of primes, but P is a big enough number that you need a long list of primes (much more than 1000). Scrap that approach.

2. If we check whether or not P is evenly divisible (i.e. divisible without a remainder) by odd numbers, do we know that it is prime? Explain.

2. Use Excel to generate a column of odd numbers. In the next column, in each cell calculate the value of P divided by odd number in the cell just to its left. Is P prime? Explain.

[For instance, if the odd numbers were in column A, starting in row 1, and P were 105, you would enter “=105/A1” in cell B1, and then copy cell B1, select cells B2, B3, B4, … as far down as you like, and then paste.]

Hmm… we are not getting prime numbers. BUT Euclid had a great insight. One way of proving there are infinitely many primes is to give a procedure so that given any natural number “m” (i.e. a positive whole number) one can produce a prime number that is larger than “m.” That’s not working. Euclid’s idea is much more subtle: He proposes: don’t worry about finding that prime number; just prove that it exists.

3. Read Sec. 2.3 and explain how Euclid’s method of establishing the existence of a prime number larger than a given number, say “m,” is similar to but different from our first try above (and in class).

4. Do Mindscape # 21 from Sec. 2.3.

5. Do Mindscape # 20 from Sec. 2.3. For this you may want to use Excel to produce the list of potential primes given by n^2+n+17. ( For this you first need a row or column of values for n that start out 1, 2, 3, 4, …) You can compare your “possible primes” with a list, such as the one at http://primes.utm.edu/lists/small/1000.txt . When you find the first one that is not prime, factor it. Here again, Excel can help if you do as in (2.), checking the quotient of the “possible prime” and odd numbers.