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.