Here is another proof I remember from number theory. There’s nothing deep or tricky here — just another example of a simple proof that I would like to use to show my high schoolers what a proof is (outside geometry). In addition, for some reason, I find the prime numbers fascinating. I hope someday I can spend more time learning about them, but this proof is one that anyone can grasp, even an elementary student.
We’re going to prove that every prime number larger than 3 is either a multiple of 6 plus 1 or a multiple of 6 plus 5. I find that remarkable! Of all the prime numbers in the world, even though no one has ever been able to find a pattern of any kind, will they really, truly, all fit into these two categories? And how can we be sure that out there in the ten trillions somewhere that there’s not one renegade prime with some other remainder? Let’s see:
All prime numbers larger than 3 have a remainder of either 1 or 5 when divided by 6.
Proof: All positive integers can be written as 6k+0, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5, where k is some integer greater than or equal to zero. (That is, every integer is the result of multiplying other some integer by 6 and adding a remainder of either 0, 1, 2, 3, 4, or 5.)
We know that 2 and 3 are prime, but we are only concerned with primes larger than 3. The next prime, 5, has the form 6k+5. (In this case, k = 0.)
Now let’s take a look at each form. Numbers in the form 6k, 6k+2, and 6k+4 are all even, so they are all multiples of 2 and therefore not prime. Numbers in the form 6k+3 can also be written as 3(2k+1) (by factoring out the 3). Therefore these numbers are multiples of 3 and therefore not prime.
The only two forms left are 6k+1 and 6k+5. So we have proven our original statement that all prime numbers larger than 3 have have a remainder of either 1 or 5 when divided by 6. The neat part (to me) is that with just a few lines of proof we have ruled out 2/3 of the integers as possible primes!
End of Proof.
A question: Why did we pick 6? Are there other number for which we could take a similar approach and possibly rule out more integers? And what might be a good candidate for such a number?
Well, 6 = 2 x 3, the product of the first two primes. If we try 8, 9, 12, or 16, we really won’t accomplish anything because all of these numbers are just different combinations of 2’s and 3’s. We’ve already ruled out all the multiples of 2 and 3. If we try 10 (2×5), we don’t seem to rule out as many as we did with 6. (Try it yourself. I count that we eliminate 6 out of 10 integers larger than 5.) So we need to include another prime in our factors for this new number.
I think the only number that is sensible to try next is 30, which is 2×3x5. Try it and see what happens……
1 response so far ↓
Rolfe Schmidt // June 7, 2007 at 6:30 pm
Great example! I just realized this a few months ago, and thought it was very neat. And really do try it for 30, and 210, and so on…