Checking for Divisibility by A Prime Number, Part 001

I have long wondered how to check a number for divisibility by an awkward number such as 7, 13, 23 or 31.

Checking for divisibility by other numbers could not be easier, once you know what to look for.

To check that a number is divisible by 2 (i.e. that it is an even number) check the last digit. Is the digit 2, 4, 6, 8 or 0? If so, the number is even.

To check if the number is divisible by 4, you have to check the last two digits. If the last two digits are one of the fifty multiples of 4 less than 100, from 00 to 96, the number will be divisible by 4.

To check if the number is divisible by 8, you have to check the last three digits. If the last three digits are a multiple of 8, from 000 to 992, the number will be divisible by 8.

A similar formula works to check for divisibility by 16, 32, 64, 128 and higher powers of two: for 16, check the last four digits for divisibility by 16; for 32, check the last 5 digits for divisibility by 32, and so on.

A number is divisible by 5 if the last digit is 0 or 5; it is divisible by 10 if the last digit is 0.

To check if a number is divisible by 100, 1000, 10,000 and so on, count the number of final zeroes in the number you are testing for divisibility. If the number has that many last digits all zeroes, the number is divisible by that number. (For example, to check if a number is divisible by 10,000 check if the last four digits are zero, e.g. 14,560,000).

A number is divisible by 3 if all of its digits add up to 3, 6 or 9: e.g. the digits of 165,289 added together yield 1+6+5+2+8+9 = 31; 3+1 = 4. Therefore 165289 is not divisible by 3.

If the number is divisible by 3 and it is also even, the number is divisible by 6. If the sum of all the digits adds up to 9 and only 9, the number is divisible by 9.

A number is divisible by 15 if it is divisible by 3 and its final digit is 0 or 5.

And lastly, to check for divisibility by 11 check the difference between the sum of all the even numbers and all of the odd numbers: if the difference is 0 or 11, the number is divisible by 11.

For example, to check the number 5,112,832,549 for divisibility by 11, add up all the odd numbers together and all the even numbers together, and deduct the larger number from the smaller:-

5+1+8+2+4 = 20; 1+2+3+5+9 = 20. 20 - 20 = 0.

The number 5,112,832,549 is divisible by 11. (Check it yourself).

To check for divisibility by a non-prime number like, say, 12, check for divisibility by its factors - in this case, divisibility by 3 and 4. Similarly for 25, check the last two digits to see if they are 00, 25, 50 or 75. To check for divisibility by 33, check for divisibility by both 3 and 11, and so on.

These are the basic mechanisms to check for the common numbers 2, 3, 4, 5, 6, 8, 9, 10 and 11, and of course the non-prime numbers.

So what, then, of prime numbers such as 7, 13, 17, 19 and so on? Well, I only came across a nifty technique that works for all such numbers. Once you know how to do this for, say, 7, you'll know how to do this for any and all such prime numbers.

And all you have to do is to remember the first five multiples of your target number. In the case of divisibility by 7, for instance, all you need to remember is 7, 14, 21, 28 and 35.