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 10*a* + *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*= ⌊7*p*/ 10⌋. - If
*p*ends in 7, we can take*k*= ⌊3*p*/ 10⌋. - If
*p*ends in 9, we can take*k*= ⌊9*p*/ 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