Sunday, January 13, 2013

Sum of two squares and the prime numbers of the form 4k+1

Repeating the definition of prime numbers.

Definition: A prime number p is a positive integer that has exactly two factors, 1 and p itself.

2 is the only even prime. Other small primes include 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... The list goes on forever as there is no largest prime number.

One way to split up the odd primes is to divide by 4 and check the remainder.

With 3, 4 goes in 0 times with remainder 3.
With 5, 4 goes in 1 time with remainder 1.
With 7, 4 goes in 1 time with remainder 3.
With 11, 4 goes in 2 times with remainder 3.
With 13, 4 goes in 3 times with remainder 1.
With 17, 4 goes in 4 times with remainder 1.

With a little thought, it's easy to convince yourself that the only options for the remainder are 1 and 3, so we can split the odd primes into two camps, the 4k + 1 primes {5, 13, 17, 29, ...} and the 4k + 3 primes {3, 7, 11, 19, 23...}.

Let's look at perfect squares. An even number can always be written 2k, while an odd number can be written as 2k+1. Here's what happens when we square even numbers and odd numbers.

(2k)² = 4k²
(2k+1)² = 4k² + 4k + 1

What this tells us is that even perfect squares are not just divisible by 2, but also divisible by 4.  Take a look at 4, 16, 36, 64, 100, 144, etc. if you need convincing.

For the odd squares (1, 5, 9, 25, 49, 81, etc.) you will always get the remainder of 1 when you divide by 4.

Fact with easy proof: No prime of the form 4k + 3 can be the sum of two squares.

Even square + even square = divisible by 4
Even square + odd square = remainder of 1 when dividing by 4
Odd square + odd square = remainder of 2 when dividing by 4

So the sum of two squares when divided by 4 can have remainder 0, 1 or 2, but not 3.

Fact with much harder proof: Every prime of the form 4k + 1 can be written as the sum of two squares and the choice of the two squares, one even and one odd, is unique for each prime.

Let me show you the first few examples.
5 = 2²+ 1² = 4 + 1
13 = 2²+ 3² = 4 + 9
17 = 4²+ 1² = 16 + 1
29 = 2²+ 5² = 4 +25
37 = 6²+ 1² = 36 + 1
41 =  4²+ 5² = 16 +25

This is not an easy proof and beyond the scope of what I want to discuss on the blog. To me, this is one of those remarkable things you can discover in higher mathematics. It's remarkable that it works for every prime of the form 4k+1 and doubly remarkable that the solution is unique for each prime of that form.

Tomorrow: Fun with Pascal's Triangle.

1. 2. 3. 