Universal Test for Divisibility
Given positive integers N, x and b, is N
divisible by x in the base b ?
Suppose that
and
N = f(b) = a_{0
}+
a_{1}b
+
a_{2}b^{2
}+
¼
+
a_{n}b^{n}. 

Then
N = a_{0 }+ a_{1}(sx
+
r)
+ a_{2}(sx + r)^{2 }+
¼+
a_{n}(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 c_{0},
c_{1},
c_{2
},¼,
c_{n}
be integers with
r^{0} º
c_{0},
r^{1}º
c_{1},
r^{2}º
c_{2
},¼,
r^{n
}ºc_{n}
mod x. 

Then
N = f(b) = a_{0
}+
a_{1}b
+
a_{2}b^{2
}+¼+
a_{n}b^{n} 

º f(r)
= a_{0 }+ a_{1}r + a_{2}r^{2
}+
¼
+
a_{n}r^{n} 

º a_{0}c_{0
}+
a_{1}c_{1
}+
a_{2}c_{2
}+
¼
+
a_{n}c_{n}
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
a_{k}
are listed on the first row. In this example the integer to be tested is
N = 2478291486375134_{23}, 

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 builtin function @mod. Then the various powers
of r modulo x are calculated. Finally the running sum's
of the a_{k}c_{k} 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
