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