divisibility test

A means of determining whether m|n without actually having to calculate nm. Most divisibility testsMathworldPlanetmath exploit some characteristic of the multiplesMathworldPlanetmath of m in a given base b.

For example, suppose that for some reason you wanted to determine whether 24709898213 is divisible by 11 but didn’t have access to (or didn’t want to use) a calculator or computer. You don’t need to know the result or the remainder (if applicable).

The most obvious way to make the determination is by actually dividing 24709898213 by 11. This could take ten subtractions and at least six multiplication table look-ups (even if one has memorized the multiplication table, it still counts as an operationMathworldPlanetmath). The answer is 2246354383 and there is no remainder, meaning that 24709898213 is in fact divisible by 11.

If on the other hand you add up the odd place digits (2 + 7 + 9 + 9 + 2 + 3) and subtract the sum of the even place digits (4 + 0 + 8 + 8 + 1), you get the answer 11, meaning that 24709898213 is in fact divisible by 11; this result was obtained having needed just two additionsPlanetmathPlanetmath and one subtraction. This is the well-known base 10 divisibility test by 11, which is that an integer n is divisible by 11 if the differencePlanetmathPlanetmath between the sum of the odd-placed digits and the even-placed digits is also a multiple of 11.

A few other well-known divisibility tests in base 10 are:

n is divisible by 2 if the least significant digit is 0, 2, 4, 6 or 8.

n is divisible by 3 if it has digital root 3, 6 or 9.

n is divisible by 5 if the least significant digit is 0 or 5.

n is divisible by 9 if it has digital root 9.

n is divisible by 10 if the least significant digit is 0.

From this it can be generalized to other bases: that if 2|b then the least significant digit of the number has to be even for the number as a whole to also be even; that if the digital root of n is b-1 then (b-1)|n; that bx|n if the x least significant digits of n are all zeroes; and that (b+1)|n if the difference of the odd placed digits and the even place digits of n is a multiple of b+1.

For some semiprimes pq it might still be advantageous to perform two divisibility tests (one for p and then one for q) than to calculate npq.

Divisibility tests are usually more useful for humans than for computers, and then only for sufficiently small numbers. For example, a computer might be able to divide 10000! + 11 by 11 in an immediate-feeling .032 seconds, but it might take .094 seconds just to figure out what the base 10 digits of 10000! + 11 are. However, the divisibility tests in binary might be useful for certain programming problems.

Title divisibility test
Canonical name DivisibilityTest
Date of creation 2013-03-22 15:59:58
Last modified on 2013-03-22 15:59:58
Owner CompositeFan (12809)
Last modified by CompositeFan (12809)
Numerical id 6
Author CompositeFan (12809)
Entry type Definition
Classification msc 11A63
Synonym divisibility rule