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.

Checking for Divisibility by A Prime Number, Part 002

Here, I'll introduce a little terminology.

- The subject number is the number you are testing.

- The target number is the number for which you are testing for divisibility.

- The remnant is the number that remains.

First of all, check that your number is a prime number - that its only factors are 1 and itself. If the number is a non-prime, you'll have to check that the subject number is divisible by both or all factors.

Now work out the multiples of that number, from 1 to 5.

For example: the multiples of 7 from 1 to 5 are 7, 14, 21, 28, 35.

The multiples of 13 from 1 to 5 are 13, 26, 39, 52 and 65.

The multiples of 17 from 1 to 5 are 17, 34, 51, 68 and 85.

And so on.

Begin with your subject number.

Now either add to that subject number, or subtract from it, the multiple of your target number that leaves the last digit or digits as 0. Divide the remnant by 10 and repeat until you get a single digit. If that single digit is not 0, the number is not divisible.

Consider testing 15,579 by 19.

First, subtract 19 to leave 15,560. Getting rid of the 0 leaves 1,556. Subtracting (4x19=76) yields 1,480. Again, getting rid of the 0 yields 148. Subtracting (2x19=38) yields 110. Removing the 0 yields 11. Adding 19 yields 30; getting rid of the 0 yields a final digit of 3. This is clearly not zero, so 15,579 is not divisible by 19.

Another example: testing the divisibility of 345,246 by 13.

First, subtract (2x13=26) to yield 345,220. Dividing by 10 yields 34,522. Subtracting (4x13=52) yields 34,470; division by 10 produces 3,447. Adding 13 yields 3,460; discarding the 0 yields 346. Deducting another 26 yields 320. Dividing by 10 yields 32; adding (6x13=78) yields 110. Dividing by 10 yields 11; adding (3x13=39) yields 50, and a final division by 10 produces a single digit, 5. 345,246 is not divisible by 13.

This tool has just been added to my growing arsenal of mathematical techniques. I commend it to the house.

New Blog!

I broke open a new blog here at Blogger. It's likely I'll be devoting that one to Vedic Mathematics, though not exclusively to it.

I'm retaining this blog for general purpose posts, including but not restricted to crossposts from Comfortable Creature, the name of my other blog.

That makes, let's see now, this blog, my community posts - I have three that I maintain, my blog on OKCupid, my heavily censored North Walse Newspapers one, my mostly empty InsaneJournal and Dreamwitdh ones gathering dust, and now this one. I used to have one on the Shadownessence forum, but that one's probably well and truly extinct by now.

That's a whole damn load of blogging. :)