Wednesday, November 25, 2009

Wednesday Math, Vol. 98: Patterns in the prime numbers

You may recall from a long ago math class that a prime is a positive whole number greater than 1 that can only be evenly divided by itself and 1. In older math books, 1 was listed as a prime, but at some time in the 20th Century it was decided that 1 was a special case and it was called a unit and would be separate from the primes. This means 2 is the smallest prime number and the only even prime number, since every other even number is divisible by 2.

If we divide an odd number by 4, the remainder will either be 1 or 3. This means any odd number must either be of the form 4k+1 or 4k+3. Here are the starts of the two lists on the positive side.

4k+1 = {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, ...}
4k+3 = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, ...}

Any prime number bigger than 2 has to be in one of these two lists. The early primes on the two lists are marked in bold and red. There has been a proof that there are infinitely many primes since the time of Euclid. It's a more recent proof that there are infinitely many primes in each of our subcategories 4k+1 and 4k+3.

The primes show up somewhat randomly. There are long stretches of consecutive numbers that contain no primes and there are also many instances of two consecutive odd numbers both being prime, like 29 and 31 or 41 and 43. These pairs are called twin primes. It is still unknown if there are infinitely many pairs of twin primes.

Here's an unusual fact about the primes of the form 4k+1. All of them can be written as the sum of two perfect squares. Here are some early examples.

5 = 4+1 = 2^2 + 1^2
13 = 9+4 = 3^2 + 2^2
17 = 16+1 = 4^2 + 1^2
29 = 25+4 = 5^2 + 2^2

Notice that this isn't true for any old number of the form 4k+1. 21 is not the sum of two perfect squares, while 25, which isn't prime, is 3^2 + 4^2 = 9 + 16. So it's hit and miss if the number isn't prime, but it works every time with the 4k+1 primes. Fermat made the statement of the theorem back in the 1600's, but gave no proof. The first proof written down in the 1700's was by My Favorite Lenny, Leonhard Euler. It's just crazy how many things in math were first done by Euler. His proof was complicated and some simpler proofs, or at least shorter ones, have been proved since.

Next week: Something we don't know about the primes.


Dr. Zaius said...

Math is hard. My best advice that I can give you regarding math is that I think that you should cheat whenever possible. ;o)

Distributorcap said...

want to really make our heads explode LOL (in a good way) - i cant wait until your post on imaginary numbers!

and all numbers are eventually the product of primes... correct?

Matty Boy said...

Doc: Math as it is taught today gives all honor and glory to the best cheats of centuries gone by.

D-Cap: I actually did a post on i, but I just might have another one in me.

And yes, all numbers greater than 1 have a unique prime factorization.