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.

Relatively prime.

You might recall the idea of reducing fractions to lowest terms from school. I hope these memories are not accompanied by cold sweat or outbursts of obscenity. The name for the concept behind lowest terms is relatively prime.

Definition. Two numbers a and b are relatively prime to each other if their respective prime factorizations have no primes in common.

Let's use the idea in the concept where most people see it first, reducing fractions.

Example 1: 40% is the same as the fraction 40/100.  This is obviously not in lowest terms, since both are divisible by 10, so 40/100 = 4/10. This is still not in lowest terms since both are even. 4/10 = 2/5, and 2 and 5 are relatively prime. In fact, both 2 and 5 are prime, which might cause some confusion. Let's do a second example of relatively prime number where neither number is prime.

Example 2: 48% is the same as the fraction 48/100, not a relatively prime pair.  Let's reduce to lowest terms.

48/100 = 24/50 = 12/25, which is lowest terms.

12 = 3 × 2 × 2, so it isn't prime.
25 = 5 × 5, also not a prime.

The pair 12 and 25 is an example of a relatively prime pair of numbers where neither number is prime.

Tomorrow: The triangular numbers

Divisibility by 13, and a general method for any prime number.

Here's something you already know. 10 = 5 × 2. Because of this well known fact, all we have to do is check the last digit of any number to decide whether a number is divisible by 2 (last digit even) or divisible by 5 (last digit 0 or 5).

For any other prime number, the method for divisibility will be like this.

Step 1: Split the number into two new numbers: the last digit and all the rest.
Step 2: Multiply the last digit by some special number. (This number is dependent on which prime we are using.) Then add this multiplied value to the value we are calling "the rest".
Step 3: Check to see if you can tell if this new value is divisible by the prime in question. If you cannot tell yet, go back to step 1 and continue until you get a number where you can tell.

Examples

Divisibility by 3: The special number we multiply the last digit by is 1. (Nice and easy.)
Divisibility by 7: The special number we multiply the last digit by is 5.
Divisibility by 11:  The special number we multiply the last digit by is 10.
Divisibility by 13: The special number we multiply the last digit by is 4.

(Finding the special number is done by understanding number theory. What we are looking for is the number we multiply by 10 so that the remainder when we divide by the prime is 1.)

Okay, let's look at 5,280, the number of feet in a mile, and see if it is divisible by 3, 7, 11 or 13. (It should be obviously that it is divisible by 2 and divisible by 5.)

Divisible by 3.
1. Split 5280 into 528 and 0. Multiply 0 by 1 and add to 528, which gives us 528. 528 is a little too big, so let's do the method again.
2. Split 528 into 52 and 8. Multiply 8 by 1 and add to 52, which gives us 60. 60 is divisible by 3, so the original number 5,280 is also divisible by 3.

Divisible by 7.
1. Split 5280 into 528 and 0. Multiply 0 by 5 and add to 528, which gives us 528. 528 is a little too big, so let's do the method again.
2. Split 528 into 52 and 8. Multiply 8 by 5 and add to 52, which gives us 92. Still a little to big to see divisibility by 7 easily, so one more step.
3. Split 92 into 9 and 2. Multiply 2 by 5 and add to 9 to get 19.  19 is not divisible by 7, so the original number 5,280 is also not divisible by 7.

Divisible by 11.
1. Split 5280 into 528 and 0. Multiply 0 by 10 and add to 528, which gives us 528. 528 is a little too big, so let's do the method again.
2. Split 528 into 52 and 8. Multiply 8 by 10 and add to 52, which gives us 132. Still too big, so one more step.
3. Split 132 into 13 and 2. Multiply 2 by 10 and add to 13, which gives us 33.  33 is obviously divisible by 11, so 5,280 is also divisible by 11.

Divisible by 13.
1. Split 5280 into 528 and 0. Multiply 0 by 4 and add to 528, which gives us 528. 528 is a little too big, so let's do the method again.
2. Split 528 into 52 and 8. Multiply 8 by 4 and add to 52, which gives us 84. Not crystal clear, so let's go one more step.
3. Split 84 into 8 and 4. Multiply 4 by 4 and add to 8, which gives us 24. 24 is not divisible by 13, since 2 × 13 = 26. This means the original number 5,280 is not divisible by 13.

Tomorrow: Relatively prime.

What are the prime years in the 21st Century?

Yesterday, we checked to see if 2013 was a prime number. Because the digits sum to 2+0+1+3 = 6, we can tell immediately that it is not prime because it is divisible by 3, 2013 = 671 × 3. It turns out that 671 isn't prime, either, since it factors to 61 × 11, both of which are prime.

This means the prime factorization of 2013 = 3 × 11 × 61.  I put the primes in order from smallest to largest, but that's just me being tidy. The order of the primes doesn't matter. We say that every number has a unique prime factorization up to order.

Not everyone knows this rule for divisibility by 3, but the rule for divisibility by 5 is much simpler and better known. It shows us quickly that 2015 can't possibly be prime, since 2015 = 5 × 403. (To get the complete prime factorization, we have to check to see if 403 is prime. It turns out it isn't, 403 = 13 × 31.)

So let's ask a slightly more general problem. What numbers between 2000 and 2100 are prime? This sounds like a lot of work, which is why I decided to use Excel to answer the question.

(If you are new to Excel, you can skip down to the answer.)

Step 1: What is the square root of 2100?
In cell A1, type =sqrt(2100). The answer is 45.8257... The reason to find this is because we need to check each of our numbers for divisibility by the primes less than their square root. If a × b = n, the smaller of a and b has to be less than or equal to the square root of n and the larger must be greater than or equal to the square root of n.

Step 2: Across row 1 starting in B1, list the primes less than 45.
Starting in B1, type 2[tab] 3[tab] 5[tab] 7[tab] 11[tab] 13[tab] 17[tab] 19[tab] 23[tab] 29[tab] 31[tab] 37[tab] 41[tab] 43[tab].

Step 3: Put the numbers from 2001 to 2099 in column A.
The easiest way to do this is to type 2001 in A2, drag the value down to A101 and change the method of filling the values in to "Fill Series".

Step 4: How to tell if a number is evenly divisible by a prime.
2001/3 = 667, but 2001/5 = 400.2, which means 2001 is divisible by 3, but not by 5. The Excel formula to type will use the Excel built-in formulas IF and INT. 

IF asks for a statement that is true or false, what to do if it is true and what to do if it is false.

INT takes a number x and rounds down to the largest whole number less than x. For example, =INT(2001/3) will give us 667, but =INT(2001/5) will give us 400 instead of 400.2, a difference we will be using in our logical statement to test.

Here is the formula to type into cell B2.

=IF(INT($A2/B$1)=$A2/B$1, "yes"," ")

What this does is check if INT(2001/2) = 2001/2.  In this case it does not, so Excel will put a blank in this cell, which is what " " means.) If I click and drag this formula down the column and across the rows, The spreadsheet will now have a pattern of the word "yes" scattered about among the blank cells.

Step 5: Use an IF statement to find the numbers that weren't divisible by any of the primes we used.
We now use IF and COUNTIF in the column just beyond N to see if the word "yes" showed up in that row. If it didn't, the number in column A is prime and we will copy that number into column P.

=IF(COUNTIF(B2:N2,"yes")=0, A2, " ")

Yet again, click and drag the formula down the column. Column P now has the primes between 2000 and 2100 listed. Here they are.

The Answer.

2003

2011

2017

2027
2029

2039

2053

2063

2069

2081
2083

2087
2089

2099

Notice that some primes have a difference of only two, like 2081 and 2083.  These are called twin primes. Mathematicians have known since the time of Euclid that there are an infinite number of primes, which means that whatever big number n you choose, there have to be primes larger than n. It is unknown if the twin primes are infinite. It is not of vital importance, but mathematicians are fascinated by problems that are easy to state and difficult to solve.

Tomorrow: A practical application of number theory known as casting out nines.

Is 2013 a prime?

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

Examples: 2, 3, 5, 7, 11, 13, 17 and 19 are all the primes less than 20. Primes keep going on forever, so no matter how large a number you choose, there are primes that are even larger.

Definition: In earlier times, 1 was considered a prime, but now it is called a unit, and it stands alone among the positive integers, since it has only one factor, namely itself.

Definition: Numbers bigger than 1 that are not prime are composite.

Examples: Here are the composite numbers that are less than or equal to ten.

4 has three factors: 1, 2 and 4
6 has four factors: 1, 2, 3 and 6
8 has four factors: 1, 2, 4 and 8
9 has three factors: 1, 3 and 9

Question: Is 2013 a prime number?

Explanation: It's "obvious" that 2012 couldn't be a prime number, because any even number greater than 2 is divisible by 2, so 2012 = 2 × 1006. More than two factors means composite not prime. For the same reason, 2014 isn't prime. It's also easy to see 2015 isn't prime, because it is divisible by 5. To be exact, 2015 = 5 × 403.

Okay, so what about 2013? It's not quite as obvious, but 2013 is not prime because it is divisible by 3. The rules for divisibility by 2 and 5 are simple and taught in schools everywhere. The method is only concerned with the final digit.

Rule for divisibility by 2: The last digit must be 0, 2, 4, 6 or 8.

Rule for divisibility by 5: The last digit must be 0 or 5.

Rule for divisibility by 3: This one takes a little arithmetic, but only a little. Add up the digits of a number. If that sum is divisible by 3, the original number is divisible by 3. And to the contrary, if the sum isn't divisible by 3, the original number isn't divisible by 3, either.

2013 = 3 × 671, so it has more than two factors and is not prime.

One step further: Every number can be broken down into a unique product of primes, known as a prime factorization.

Examples: 

We already know that 2012 = 2 ×1006, but 1006 isn't prime.
2012 = 2 × 2 × 503. It turns out that 503 is a prime number, so 2 × 2 × 503 is the prime factorization of 2012.

We already know 2013 = 3 × 671. Is 671 a prime? No, it is 11 × 61, so 3 × 11 × 61 is the prime factorization of 2013.

Tomorrow: How to determine if a number is prime or composite.