One more rule about Pythagorean triples

Yet again, let's consider Pythagorean triples, sets of three positive integers a, b and c such that a² + b² = c².  Here are several examples where all three numbers are less than 100.

3² + 4² = 5²
12² + 5² = 13²
15² + 8² = 17²
7² + 24² = 25²
9² + 40² = 41²
20² + 21² = 29²
48² + 55² = 73²

We know that we can generate Pythagorean triples using any two positive integers j and k with the formulas, where j > k with

a = j² - k²    b = 2jk and   c = j² + k²

This means there must be infinitely many different Pythagorean triples. If you aren't sure, consider k=1 and we get

a = j² - 1   b = 2j and  c = j² + 1

For any j > 1, we will get a unique Pythagorean triple.

Here's a pattern I noticed. Every triple on our list above has one number that is divisible by 5. Let us start with a speculation.

Speculation: Every Pythagorean triple has at least one number that is divisible by 5.

We could create a triple where all three numbers are divisible by 5 just by taking any Pythagorean triple and multiplying all the numbers by 5.

Example: Because  3² + 4² = 5², 15² + 20² = 25², The original numbers are 9 +16 = 25, and if we multiply all the numbers by 5, all the squares are multiplied by 25 and we get 225 + 400 = 625.

That explains why the modifier "at least" is used in the speculation.

Let's find facts that will help us prove the speculation.

Fact: The last digit of a square is determined by the last digit of the original number.

Think about multiplying two numbers that have two digits together, like 72 × 72. 

__72
_×72
_144
504 
5184

The ones place is just 2 × 2 and the 70 isn't involved. This would be true no matter how many digits in a number.

Fact: The last digit of a perfect square can only be 0, 1, 4, 9 or 6.

We can prove this by looking at the list of perfect squares of the numbers 0 through 9 (0, 1, 4, 16, 25, 36, 49, 64, 81) and using the first fact from above that the last digit of a number determines the last digit of the square.

Fact: The remainder of a perfect square when divided by 5 can only be 0, 1 or 4.

Because 10 = 2 × 5, the remainder upon division by 5 will look a lot like the last digit, except 6 becomes 1, and 9 becomes 4.

Fact: If you want to make a sum of two numbers from the set {0, 1, 4} to add up to 0, 1 or 4, there are only a finite number of patterns and not all of them work.

0 + 0 = 0 works
0 + 1 = 1 works
0 + 4 = 4 works
1 + 0 = 1 works
1 + 1 = 2 doesn't work
1 + 4 = 5 doesn't work, except when we divide 5 by 5 we get remainder 0, so it does work for us.
4 + 0 = 4 works
4 + 1 = 5  doesn't work, except when we divide 5 by 5 we get remainder 0, so it does work for us.
4 + 4 = 8 doesn't

Fact: Every pattern that works has a 0 or 5 in it.

Fact: A remainder of 0 when dividing by five means the number is divisible by 5.

Fact: Because 5 is prime, getting a perfect square that is divisible by 5 means the original number is divisible by 5.

This means our speculation about the Pythagorean triples is in fact a pattern that is always true. We could call it a "theorem", but I'm going to save that word for

Fact: Every Pythagorean triple has at least one number that is divisible by 5.

Here are two other facts that can be proved using similar methods, which the reader can try to prove if interested.

Fact: Every Pythagorean triple has at least one number that is divisible by 3.

Fact: Every Pythagorean triple has at least one number that is divisible by 2 and one number  divisible by 4.

We don't have any other primes for which this is true. That is proved simply by the triple 3, 4, 5. All the primes greater than 5 (7, 11, 13, 19, ...) do not divide any of these numbers evenly, so we have a single counter-example that works for an infinite number of cases, a situation a lazy mathematician is always happy to find.

Another rule about Pythagorean triples.

Last January, I wrote several posts about Pythagorean Triples, a set of three whole numbers a, b and c that follows the rule of the Pythagorean Theorem a² + b² = c². Here are some examples.

3² +4² = 5²
8² + 15² = 17²
24² + 7² = 25²

If we think about these numbers as sides of a triangle, the area will be ½ab. In the cases from above, the areas as 6, 60 and 84, respectively.

There is a way to generate all such whole number triples, using two positive integers j and k, with j>k.

a = j² - k²
b = 2jk
c = j² + k²

Our first rule is that we should stipulate that j does not equal k, because in the that case a = 0. Re-writing a and b in the area formula into multiples of j and k, we get this.

Area = ½ab = ½(j² - k²)2jk = (j² - k²)jk

Since j and k are whole numbers, the area must be a whole number. But more than that the number must be divisible by 6. The proof is split into two parts, first that the area is divisible by 2 and secondly that the area is divisible by 3.

Proof of the area is divisible by 2. If j or k is even, then (j² - k²)jk is even, since if you have a product of whole numbers and one is even, the product is even. The only other option is that both j and k is odd, and if that is the case then j² - k² = odd - odd = even.

Proof of the area is divisible by 3. If j or k is a multiple of 3, then (j² - k²)jk is a multiple of 3. The only other option is that neither j and k is a mulitple of 3. For any number n that isn't a multiple of 3,  n² will be of the form 3p + 1, which is to say one more than some multiple of 3. If that is the case then j² - k² = (3p + 1) - (3q + 1) = 3(p- q), which is a multiple of 3 as well.

Generating Pythagorean triples.

The Pythagorean Theorem is usually stated as a² + b² = c². If all three numbers are whole numbers, it is called a Pythagorean triple. Here are some examples with small numbers as the entries.

3² + 4² = 5²
12² + 5² = 13²
15² + 8² = 17²
24² + 7² = 25²
21² + 20² = 29²
35² + 12² = 37²

In these examples, no number bigger than 1 divides all three numbers in the set, so these are the relatively prime Pythagorean triples. It is true that 6² + 8² = 10² (36+64=100), but this is just taking the 3-4-5 triangle and multiply each number by two.

Here are a few rules about the relatively prime Pythagorean triples.

They are always of the form odd² + even² = odd². We can have even² + even² = even², like 6-8-10, but all the numbers are divisible by two, so they aren't relatively prime. It turns out that odd² + odd² will be even, of course, but it can never be the square of an even number. All the even squares are divisible by 4 and the sum of two odd perfect squares will always have remainder 2 when divided by 4.

There is a generating function. Take any two distinct whole numbers j and k and let j be the larger. Here are the formulas for a, b and c.

a = j² - k²
b = 2jk
c = j² + k²

Tomorrow, we will look at what choices for j and k will produce the relatively prime Pythagorean triples.

The 3-4-5 triangle

The Pythagorean Theorem is often stated as


a² + b² = c²

means that the sum of the squares of the lengths of the two short sides (the ones that meet to create the right angle) is equal to the square of the length of the long side opposite the 90°, the side known as the hypotenuse.

If you pick two whole numbers at random to be the short sides, also known as the legs, the hypotenuse will be a square root of a whole number.

For example: If a = 1 and b = 3, 1² + 3² = 10, which means c² = 10. 10 is not a perfect square, so c is equal to the irrational number the square root of 10, which I will write as sqrt(10).

If we are looking at one digit numbers only, we have just one pair of legs that will add up to a perfect square. 3² + 4² = 9 + 16 = 25 = 5².

Three whole numbers that satisfy a² + b² = c² are called a Pythagorean triple. If we find such a triple, we can create infinitely more by multiplying all the sides by the same whole number.  Here are some examples.

Multiply 3-4-5 by 2: 6² + 8² = 10²
Multiply 3-4-5 by 3: 9² + 12² = 15²
Multiply 3-4-5 by 4: 12² + 16² = 20²
...

All of these triangles are similar and when discussing Pythagorean triples, the ones that are relatively prime are a special case.

The Pythagorean Theorem is named for the ancient Greek mathematician Pythagoras (570-495 BCE), but as often happens in math, this does not mean he was the first person ever to notice the pattern. There is strong evidence that the ancient Egyptians who built the pyramids understood the 3-4-5 triangle at the very least, and they lived thousands of years before Pythagoras. In many archeological digs, among the building tools are three sticks of lengths with the ratio 3:4:5. It is assumed that the builders used these when constructing walls to make sure the walls and the floors met at 90° angles.

There are other relatively prime Pythagorean triples; in fact, there are infinitely many. The next two smallest ones are 5² + 12² = 13² and 8² + 15² = 17².

Tomorrow, we will discuss how to create all the Pythagorean triples, both those that are relatively prime and those that aren't.

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.

Casting out elevens.

Yesterday, we discussed casting out nines, a method for checking your work when doing addition. (It also works for multiplication and subtraction, as will the method we discuss today.) Casting out nines has a problem that it will not catch a transposition error. For example.

 321 casting out nines is 6
-235 casting out nines is 10 -> 1
  86 casting out nines is 14 -> 5 

check: 6 - 1 = 5, we are good

 321 casting out nines is 6
-253 casting out nines is 10 -> 1
  68 casting out nines is 14 -> 5 

check: 6 - 1 = 5, we are good... or are we?

Transposition can be caught be casting out elevens. Instead of adding up all the digits, we start with the digit in the ones place, then subtract the digit in the tens place, add the digit in the hundreds place, subtract the digit in the thousands place, and continue this alternation of addition and subtraction until we run out of digits.  Let me show examples with the numbers above, 321, 235, 86, 253 and 68.

321: start with the 1, subtract 2 (gives us -1), add 3.  Casting out elevens gives us 2.
235: start with 5, subtract 3 (gives us 2) add 2. Casting out elevens gives us 4.
86: take 6 subtract 8. Casting out elevens is -2. (If you don't like negative numbers, add 11 and get 9. It will still work.)
253: start with 3, subtract 5 (gives us -2) then add 2. Casting out elevens gives us 0. This means 253 is a multiple of eleven, though that is not needed for the work we are doing.
68: take 8, subtract 6, you get 2.  Let's do the problems above again.


 321 casting out elevens is 2
-235 casting out elevens is 4
  86 casting out elevens is -2

check: 2 - 4 = -2, we are good

 321 casting out elevens is 2
-253 casting out elevens is 0
  68 casting out elevens is 2

check: 2 - 0 = 2, a different result from above

In the era when this was used, you could check original invoices against the copied numbers in the ledger, or possibly the sum in the ledger would be compared with cash on hand. Transposition errors are fairly common and casting out nines won't catch them, but casting out elevens will. What this means is that when we divide 86 by 9, we get a remainder of 5, which is also the remainder when dividing 68 by 9. The remainder of 68 by 11 is 2, while the remainder of 86 by 11 is 9, which is 11 away from -2, another way to write the remainder.

Let's say 86 is the right answer and 68 is the wrong answer. If the only mistake you have made is a transposition, the difference between right and wrong will always be a multiple of 9, like 86-68 = 18. This tells you that if you have made a single mistake, you transposed two numbers in the ones place and the tens place, and the difference between them is 2.

Tomorrow: Two different "tricks" for multiples of 7.

Casting out nines.

Number theory is the study of the properties of whole numbers. Divisibility and primes are the major part of the field. It is usually counted as part of pure mathematics, the study of the discipline that is done for its own sake and for the sake of beauty, but even the most esoteric parts of math sometimes have practical purposes.

On New Year's Day, I discussed how to determine if a number is divisible by 3. The "trick" or method is to add up the digits. If that sum is divisible by 3, so is the original number, If it's not divisible by 3, the original number isn't divisible by 3 either.

The method for divisibility by 9 is very similar. Add the digits and check to see if the sum is divisible by 9. If yes, the original number is divisible by 9, and if no, the original number is not divisible by 9.

For example, the number of feet in a mile is 5,280. 5+2+8+0 = 15, which is divisible by 3 but not divisible by 9. The prime factorization of 5,280 is 2 × 2 × 2 × 2 × 3 × 5 × 11. For a number to be divisible by 9, we need two copies of 3 in the prime factorization,

And now for the practical use. In the 19th Century, there were no calculators and people did all their computations by hand. For example, clerks and accountants spent much of their days adding long columns of numbers. Let's set up a small example.

 322.75
 201.43
  75.32
+835.85

 The correct answer is 1435.35. But let's say a weary clerk makes a mistake and only carries 1 when adding up the tenths column instead of carrying 2. The answer would become 1434.35 and would be incorrect.

What we are going to do is add the digits of each of the numbers together. To take the process a step further, if the sum is two digits long we will add the digits together to get a one digit number.

322.75 -> 3+2+2+7+5 = 19 -> 1+9 = 10 -> 1+0 = 1
201.43 -> 2+0+1+4+3 = 10 -> 1+0 = 1
75.32 -> 7+5+3+2 = 17 -> 1+7 = 8
835.85 -> 8+3+5+8+5 = 29 -> 2+9 = 11 -> 1+1 = 2

Notice that 19 gets sent to 1, just as 10 is sent to 1, and 29 is sent to 2. Anytime a 9 shows up in our calculations, it acts on the sum just as if it were 0, not changing the sum at all. If you do this a lot, it's easy to see that a 9 can be thrown out, which gave the method the name "casting out nines".

Okay, so now the sum we have is 1+1+8+2 = 12, which we can break down further to 1+2 = 3.  What good is it?

The answer we get when adding up all the numbers should also become 3 when we cast out nines. The correct answer of 1435.35 becomes 1+4+3+5+3+5 = 21 and 2+1 = 3. When I made the mistake in carrying, I got 1434.35, which becomes 1+4+3+4+3+5 = 20 and 2+0 = 2. This was a relatively easy way to check for mistakes in sums.

Casting out nines is not perfect. The simple mistake of transposition of numbers will not be caught. For example, let's say I wrote 210.43 instead of 201.43 for the second number in the list.

 322.75
 210.43
  75.32
+835.85
1444.35 

1,444.35 becomes 1+4+4+4+3+5 = 21 becomes 2+1 = 3. When casting out nines, it is not distinguishable from 1,435.35.  Another method is needed to catch transpositions and it went under the name casting out elevens. We will take a look at this tomorrow.

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.