Universal Test for Divisibility


Given positive integers N, x and b, is N divisible by x in the base b ?

Suppose that

b = sx + r
and
N = f(b) = a0 + a1b + a2b2 + ¼ + anbn
Then
N = a0 + a1(sx + r) + a2(sx + r)2 + ¼+ an(sx + r)n
It is clear from this that x divides N if and only if x divides f(r).There are infinitely many values of r and s satisfying the condition, be most natural one for r being the remainder when b is divided by x: then 0 £ r < x. Now let c0, c1, c2 ,¼, cn be integers with
r0 º c0, r1º c1, r2º c2 ,¼, rn ºcn mod x
Then
N = f(b) = a0 + a1b + a2b2 +¼+ anbn
º f(r) = a0 + a1r + a2r2 + ¼ + anrn
º a0c0 + a1c1 + a2c2 + ¼ + ancn   mod x
Thus N is divisible by x if and only if this last expression is divisible by x.

To implement this algorithm on a spreadsheet, the given coefficients ak are listed on the first row. In this example the integer to be tested is

N = 247829148637513423
being expressed in base 23. Next we enter x. Thus it is desired to find if N is divisible by 17. After entering the base number, r ( = 6) is computed with the built-in function @mod. Then the various powers of r  modulo x are calculated. Finally the running sum's of the akck  are computed along the last row. It is the very last sum, = 15 in this case, that determines the divisibility. In this instance a nonzero sum appears, meaning N is not divisible by x.
 
2
4
7
8
2
9
1
4
8
6
3
7
5
1
3
4
17
                               
23
                               
6
3
9
10
13
5
15
11
16
14
8
7
4
12
2
6
1
 
15
9
7
5
3
10
11
0
4
11
14
10
16
7
5
4