Test for Divisibility by 13
johndcook.com
johndcook.com
I'll copy the example from german Wikipedia article [0] as you might generalize from that easier as when I would write it down in mathematical notation:
Here are the weights for 7:
1 ≡ 1 (mod 7)
10 ≡ 3 (mod 7)
100 ≡ 2 (mod 7)
1000 ≡ −1 (mod 7)
10000 ≡ −3 (mod 7)
100000 ≡ −2 (mod 7)
1000000 ≡ 1 (mod 7)
...
10^n ≡ a_n (mod 7)
Example:
853629:
8x (-2) + 5x (-3) + 3x (-1) + 6x 2 + 2x 3 + 9x 1 = -16-15-3+12+6+9 = -7, therefore 853629 is divisible by 7.
[0] https://de.wikipedia.org/wiki/Quersumme#Gewichtete_Quersumme
One can also find periodical sequences for other natural numbers. E.g.,
* for 11, the sequence +1, -1, ...
* for 13, the sequence 1, -3, -4, -1, 3, 4, ...
For most divisors, it is not practical to test divisibility this way, as there are only few easily remembered weight sequences.
8
^ 8 (mod 7) is 1, remember that
85
^ 1 · 10 (mod 7) is 3, and 3 + 5 (mod 7) is 1, remember that
853
^ 1 · 10 + 3 (mod 7) is 6
8536
^ 6 · 10 + 6 (mod 7) is 3
85362
^ 3 · 10 + 2 (mod 7) is 4
853629
^ 4 · 10 + 9 (mod 7) is 0
def modulo(number, k):
val = 0;
for digit in str(number):
val = (val * 10 + int(digit)) % k
return val
The advantage is that you only need a small amount of memory (a single number between 0 and 6), so this is a kind of general divisibility rule where you only have to do small calculations in your head.
If I may digress a bit into automata theory, this means that you can construct a finite state automaton that determines whether a number is divisible by 7 (or any other constant) by reading its digits from left to right. Additionally, if a finite state automaton can do something reading from left to right, there is another automaton doing the same thing but reading from right to left. This means that there is also a 'simple' divisibility rule when starting with the least significant digit, though it may be a bit harder to find.
This is basically what also happens during long division! I marked the remainder of the previous operation in each line with a bracket (no italics in code formatting, sadly), appending another digit of the dividend behind them is the same operation as multiplying the 'remembered' number by 10 and adding the next digit to it:
8 5 3 6 2 9 / 7 = 1 2 1 9 4 7; remainder 0
- 7
--
[1]5 How long division works:
- 1 4 <------- subtract largest possible multiple,
---- note remainder in next line, append
[1]3 next digit from number at top, and
- 7 repeat until done. And make sure to
---- keep track of the result.
[6]6
- 6 3
----
[3]2
- 2 8
----
[4]9
- 4 9
----
[0] <= final remainder = 0, i.e. 7 is a divisor of the number
Maybe not mechanically easier, but easier to remember.
In your example, you calculate the value of the polynomial 8x^5+5x^4+3x^3+6x^2+2x^1+9 with x=10. The value is 853629, of course, but it you perform your calculation modulo 7, you have precisely followed Horner's method in the field F_7. To further simplify the calculation, note (as you did!) that 10 is congruent to 3 mod 7, so use x=3 instead of x=10.
Clearer as an example: Is 4173 divisible by 13? First iteration: 417 - (3 x 9) = 390. Second: 39 - (0 x 9) = 39. And 39 is divisible by 13, so 4173 is. (No worries if the last subtraction gives a negative result; same rule applies.)
To test for divisibility by 7, do exactly the same thing, but multiply the one's digit by 2 instead of 9. For 17, use 5. For 11, use 1.
I learned the divisible-by-7 trick from a book when I was a kid, but didn't figure out why it works, and how to generalize it, until I was embarrassingly adult. Left as an exercise for the reader.
I find the alternating digit sum method is easier to use for 11. They're competely equivalent, but your method makes it seem like you need to remember more state. For example, to test 678101 for divisiblity by 11 you'd go "678101, 67809, 6771, 676, 61, nope". With the alternating digits method you go "1, 1, 2, -6, 1, -5, nope" only dealing with one-digit numbers at every step. Maybe with practice you learn to ignore the leading digits until you need them.
678101 -> 6-7+8-1+0-1 = 5 -> no bueno
874632 -> 8-7+4-6+3-2 = 0 -> divides by 11
4173 -> 417 + (3 x 4) = 429 -> 42 + (9 x 4) = 78, which is divisible by 13, so 4173 is.
Of course, these two tests work for the same reason. You're saying 10a + b is divisible by 13 iff a - 9b is, I'm saying 10a + b is divisible by 13 iff a + 4b is, and those differ by 13b.
I guess I’m confused what point you’re making?
> You can check you’re right if (a) the first digit of the result is 1 less than the number you started with
The first digit of the result is 2 ... And the number that you started with is also 2, which is not 1 less... I guess I am not smarter then a 5th grader
I’m curious, how did you find that counterexample? I kind of ‘overfitted’ my mental model to the first 10 integers. But as a statistician I’m only in the business of being approximately right...! Nice catch.
23x9=207 starts with 20 which is 3 less than 23... 24x9=216, and 21 is 3 less than 24. 11x9=99 and 9 is 2 less than 11, 12x9=108 and 10 is 2 less than 12. So 0-9 are offset by 1, 10-19 are offset by 2, 20-29 offset by 3, 30-49 offset by 4?
The 7 * 11 * 13 = 1001 development in particular appears just after example 4.4 and is then generalized to arbitrary bases by theorem 4.3. For example to divide by five in octal, do the alternating sum trick on digits grouped in pairs, because 5 divides 8^2+1.
Though it quickly stops being useful for manual checks, Fermat's Little Theorem is a fun gizmo. It says for any prime `p` (say, 17) and base `a` not divisible by it (10), we have that `a^(p-1) % p == 1`. Put another way, so long as we meet the criteria (prime, doesn't divide base), we can form a divisibility test by summing blocks of `p-1` (16) digits and testing the result, just like the `3` case.
Further, since `p-1` is even we can take the square root of both sides (`a^((p-1)/2) % p == +/-1`) and use either the sum or alternating sum tricks with blocks half that size, depending on the sign of the final `1`.
Modular arithmetic, pretty fun stuff even if i'm incredibly bad at it.
How does this work when the last digit is 0?
Take the divisible by 3 rule: digits add up to a number divisible by 3, then the original number is divisible by 3. But 144 will get you 9. What in number theory tells you that 9 is divisible by 3?
while (n > 9)
n = sum_digits(n);
return (n == 3 || n == 6 || n == 9);As for how to generate the base table, recall that we say a divides n provided there exists some b such that ab = n. In this case we're talking about integers, although this is the definition for any ring.
Therefore, proving 3 divides 9 is as simple as noting that 3 * 3 = 9, and likewise we can prove 3 divides 6 by noting that 3 * 2 is 6.
Proving a lack of divisibilty is a little bit trickier. For this, you'll want to first prove the division algorithm which, in the case of the integers, says that for any two integers a and n, there exists unique integers b and r with abs(r) < abs(a) such that ab + r = n.
Given this, we can then note that, for instance, 7 = 3 * 2 + 1. Therefore 7 cannot be divisible by 3 as that would imply there exists some other integer b such that 7 = 3 * b + 0 contradicting that the integers from the division algorithm are unique.
You might then wonder: well, how do we know 3 * 2 is 6? Well, to stop these questions from recursing endlessly, we need to define the integers. One reasonable definition is "the initial element in the ring category" which gives us that the integers are a ring by definition. As such, we have axiomatically that there are integers 0 and 1, a commutative operation + with identity 0 that is closed under inverses, an associative operation * with identity 1, and that * distributes over +. If we then define 2 to be 1 + 1, 3 to be 1 + 1 + 1, and 6 to be 1 + 1 + 1 + 1 + 1 + 1, we can use distributivity to prove that 3 * 2 = 3 * (1 + 1) = (3 * 1) + (3 * 1) = 3 + 3 = 6.
Is akin to knowing the idea of how to drive a stick shift, and knowing how to drive a stick shift.
Divisibility by 13 is of course not as useful/applicable as divisibility by three, but the question is then more nuanced: "Why should I memorize this particular divisibility trick?"
This involves less memory than knowing how to use your calculator app to check.