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.

Is 7,308 divisible by 7?

In math, we can always divide a by b unless b is zero. But when we say "divisible by 3" for example, we mean evenly divisible by 3, that when we divide by 3 we get a whole number and no remainder or decimal part.

At some point in grade school - I don't know the curriculum year by year - students learn about odd and even numbers, and that numbers ending in 0, 2, 4, 6 and 8 are even and can be divided by 2.  Soon after, they learn that numbers ending in a 0 or 5 are divisible by 5.  Here on the blog, we learned the method for divisibility by 3 and the method for divisibility by 9, both dealing with the sum of the digits. The method for 9 was called "casting out nines" way back in the day (19th Century), and the method for 11 was called "casting out elevens".

Armed with this information, we can tell if a number is divisible by several of the smallest prime numbers, 2, 3, 5 and 11.  But another small prime, namely 7, has been skipped over.  Here is a method for seeing if a number is divisible by 7.

Example 1: Let's take 7,308, a number I chose at random. Here is the method as I was taught in grade school.

 
Step 1: Split the number into the ones digit and the rest of the number. In this example, that means 7,308 becomes 730 and 8.

Step 2: Subtract two times the ones digit from the rest of the number. In this case, we have

730
-16
714

Step 3: If you can tell if the new number is divisible by 7, stop. If not, take the new number and go back to Step 1.

In this case, I can look at the number and say "7 is divisible by 7 and 14 is divisible by 7, so 714 will be divisible by 7."  But let's assume that some people who don't use numbers as often as I do still can't tell and continue with our process, splitting the number into 71 and 4.

71
-8
63

I would hope that everyone remembers 63 = 7 × 9, but even if someone didn't, they could split this number into 6 and 3 and continue.

 6
-6
 0

In general, we should say the process ends when we get a number less than 70 and ask the people using the method to be able to "eyeball" numbers less than 70 and tell if 7 goes in evenly. If someone doesn't remember these numbers, we could get a negative answer.

Example 2: Let's say you can't remember if 85 is divisible by 7. (Hint: It's not.) You can split it into 8 and 5, double the 5 to 10 and subtract.

  8
-10
 -2

This method can leave us with a negative number. If you don't like negative numbers, here is another version of the same idea that uses addition instead of subtraction.

Example 1a: Let's again start with 7,308.

Step 1: Split the number into the ones digit and the rest of the number.  In this case, we'll have 730 and 8, just like before.

Step 2: Multiply the ones digit by 5 and add to the rest of the number. In this case, this means adding 730 and 8 × 5 = 40.

730
+40
770

Step 3: If you can tell if the new number is divisible by 7, stop. If not, take the new number and go back to Step 1. I would hope all my students could see 770 is divisible by 7.

Example 2a: This time, let's use 822.  Split it into 82 and 2, multiply 2 by 5 and get 10.

 82
+10
 92

92 is not divisible by 7, but if we aren't sure of that, split it into 9 and 2, multiply 2 by 5 and add again.

  9
+10
 19

The person using this method needs to know 7 does not go into 19. One "drawback" of this second method is that if we have a two digit number, splitting it again can make a bigger two digit number, so "eyeballing" numbers less than 70 is a non-negotiable skill.

Tomorrow: A similar method of divisibility by 13.

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.

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.