Divisibility rule for any prime using determinants

Here is a general approach to determining whether a number is divisible by a prime. I’ll start with a couple examples before I state the general rule. This method is documented in [1].

First example: Is 2759 divisible by 31?

Yes, because

$\begin{align*} \begin{vmatrix} 275 & 9 \\ 3 & 1 \end{vmatrix} &= 248 \\ \begin{vmatrix} 24 & 8 \\ 3 & 1 \end{vmatrix} &= 0 \end{align*}$

and 0 is divisible by 31.

Is 75273 divisible by 61? No, because

$\begin{align*} \begin{vmatrix} 7527 & 3 \\ 6 & 1 \end{vmatrix} &= 7509 \\ \begin{vmatrix} 750 & 9\\ 6 & 1 \end{vmatrix} &= 696\\ \begin{vmatrix} 69 & 6\\ 6 & 1 \end{vmatrix} &= 33 \end{align*}$

and 33 is not divisible by 61.

What in the world is going on?

Let p be an odd prime and n a number we want to test for divisibility by p. Write n as 10a + b where b is a single digit. Then there is a number k, depending on p, such that n is divisible by p if and only if

$\begin{align*} \begin{vmatrix} a & b \\ k & 1 \end{vmatrix} \end{align*}$

is divisible by p.

So how do we find k?

If p ends in 1, we can take k = ⌊p / 10⌋.
If p ends in 3, we can take k = ⌊7p / 10⌋.
If p ends in 7, we can take k = ⌊3p / 10⌋.
If p ends in 9, we can take k = ⌊9p / 10⌋.

Here ⌊x⌋ means the floor of x, the largest integer no greater than x. Divisibility by even primes and primes ending in 5 is left as an exercise for the reader. The rule takes more effort to carry out when k is larger, but this rule generally takes less time than long division by p.

One final example. Suppose we want to test divisibility by 37. Since 37*3 = 111, k = 11.

Let’s test whether 3293 is divisible by 37.

329 – 11×3 = 296

29 – 11×6 = -37

and so yes, 3293 is divisible by 37.

[1] R. A. Watson. Tests for Divisibility. The Mathematical Gazette, Vol. 87, No. 510 (Nov., 2003), pp. 493-494