Do you have a question you would like to ask Professor Puzzler? Click here to ask your question!
S. Ventar writes, "I saw video that explains divisibility for 19. Multiply the last digit by 2 and add to left over digits. repeat until result two digits multiple of 19. Why does method work?"
Hi S! That's a great question. Let's do an example first, to make sure everyone understands the method. Let's take the number 65968 and do the process on it. Ready?
65968: 6596 + 2 x 8 = 6612
6612: 661 + 2 x 2 = 665
665: 66 + 2 x 5 = 76
76: 7 + 2 x 6 = 19
Since the result of this repeated process is 19, the number is divisible by 19. Note that you can stop the process anywhere you happen to know that a number is a multiple of 19. For instance, if you knew that 76 was a multiple of 19, you wouldn't have to do the last step. Similarly, if you knew that 76 wasn't a multiple of 19, you could stop there.
For completeness, let's do one that isn't a multiple of 19, and then we'll explore your questions of why this works. Let's do the number 6121.
6121: 612 + 2 x 1 = 614
614: 61 + 2 x 4 = 69
69: 6 + 2 x 9 = 24
And I know that 24 is not divisible by 19, so I conclude 6121 is not divisible by 19 either.
Before I go any further, I want to introduce you (in case you're unfamiliar) with a branch of mathematics we call "modular arithmetic." In modular arithmetic, we aren't dealing with equations; instead, we're dealing with something called "congruences." A congruence looks like this:
a ≡ b mod c
It looks like an equation, except that instead of an equals sign, the symbol in the middle has three bars. We read this congruence like this:
"a is congruent to b mod c."
It's a short-hand way of saying that if you subtract b from a, you get a multiple of c.
Thus, all of the following are true:
7 ≡ 1 mod 3 (7 - 1 = 6, which is a multiple of 3)
10 ≡ 1 mod 3 (10 - 1 = 9, which is a multiple of 3)
15 ≡ 0 mod 5 (15 - 0 = 15, which is a multiple of 5).
There are a couple of nice rules for congruences that will help us see why this divisibility rule works.
Multiplicative Congruence Property
If a ≡ b mod c, then ax ≡ bx mod c.
Additive Congruence Property
If a ≡ b mod c, and d ≡ e mod c, then a + d ≡ b + e mod c.
These should look very familiar to you; they are just like the multiplicative and additive properties for equality, except that they involve congruences (with the same modular base - note that the c stays constant throughout!).
With all of this in mind, let's explore what happens with our 19 divisibility rule. First of all, I'll start by pointing out that any integer can be written in the form 10x + y, with the y representing the last digit, and x representing the number formed by all the other digits. Here are some examples:
145: x = 14, y = 5; 145 = 10(14) + 5
32794: x = 3279, y = 4; 32794 = 10(3279) + 4
Let's suppose we have a number K which is divisible by 19. We can write K = 10x + y, for some integer x, and y representing the last digit of K. Using congruences, we can write:
Congruence 1. 10x + y ≡ 0 mod 19
Now, just because K is divisible by 19 doesn't mean that 10x is divisible by 19. Let's say that when we divide 10x by 19, we get a remainder of z. This means we can write:
Congruence 2. 10x ≡ z mod 19
Subtracting the second congruence from the first gives us the following:
Congruence 3. y ≡ -z mod 19
If we do our process on the number 10x + y, we obtain the following: x + 2y. (divide 10x by 10, and add twice the last digit). Remember this result, because we're going to return to it later! If we start with 10x + y, the next number in our process is x + 2y. If we can show that x + 2y is congruent to 0 mod 19 whenever 10x + y is congruent to 0 mod 19, then we'll have shown that the divisibility rule works (because each step in the process will recursively be a multiple of 19 as well).
Now it's time to invoke the Multiplicative Congruence Property on Congruences 2 and 3, using the number 2 as our multiplier:
Congruence 4. 20x ≡ 2z mod 19
Congruence 5. 2y ≡ -2z mod 19
Now we note that 19x has no remainder when divided by 19, because x is an integer, so 19x must be a multiple of 19. This means:
Congruence 6. 19x ≡ 0 mod 19
Combining 4 and 6, using the Additive Congruence Property (technically, subtractive property, or multiplication by -1 and then addition) gives us:
Congruence 7. x ≡ 2z mod 19
Now add together Congruences 5 and 7:
Congruence 8. 2y + x ≡ -2z + 2z mod 19
Congruence 9. 2y + x ≡ 0 mod 19.
In other words: if you start with a multiple of 19, and do the process described, you'll end up with another multiple of 19. And if you do the process on that number, you'll still have a multiple of 19. And so on, and so on. And that's why the process works.
Incidentally, I should add that as far as I know, no one actually uses this divisibility rule for anything; the more cumbersome a divisibility rule is, the less useful it is compared to doing long division. After all, if a number is divisible by 19, you probably want to know what the other factor is, so you'll end up doing long division anyway!