Divisibility criteria: history and methods | Tangente

Criterion or character? ----------------------

In the mathematical literature, both expressions occur: "divisibility criterion" and "divisibility character." The second seems older; it is found, for example, in the writings of Blaise Pascal. It stems from the meaning of the word "character" as "that which characterizes."

The first is more widely used today, since the word "criterion" refers to a method for determining whether a property holds or not. In both cases, what is meant is the divisibility tests you probably learned at school — at least some of them!

Divisibility by 2, 4, 8, 16… -----------------------------------------

The simplest of the divisibility criteria is unquestionably that for divisibility by 2:

This criterion generalizes to powers of 2:

*"A number is divisible by 2ⁿ if, and only if, the number formed by its last n digits is divisible by 2ⁿ."*

Thus, 2016 is divisible by 4 because 16 is divisible by 4 (this is how you can spot leap years that are not divisible by 100). It is also a multiple of 8 because the number formed by its last three digits (016) is divisible by 8. The number 2016 is also divisible by 16 and by 32, but for these values using the criterion amounts to performing the division directly, since the number of digits is not enough to save any computing time!

Divisibility by 3, 9… --------------------------

The divisibility criterion for 3 is one of the best known:

This criterion follows from the fact that, for every integer n, 10ⁿ is always congruent to 1 modulo 3, or to put it more simply, that the remainder in the division of 10*ⁿ* by 3 is always equal to 1 (since the numbers 9, 99, 999, 9,999… are all divisible by 3).

A similar criterion exists for divisibility by 9:

This divisibility criterion is the origin of the famous "proof by nines," which — despite what its name suggests — is never a proof of the correctness (or accuracy) of a calculation. These criteria can be generalized to divisibility by 27, 81…

Thus, to check whether a number is divisible by 27, the number is split into "blocks" of three digits, these blocks are added together, and the result is checked for divisibility by 27.

-

Divisibility by 11, 5, 25… -----------------------------------

You will remember this one:

Here again, this criterion can be generalized to test divisibility by 5ⁿ (with n > 1):

*"A number is divisible by 5ⁿ if, and only if, the number formed by its last n digits is divisible by 5ⁿ."*

This of course follows from the fact that 10ⁿ is a multiple of 5*ⁿ but is not a multiple of 5ⁿ*⁺¹.

The divisibility criterion for 11 is perhaps less well known, but relatively easy to use:

Let's look at two examples:

For 2016, (0 + 6) – (2 + 1) = 3. We deduce that 2016 is not divisible by 11 (we can even deduce that the remainder in the division of 2016 by 11 is equal to 3).

For 1,234,554,321, (2 + 4 + 5 + 3 + 1) – (1 + 3 + 5 + 4 + 2) = 15 – 15 = 0. This number is therefore divisible by 11.

The principle behind this criterion rests on the fact that, for odd n, 10n is congruent to –1 modulo 11, and that, for even n, 10n is congruent to 1 modulo 11.