Exact divisibility by 19
First recognise the lower multiples of 19 which are
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
38, 57, 76, 95, 114, 133, 152, 171, 190, 209, 228
Rule to test for divisibility by 19
Multiply the last digit by 2 and add this to the number represented by the remaining digits. Repeat this until a multiple is recognised, (or not).
Example: Is 11628 divisible. by 19? Proceed like this
(7 x 2) >> 1164 >>> (8 x 2) >>> 117
14 16
1178 133 Yes
Discussion
Let the number to be divided be N = 10a + b. All integers may be written in this form. [e.g. 11628 = (10 x 1162) + 8 ]
The result produced after applying this rule once is a + 2b.
To demonstrate that this test for divisibility by 19 is valid in all cases, we need to show that
if a + 2b is a multiple of 19, then it follows that N = 10a + b must be also.
Proof:
If a + 2b is a multiple of 19, we may write
a + 2b = 19k Multiply through by 10
10a + 20b = 19(10k) Deduct 19b from both sides
10a + b = 19(10k - b)
This expression makes it clear that
10a + b is also a multiple of 19 (Q. E. D.)
I think this supplies what you asked for. If you are curious where the general form of the rule, (described below), originated, it is from the study of congruences in number theory.
Having shown that the rule is valid for the case of divisibility by 19, it is a simple matter to find a similar form of proof for any particular case of divisibility by a prime.
If you read on you will see how the appropriate number, (such as the number 2 for divisibility by 19 above), is chosen for each divisibility test.
General Divisibility Rule for any prime divisor p
Find the least multiple of prime p that ends in 9
Let n = [(least multiple of prime p that ends in 9 ) + 1]/10
Also record p - n. The results for a few primes below are given below.
There are two types of rule depending on whether n or p - n (see below), is smaller.
Type I; If p - n is smaller just multiply the last digit by p - n and subtract this from the rest of the number. Repeat until a multiple of p is recognised, or not.
Type II; If n is smaller just multiply the last digit by n and add this to the rest of the number. Repeat until a multiple of p is recognised, or not. The earlier example was type 1.
p n p - n
7 5 2
11 10 1
13 4 9
17 12 5
19 2 17
23 7 16
29 3 26
31 28 3
37 26 11
41 37 4
43 13 30
47 33 14
Here is an example of Type II, which uses p - n = 2
Example: Is 18788 divisible. by 7? Proceed like this
Multiply the last digit by 2 and subtract
(8 x 2) >> 1878 >>> (2 x 2) >>> 186 >>> 18
-16 -4 -4
1862 182 14 Yes
I hope all this was helpful,
Regards - Ian
