Problems & Puzzles:
Puzzles
Puzzle 101. Digital
Divisibility Tests
For sure you know some of the popular
"digital divisibility tests" of a given number N
by another number p, based on
certain operations/properties of the decimal digits of N.
For the purposes of this puzzle we must
understand a "divisibility test" as a procedure that
operates over the decimal digits of N and that reduces the initial given
number N into another N' such that N>N'.
This procedure can be applied recursively producing a series of numbers N
> N' > N'' >...> N* such that the last one, N*, can be easily
divided by p; when this happens then
the original number N also is divided
by N.
Here are some of these tests, for the first
primes p:
p 
Divisibility test of N
by p 
2 
If N is even (that is
the say if the rightmost digit of N is zero or an even digit) then
2 divides N

3 
If
the sum of the digits of N is divided by 3 then N is divided by 3

5 
If the rightmost digit
of N is 0 or 5 then 5 divides N

7 
"Double the
units and subtract from the tens", e.g. 1365
>136(2x5)=126 >12(2x6)=0. If the chain ends in zero or a
multiple of 7, then the original number is divisible by 7"

11 
If N=a1a2a3a4...ak then
if (a1a2+a3a4 ...) is divided by 11 then N is divided by 11
"Subtract the units from
the tens", e.g. 1364 > 1364 etc. If the chain ends in
zero, then the original number is divisible by 11"

13 
"Add the tens to
4 times the units", e.g. 1365 > 136+20 etc. If the chain
ends in a multiple of 13, then the original number is divisible by
13"

17 
"Two times the
hundreds less the last two digits, e.g. 8517 > 2*85 17,
etc...." 
19 
"Add the
hundreds to 4 times the rest", e.g. 1311 > 13+44 etc. If
the chain ends in a multiple of 19, then the original number is
divisible by 19" 
23 
? 
others 
? 
Questions:
1. Find the divisibility rule for p = 23
and others
2. Do you devise a general approach to determine the divisibility rule for
any prime p?
References:
1. http://www.mcn.net/~jimloy/divis.html
2. http://mathworld.wolfram.com/DivisibilityTests.html
3. http://www.nrich.maths.org.uk/mathsf/journalf/jan97/art1/index.html
4. http://uzweb.uz.ac.zw/science/maths/zimaths/div19.htm
5. http://forum.swarthmore.edu/k12/mathtips/ward2.html
6. http://www.cuttheknot.com/blue/FurtherDivisibility.html
A new one after the Nash solution:
7. http://dmoz.org/Science/Math/Number_Theory/Divisibility/Division_Rules/
Solution
Chris
Nash has solved (29/07/2000) both questions showing a general method
to produce any "divisibility test". As part of his approach to
the solution, new interesting and second level questions arise. Here is
his email. Ready?... then, go!!!
"I
thought about looking at solving this problem, and split the
divisibility criteria into two varieties.
Case 1). Split the digits into groups of a specified size. Either
add all the groups, or alternatively add or subtract the groups.
Case 2). Take the last d digits. Multiply them by some small quantity,
and add them to the rest.
Case 3). Division by 2 or 5 is done merely by looking at the last digit,
since 2 and 5 are factors of the base 10.
Case 1) is actually a variant of case 2). (Make the small quantity
either +1 or 1).
So we look merely at case 2). Let our number be N, and let us
choose to take d digits from the end. Then N can be written as X*10^d +
Y, where Y is the last d digits of N. And we now wish to find an integer
k such that N is divisible by p if and only if X+kY is divisible by p.
We have the following logic, <=> denotes if and only if. p
is a prime, and is not 2 or 5 X+kY is divisible by p <=>
10^d(X+kY) is divisible by p <=> (X*10^d + Y) + (k*10^d1)Y is
divisible by p
Hence, for our required division rule, given d, we must choose k
such that k*10^d1 is divisible by p. Any choice of d will give us a
division rule. However the idea is to choose a value of d that is not
too large, and a value of k so that multiplication is not too difficult.
We search by value of d, and we will assume that it is easy to multiply
a d digit number by numbers 5 or less.
d=1
===
Division rules exist with multiplier k if 10k1 is divisible by p. So we
attempt the k values from 5 to 5
k=5: 51 has factors 3*17. We already know easier division rules
for these.
k=4: 41 has factors 41. So here is a division rule for 41: subtract
four times the units from the rest.
k=3: 31, again produces a division rule for 31: subtract three times
the units from the rest
k=2: 21, gives the division rule you list for 7: subtract twice the
units from the rest
k=1: 11, gives the division rule you list for 11.
k=1: 9, gives the familiar division rule you list for 3.
k=2: 19, gives a different rule than you list for 19: double the units,
add to the rest
k=3: 29, gives a rule for 29: multiply the units by 3, add to the rest
k=4: 39, gives the rule you list for 13: multiply
the units by 4, add to the rest.
k=5: 49, gives a rule for 7, but it is not so easy: multiply the units
by 5, add to the rest.
Before we continue with this search, we need to think, what
is an 'easy'
division rule? For instance, which rule is easier for 19?
 double the units, add to the rest, or
 add the hundreds to four times the rest
It appears the easiest rule is the rule that gives the smallest
value of k, however this may not always be true. For example, we can
always construct a rule for any prime p, with k=1. Since 10^(p1)1 is
divisible by p, a general division rule for p is take the last p1
digits, and add to the rest. But this is not too helpful, since it may
only reduce our problem to p1 digits.
So I started to search for division rules that work as follows.
Find a division rule with the smallest value of d, and for k values in
the range 5 to 5. Now we can reverse the process. Here is an algorithm
to find a suitable division rule for p.
1
Initialize R=1 and D=0
2 Calculate
X, such that 10X1 is divisible by p.
3 In a loop:
3.1
increase D
3.2
multiply R by X
3.3 reduce
R modulo P to it's smallest absolute value (P/2<R<P/2)
3.4 If R
is in the 'acceptable' range for multiplication (5 to +5)
output the
rule  take the last D digits, multiply by R, add to the rest, and
exit the loop
If you prefer, you can change this algorithm so the test for R
tests against other values, for instance +1, +2, +4 (if you do not
want to multiply by 3 in your rule).
Here is the list of division rules up to 100 generated using this
algorithm (it is very easy to go much higher)
13: take last 1 digits, multiply by 4, add to rest
17: take last 1 digits, multiply by 5, subtract from rest
19: take last 1 digits, multiply by 2, add to rest
23: take last 2 digits, multiply by 3, add to rest
29: take last 1 digits, multiply by 3, add to rest
31: take last 1 digits, multiply by 3, subtract from rest
37: take last 3 digits, multiply by 1, add to rest
41: take last 1 digits, multiply by 4, subtract from rest
43: take last 2 digits, multiply by 3, subtract from rest
47: take last 5 digits, multiply by 3, subtract from rest
53: take last 7 digits, multiply by 4, subtract from rest
59: take last 4 digits, multiply by 2, subtract from rest
61: take last 13 digits, multiply by 2, add to rest
67: take last 2 digits, multiply by 2, subtract from rest
71: take last 6 digits, multiply by 2, add to rest
73: take last 4 digits, multiply by 1, subtract from rest
79: take last 13 digits, multiply by 1, add to rest
83: take last 15 digits, multiply by 3, add to rest
89: take last 8 digits, multiply by 2, add to rest
97: take last 10 digits, multiply by 2, add to rest
Note some of them are not very easy to use, for instance, the rule
for 61 only reduces you to a 13
digit number. Any smaller reductions produce more difficult
multiplication needed. If you have an 8digit calculator, a rule that
reduces things to 7 digits may be good enough.
Note there is an interesting feature of these rules. Any rule
generated may work for more than one number. For instance, take 59. The
rule is take the last four digits and multiply by 2. The rule works
since 2*10^41 = 20001 is divisible by 59. The other factors are 3
(for which we already have a division rule) and 113. So the rule for 59
works for 113, too!
So, there are now more questions:
1) Does anyone have any better rules
for 61, 79, 83, 89, and 97?
2) Is the method I chose (smallest number of digits to produce a
multiplier of 5 or less) the best algorithm?
3) are there any smarter methods (such as splitting into alternate
digits) that
produce better rules?
Finally, I revised the rules of the search a little. Suppose a
division rule for p can reduce the number to a value p^2 or less, and we
have division rules for smaller p. Then we can quickly factor the
remaining number. So I defined a *difficult* division rule as one that
would require the same number of digits (or more) than p^2 (and with the
same range of k as above).
Here are the hard division rules up to 1000:
47, 53, 59, 61, 71, 73, 79, 83, 89, 97, 103, 107, 109, 127, 139,
149, 151, 157, 163, 173, 179, 191, 193, 197, 211, 223, 227, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 419, 421,
431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 503, 509, 521,
523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 887, 907,
911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 "
Later he
added:
"Of course this is only one type of division
rule  taking digits from the 'end' and adding or subtracting them into
the beginning. There are definitely other rules that can work from the
'other end', but these rules are really the same as doing the entire
division. (For instance, 97, take the first digit, multiply it by 3,
move it down two decimal places and add to the remainder... eg 5723 =
5000 + 723 > 150+723 = 873 = 800 + 73 > 24+73).
But I would be very interested if anyone can find some better
rules  in particular I wonder if a rule for a
large prime can be constructed by rules for smaller primes."
***
I feel very
happy with this solution produced by Nash, because incidentally
exhibits one of the most charming by candid aspects of the good scientific work:
it
opens more questions (4) that the closed ones (2)  without traces of harassment
...
***
The young
Jordanian mathematician, Murad A. AlDamen, has sent (24/10/2000) a very
simple & general method to find a rule of divisibility for any prime.
I would like to
show his general method with an example that  BTW  answers the question
asked by Nash about of a better divisibility for the prime 61.
The Murad's
general method goes like this:
Question: ¿Does
p=61 divides  let's say to N=3598207?
Answer: Write
down the following list of numbers
p=61 
N=3598207 
359820*1
 6*7 
359778 
35977*1
 6*8 
35929 
3592*1
 6*9 
3538 
353*1
 6*8 
305 
30*1
 6*5 
0 
If the last
number is zero then 61 divides 3598207
If, in another
example, p=103
then 10 multiplies the units of N and 3
to the rest of it, in each step, etcetera...
***
Now here is the
proof sent by Murad of his method:
"Let
N be a number that we will test it. M is a factor of N. N=n1+10n2, M=k1+10k2,
[M/10]=k2 and [N/10]=n2. The First Theorem: n2k1k2n1=0 (mod M) if and only
if MN
The proof: Let L*M=N =n1+10n2, L(k1+10k2)=n1+10n2
L*k1n1=10a ….(1)
10Lk2=10a10n2, Lk2=an2
n2 –Lk2=a … (2)
add one to two and by N=M*L
we find ((n1+10n2)(k1k2)+ (k1+10k2)(nnn1))/(k1+10k2)=11a, then
(n2k1k2n1)=0 (mod M)"
***
A new approach has been sent (20/11/2000) by Jan van Delden:
"Since it isn't mentioned explicitly, the next might be
interesting, although I must add that Murad's method is simpler to do by
hand. First establish the first k (the order, divisor of p1) for which
10^k1 has p as a divisor, or: smallest k for which 10^k congruent to 1 mod
p.
(To turn it around it's faster to calculate the primes being divisors
of the repunits {1}k Since 10^k1 is divisible by 9.
11=11
111=3.37
1111=11.101 etc.
Also interesting in this light is that: k even
10^(2r)1=(10^r1)(10^r+1) so for instance if k=4 the term 101 follows
immediately.)
Secondly calculate 10^r mod p with r=0..k1. (Let answer fall into
(p1)/2 and (p1)/2 get alternate signs in sum later on, if possible).
With p=37 (Order 3):
1 mod 37 = 1 (Not too hard to calculate:)
10 mod 37 = 10
100 mod 37 = 11
1000 mod 37 = 110 mod 37 =1
How big is the remainder of 12548 divided by 37? Write 12548 as 12 548
and add up these two groups of 3digit numbers up to 560.
Calculate the sum (multiplying by 1,10 and 11, counting from right to
left)
0*1+6*10+5*11=5
With p=13: (calculate until 10^k=1 mod p, rest negate!)
10^0 mod 13=1
10^1 mod 13=10
10^2 mod 13=9 or 4
10^3 mod 13=90 mod 13=1 (so order is 6, divisor of 12)
10^4 mod 13=10 or 3
10^5 mod 13=4
10^6 mod 13=1
(13 is divisor of 111111)
12458 gives 8+5*10+4*(4)+2*(1)+1*3=43
12458 mod 13=43 mod 13=4
To proof above use:
 (a mod p)(b mod p)=ab mod p and
 (a+b) mod p=a mod p + b mod p
So the disadvantage is that all the remainders of 10^k have to be
calculated modulo p, but the advantage is that you don't get stuck with a
large remaining number to investigate".
***
Felice Russo sends the following reference about this subject:
http://math.furman.edu/~mwoodard/fuejum/textv/volume3text.html
***
Phil Plummer wrote his collaboration to this puzzle on August 13, 2014:
Here is a pdf copy
of the journal. My paper starts on page 96. (The pages do not start
at page 1). Note however that there are a couple of typos:
a) The value in the table, column y=8 for prime= 89 should be 2, not
22.
b) The equation on top of page 97 has the signs wrong. Instead of +,
+, +, and  they should be , +, , and +.
***
