Divisibility by any prime

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

and 0 is divisible by 31.

Is 75273 divisible by 61? No, because

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

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

The post Divisibility by any prime first appeared on John D. Cook.