Discrete Math - Day 24

Today we continued looking at prime numbers and their distributions. I revisited the conjecture made by one student that the number of primes was infinite and the idea from another student about creating a formula of some sort to answer the question.

With this idea in mind I proceeded to present the idea of proof by contradiction. As an example, I used the idea that everyone agrees that when the temperature is 80 degrees or warmer then it is comfortable to wear shorts. Today the temperature is in the high 20s. Someone walks outside in shorts and concludes that it is not comfortable to wear shorts. What conclusion can we draw? Several students said that the temperature isn't above 80 degrees.

This is the idea with a proof by contradiction. We hypothesize the truth of a statement and using that assumption we follow a series of logical steps that leads to a contradiction. We are now in a position to prove that the number of primes is infinite.

This proof first appeared in Euclid's elements over 2,000 years ago and is a simple, yet beautiful illustration of proof by contradiction. First, assume there are a finite number of primes. We can list these primes as a set, albeit it might be a very large set. The primes in our set are {p₁, p₂, p₃, ... p_n}.

By the accepted properties of integers we may multiply these together and add 1 to the product to create another integer N. We have N = p₁ x p₂ x p₃ ... x p_n + 1.

Now, p_n <  p_n + 1 <  p₁ x p₂ x p₃ ... x p_n + 1 = N, so pn < N.

What happens if we divide N by p₁ or p₂ or any of the primes in our list? The class pondered this but had no response. I asked them to see what happens for 2 x 3 x 5 + 1. What happens if you divide this number by 2 or by 3 or by 5? Students saw that the prime numbers did not divide the number evenly. In fact, each time we divide by one of the primes in the list the remainder is 1.

This means that we have a number that is larger than any of our existing prime numbers and is not divisible by any of those primes. This contradicts the idea that p_n is the largest prime. Therefore there must not be a largest prime.

We then looked at creating a cumulative frequency graph of the number of primes. This graph roughly follows a logarithmic function. The asymptotic nature of the prime number distribution was proved by Gauss, but I did not get into that at this time. It is something that could be discussed now; I have a video, The Music of the Primes, that discusses this and which we will watch later.

I displayed one student's graph to help illustrate the nature of the distribution. Of course, students couldn't remember the name of the graph, although some recognized that it looked like a parabola flipped on its side or similar to a square root graph. I asked students to try to make connections between this idea and patterns that they see in their Sieve of Eratosthenes work. Again, not much was forthcoming; I asked students to continue to consider connections.

Next we answered some questions about the distribution of primes and length of contiguous composite numbers. Several students asked what a composite number was. I asked the class to help out and thankfully several were able to say that composite numbers have more than 2 factors.

We discussed the answers and they show that the number of integers needed to capture 10 prime numbers increases as the integer values go up. We also saw that the longest length of contiguous composite numbers goes up as the value of integers increase. These illustrate that while prime numbers are infinite, they become more and more spread out.

I then had students make conjectures about prime numbers and the patterns they were seeing. Several students wondered whether the prime numbers would eventually taper off to nothing. This was a wonderful opportunity to go back to the proof we did earlier. When students were reminded that we proved that the number of primes was infinite, they readily said, "Oh, that's right!" and then proceeded to modify their conjecture that the primes become more and more rare.

Next class we'll explore the idea of integers that are relatively prime. This will be followed by prime factorization and then the Euclidean Algorithm.

Visit the class summary for a student's perspective and to view the lesson slides.