Dividing by 13

Tuesday, January 12, 2010

Here's a straightforward method supplied by Scott Fellows: Delete the last digit from the given number. Then subtract nine times the deleted digit from the remaining number. If what is left is divisible by 13, then so is the original number.

---

Rafael Ando contributes: Instead of deleting the last digit and subtracting it ninefold from the remaining number (which works), you could also add the deleted digit fourfold. Both methods work because 91 and 39 are each multiples of 13. For any prime p (except 2 and 5), a rule of divisibility could be "created" using this method:

1. Find m, such that m is the (preferably) smallest multiple of p that ends in either 1 or 9.
2. Delete the last digit and add (if multiple ends in 9) or subtract (if it ends in 1) the deleted digit times the integer nearest to m/10. For example, if m = 91, the integer closest to 91/10 = 9.1 is 9; and for 3.9, it's 4.
3. Verify if the result is a multiple of p. Use this process until it's obvious.

Example 1: Let's see if 14281581 is a multiple of 17.
In this case, m = 51 (which is 17×3), so we'll be deleting the last number and subtracting it fivefold.

1428158 - 5×1 = 1428153
142815 - 5×3 = 142800
14280 - 5×0 = 14280
1428 - 5×0 = 1428
142 - 5×8 = 102
10 - 5×2 = 0, which is a multiple of 17, so 14281581 is multiple of 17.

Example 2: Let's see if 7183186 is a multiple of 46.
First, note that 46 is not a prime number, and its factorization is 2×23. So, 7183186 needs to be divisible by both 2 and 23. Since it's an even number, it's obviously divisible by 2.
So let's verify that it is a multiple of 23:

m = 3×23 = 69, which means we'll be adding the deleted digit sevenfold.
718318 + 7×6 = 718360
71836 + 7×0 = 71836
7183 + 7×6 = 7225
722 + 7×5 = 757
75 + 7×7 = 124
12 + 7×4 = 40
4 + 7×0 = 4 (not divisible by 23), so 7183186 is not divisible by 46.

Note that you could've stopped calculating whenever you find the result to be obvious (i.e., you don't need to do it until the end). For example, in example 1 if you recognize 102 as divisible by 17, you don't need to continue (likewise, if you recognized 40 as not divisible by 23).
The idea behind this method it that you're either subtracting m×(last digit) and then dividing by 10, or adding m×(last digit) and then dividing by 10.

---

Jeremy Lane adds: It may be noted that while applying these rules, it is possible to loop among numbers as results. Example: Is 1313 divisible by 13? Using the procedure given we take 13×3 and obtain 39. This multiple ends in 9 so we add four-fold the last digit.

131 + 4×3 = 143 14 + 4×3 = 26 2 + 4×6 = 26 ...

Example: Is 1326 divisible by 13? Using the procedure given we take 13×7 = 91. This is not the smallest multiple, but it does show looping. The smaller multiple does loop at 39 as well. There are some examples where we would still need to recognize certain multiples. So we subtract nine-fold the last digit.

132 - 9×6 = 78 7 - 9×8 = -65 (factor out -1) 6 - 9×5 = -39 (again factor out -1) 3 - 9×9 = -78 (factor out -1)

This only occurs though if the number does happen to be divisible by the prime divisor. Otherwise, eventually you will have a number that is less than the prime divisor.

---

And here's a more complex method that can be extended to other formulas:

1 = 1 (mod 13)
10 = -3 (mod 13)    (i.e., 10 - -3 is divisible by 13)
100 = -4 (mod 13)   (i.e., 100 - -4 is divisible by 13)
1000 = -1 (mod 13)  (i.e., 1000 - -1 is divisible by 13)
10000 = 3 (mod 13)
100000 = 4 (mod 13)
1000000 = 1 (mod 13)

Call the ones digit a, the tens digit b, the hundreds digit c, ..... and you get:
a - 3×b - 4×c - d + 3×e + 4×f + g - .....
If this number is divisible by 13, then so is the original number. You can keep using this technique to get other formulas for divisibility for prime numbers. For composite numbers just check for divisibility by divisors.