Ah, ha…gotcha! You thought this post was going to be about politics, I’ll bet, but it is really about something a bit more…mathematical.
Back in school, you were probably taught a few easy tricks to test for divisibility of one number by another number. For instance, if the last digit is even, the number is divisible by 2; if the last number ends in a zero, it is divisible by 10; if the last number is divisible by 5, so is the number; if the individual digits of the number add up to a number divisible by 3, then, so is the number (this works for 9, as well).
There were even more obscure divisibility tests, such as: to test to see if a number is divisible by 11, add the odd-place digits and subtract the even-place digits. If the result is divisible by 11, then, so was the original number. For example: is 286 divisible by 11? Well, the first digit is 6 and the third digit is 2, so 6+2=8 and the second digit is 8, so 8-8=0 and 0 counts as a number divisible by 11, according to the method, so 286 is, theoretically, divisible by 11 and, indeed, 26 x 11 = 286. Let’s take a harder example: 1,358,016.
6+0+5+1=12
1+8+3=12
12-12 = 0
so, the number is divisible by 11 (in fact, it is 11 x 123,456).
Why these tests work is usually taught in an elective course on elementary number theory to undergraduate mathematics majors.
Back around 2000 A. D., I was teaching math to 7th- and 8th-graders in a private Catholic school and I decided to teach the class divisibility tests. I started to play around with them and I developed a comprehensive system for testing divisibility by prime numbers. Why primes? This is because it can be rigorously proven that all numbers are either primes (having no divisors except themselves and 1) or may be factored into a series of primes that, when multiplied together, give the, “composite,” number. This is called the Fundamental Theorem of Arithmetic. For example, the number 5040 =
. The first 10 prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
What started this post is a dream I had, last night, involving the numbers 161 and 63 (don’t ask me why) and I decided to see if 161 were prime (63 is not, as the digits add up to 9, so the number is divisible by 9). As I was lying down, I tried to recall my earlier work and I rediscovered, pretty quickly, the divisibility test for 7 and I tried it on the number and the test result showed that 161 was divisible by 7 (it is 23 x 7), so, it is not a prime.
We have already seen divisibility tests for a few primes: 2, 3, 5, 11. What about some of the other primes, like 7 or 13? Are there tests for these? It turns out that there are and it shows the depths that even simple math can reveal. Here are some of the tests I devised back in 2000, but never published (I did write an article for a journal on math education, but I never sent it in):
Test for divisibility by 7:
Multiply the last digit by 2; subtract it from the rest; if the result is divisible by 7, so is the original number; if necessary, repeat until a small enough number is obtained.
Example:
Test 1778
8×2=16
177-16=161
Test 161
1×2=2
16-2=14
so, 1778 is divisible by 7.
Test for divisibility by 13:
Multiply the last digit by 9; subtract it from the rest of the digits; if the result is divisible by 13, then, so is the original number; if necessary, repeat the process until a small enough number is obtained.
Example:
Test 59,774
4×9=36
5977-36=5941
Test 5,941
1×9=9
594-9=585
Test 585
5×9=45
58-45=13
so, 59,774 is divisible by 13.
Test for divisibility by 17:
Multiply the last digit by 5 and subtract from the rest. Repeat, if necessary.
Example:
Test 424,405
5×5=25
42440-25=42415
Test 42415
5×5=25
4241-25=4216
Test 4216
6×5=30
421-30=391
Test 391
1×5=5
39-5=34
34 is divisible by 17, so 424,405 is divisible by 17 (it is 24,965 x 17).
Test for divisibility by 19:
Multiply the last digit by 2; add it to the rest of the digits; if the resulting number is divisible by 19, so is the original number.
Example: 26,277
7×2=14
2627+14=2641
Test 2641
1×2=2
264+2=266
Test 266
6×2=12
26+12=38=2×19
so, the number is divisible by 19.
Why did we switch from subtracting to adding? The mystery deepens (more, later)!
Test for divisibility by 23:
Multiply the last digit by 7, add to the rest of the numbers. Repeat, if necessary.
Example: 38,134
Test 38,134
4×7=28
3813+28=3841
Test 3841
1×7=7
384+7=391
Test 391
1×7=7
39+7=46
46=23×2, so, the original number is divisible by 23.
Test for divisibility by 29:
Multiply the last digit by 3 and add to the remaining digits. If the number is divisible by 29, so was the original number. Repeat, if necessary.
Example:
Test 236,118
8×3=24
23611+24=23635
Test 23635
3×5=15
2363+15=2378
Test 2378
3×8=24
237+24=261
Test 261
1×3=3
26+3=29
so, the original number is divisible by 29.
There are two questions to ask: 1) is this, “multiply by a seed number and add/subtract until reduced,” generalizable, 2) why was there a switch from subtraction to addition at 19?
The second question is easy to answer if we notice that we could have switched to subtraction, for, say, 19, if we had used multiply the last digit by 17 and then subtracted to reduction:
Example:
Test 26,277
7×17=119
2627-119=2508
Test 2508
8×17=136
250-136=114
Test 114
4×17=68
11-68=-57=-3×19
so, again, the number is divisible by 19.
Notice, that 17+2=19, so the two seeds add up to the divisor. Is this generalizable? Let’s look at 23. We used a seed of 7 and addition. What if we switched and used 23-7=16 as a seed and subtraction. Does this work? Let’s see:
Example:
Test 38,134
4×16=64
3813-64=3749
Test 3749
9×16=144
374-144=230
230=23×10
so, the number is divisible by 23.
So far, our hypothesis seems to work. This conjecture is:
************************************************************
Conjecture 1
Seed/Subtract+ Seed/Add = Divisor
************************************************************
Let’s make a table to summarize the hypothetical results, so far:
| Divisor | Seed/Subtract | Seed/Add | |
| 2 | Standard Test | Standard Test | |
| 3 | Standard Test | Standard Test | |
| 5 | Standard Test | Standard Test | |
| 7 | 2 | 5 | |
| 11 | Standard Test | Standard Test | |
| 13 | 9 | 4 | |
| 17 | 5 | 12 | |
| 19 | 17 | 2 | |
| 23 | 16 | 7 | |
| 29 | 26 | 3 |
According to this hypothesis, times 5 and add should work for division by 7. Does it:
Test 1778
8×5=40
177+40=217
Test 217
7×5=35
21+35=56=7×8,
so, the number is divisible by 7.
It should be apparent that we chose the smaller of the two seeds in each of our examples, so addition/subtraction is determined by that fact. If we write +5 to indicate seed/addition and -2 to indicate seed/subtraction, then we can make the chart, above, more streamlined. The smaller test is indicated.
| Divisor | Small Seed | Large Seed | |
| 2 | S. T. | S. T. | |
| 3 | S. T. | S. T. | |
| 5 | S. T. | S. T. | |
| 7 | -2 | +5 | |
| 11 | S. T. | S. T. | |
| 13 | +4 | -9 | |
| 17 | -5 | +12 | |
| 19 | +2 | -17 | |
| 23 | +7 | -16 | |
| 29 | +3 | -26 |
Example:
Test 601,678
8×1=8
60167-8=60159
Test 60159
9×1=9
6015-9=6006
Test 6006
6×1=6
600-6=594
Test 594
4×1=4
59-4=55=5×11
so, 601,678 is divisible by 11.
We can add seeds for the rest of the numbers that use other techniques. The resulting table is:
| Divisor | Small Seed | Large Seed | |
| 2 | No Seed | No Seed | |
| 3 | -2 | +1 | |
| 5 | -5 | +5 | |
| 7 | -2 | +5 | |
| 11 | -1 | +10 | |
| 13 | +4 | -9 | |
| 17 | -5 | +12 | |
| 19 | +2 | -17 | |
| 23 | +7 | -16 | |
| 29 | +3 | -26 |
It is easy to see that no seed is possible for 2, because of a parity (even/odd) problem. If the left-over is odd, but the last digit is even, the result will always be odd, which will invalidate the test. For example, there is no seed that will work for 34, because the number to be added or subtracted will always be even, because an even number (in this case, 4) time any number returns an even number and when subtracted or added to 3 will always return an odd number. This, “two problem,” may be at the heart of finding a universal test for prime divisors.
In any case, what is behind this method and is it generalizable to any prime? The secret to finding the seeds is to write the original number as a simple Diophantine equation, for example, with 29:
2 + d*9= 29
The value of d is, obviously, 3, and the leftover should be added. We can call the smaller seed, S, and the larger seed the compliment, Ś. Thus, Conjecture 1 may be re-written as:
Conjecture 1
S + Ś=d
Does this method always work and is it unique, in that does a given seed work only for a unique prime? That will be the subject of a future post. I suspect that the answer is, yes, but, possibly for only one of the two forms of the seed.
The Chicken