A number x is said to be divisible by y, written y | x (read y divides x), iff ∃ k ∈ Z: ky = x. Divisibility rules provide a way of determining whether a given (large) number is divisible by another (small) number without actually performing the division. They usually transform a number into a smaller number while preserving divisibility by a fixed divisor.
- Divisibility by 2
A number is divisible by 2 iff its last digit is divisible by 2 i.e., its last digit is 0, 2, 4, 6 or 8.
- Divisibility by 3
A number is divisible by 3 iff the sum of its digits is divisible by 3, e.g., 12123 (1+2+1+2+3=9) 9 is divisible by 3 and so is 12123.
- Divisibility by 4
A number is divisible by 4 iff the number formed by its last 2 digits is divisible by 4, e.g., 4032 ends in 32, which is divisible by 4 and so is 4032.
- Divisibility by 5
A number is divisible by 5 iff its last digit is 0 or 5, e.g., 5067805 ends in 5 and is divisible by 5.
- Divisibility by 6
A number is divisible by 6 iff it is divisible by both 2 and 3 i.e., its last digit is even and sum of its digits is divisible by 3, e.g., 1458 (1+4+5+8=18) is divisible by 6 since the last digit (8) is even and the sum 18 is divisible by 3.
- Divisibility by 7
It’s a little tricky to check divisibility by 7. There are several tests but here’s an easy one:
Multiply each digit beginning on the right hand side by the corresponding digit in this pattern [1,3,2,6,4,5] (or [1,3,2,-1,-3,-2]). Repeat the pattern as necessary. If the sum of the products is divisible by 7, then so is the original number.
Example: 2016 (6*1+1*3+0*2+2*6=21) is divisible by 7 since 21 is divisible by 7.
- Divisibility by 8
A number is divisible by 8 iff the number formed by its last 3 digits is divisible by 8, e.g., 6008 is divisible by 8 since 8 is divisible by 8.
- Divisibility by 9
A number is divisible by 9 iff the sum of its digits is divisible by 9, e.g., 43785 (4+3+7+8+5=27) is divisible by 9 since 27 is divisible by 9.
- Divisibility by 10
A number is divisible by 10 iff its last digit is 0.
- Divisibility by larger composite numbers
A number is divisible by a composite number iff it is divisible by the highest power of each of its prime factors e.g., we can check for divisibility by 252 (252=22*32*7) by checking for divisibility by 4, 9 and 7. Similarly, we can check for divisibility by 525 (525=3*52*7) by checking for divisibility by 3, 25 and 7.
- Generalized divisibility rule
This rule lets us test divisibility by any divisor D which ends in 1, 3, 7 or 9. It works as follows: Find a multiple of D which ends in 9 (If D ends in 1, 3, 7 or 9, multiply by 9, 3, 7 or 1 respectively). Add 1 and divide by 10, call the result m. A given number N=10t+q is divisible by D iff mq+t is divisible by D.
Example: To check if 913 (10*91+3, t=91, q=3) is divisible by 11, find m=(11*9+1)/10=10. Now mq+t = 10*3+91=121 is divisible by 11 and so is 913.
See problems NITT2 and PUCMM025 which use these ideas.
References:
Everything Under The Sun 
Hello. I have a different method for testing divisibility. As far as I can tell, this should work for any divisor and also has the benefit of being easily modified to work with numbers in other bases. It’s also quite simple. I’m assuming that the number is provided as a string because it’s too large to store as an integer:
bool check_divisibility(char* number, int base, int divisor)
{
int remainder = 0;
for (int k = 0; number[k] != 0; k++)
{
remainder = (base * remainder + number[k] – ‘0’) % divisor;
}
return (remainder == 0);
}
Rough proof of correctness:
It’s clear that an integer N is divisible by an integer D if and only if N mod D = 0. If N is too large to manipulate directly, then we can still test for divisibility by working with its digits. A number in some base B has a value equal to its digits multiplied by decreasing powers of B. For instance, the ternary number 201 has the value 2 * 3^2 + 0 * 3^1 + 1 * 3^0 = 10.
Clearly, breaking N down into its digits and calculating the sum of remainders modulo D of each digit’s value would still yield the same remainder as applying modulo to N itself. Calculating each digit’s value would be problematic because of overflows, though. We can treat the sum of digit values as a kind of polynomial and apply the same logic as used in Horner’s method. The result of that evaluation remains correct even if we take modulo D at each step rather than just at the end, so we can calculate the remainder without risking integer overflows.
Yes, that’s the obvious approach when the divisor can be any arbitrary integer. The divisibility rules in this post are special cases, which apply for some divisors and provide greater efficiency. In repeated remainder approach above, we will have to use the modulo operator a lot of times and it’s not as efficient. For some divisors like 5, 10 and powers of 2, we don’t have to process the whole input to determine if it is divisible by them.