Divisibility criterion

by a natural number

A condition which is satisfied by a natural number if and only if it is divisible by . It is also desirable for this condition to be readily verifiable, and for this verification not to be any more involved than the direct division of by would be.

If the difference between two numbers and is divisible by , the number will be divisible by if and only if the number is divisible by . This property forms the basis of many divisibility criteria. Let the notation of in the decimal system have the form

then

, where ;

, where ;

, where ;

These equalities immediately yield divisibility criteria by . Also, for a number to be divisible by it is necessary and sufficient for its last digit, i.e. the number , to be divisible by 2; for the number to be divisible by (by ) it is necessary and sufficient for the number represented by the two (respectively, three) last digits of , i.e. the number (the number ) to be divisible by 4 (by 8). Since the difference is a multiple of 4, the divisibility criterion by 4 may also be stated as follows: A number is divisible by 4 if and only if the number is divisible by 4.

Each divisibility criterion by a number makes it possible to replace the number (unless this number is too small) by some non-negative integer smaller than which is divisible by if and only if itself is divisible by . In other words, each divisibility criterion by a number is defined by some function , assuming integral values and satisfying the conditions: for each natural number ; and is divisible by if and only if the number is divisible by . Any integer-valued function that satisfies the above conditions is known as a divisibility function for the number ; the set of all such functions is denoted by . It is clear that

Since

one has

Thus, the number is divisible by (by ) if and only if the sum of its digits is divisible by 3 (by 9). In a similar manner

so that

If the numbers are represented in the numeral system with base , where it is possible to find divisibility criteria by divisors of the type . Thus, if , one obtains the following divisibility functions by 11 and by 101:

Since , one obtains a combined divisibility criterion by the numbers 7, 11 and 13: In order to find out whether a given number is divisible by any one of the numbers 7, 11 or 13, it is sufficient to subdivide the number into groups of three digits, beginning from the right, and then form the alternating sum of the numbers represented by these groups. The number thus obtained is divisible by , or if and only if the original number is divisible by 7, 11 or 13, respectively. Thus,

If the integers and are coprime, the number is divisible by if and only if the number is divisible by . This idea is also frequently employed in constructing divisibility criteria. Let be some divisor of the difference ; the numbers and are then coprime, and it follows from the equation

that the number is divisible by if and only if the number is divisible by . For instance, if , , the difference is divisible by 19. Therefore

In order to find out whether or not a given number is divisible by 19, this criterion can be repeatedly applied. Let be some divisor of the sum . It follows from the equation

that the number is divisible by if and only if the number is divisible by . Now, if the number is divisible by 37. Accordingly,

The corresponding divisibility criterion may be formulated as follows: In order to find out whether or not a given number is divisible by 37, it is sufficient to remove the last digit of , and to subtract the product of 11 and this digit from the number formed by the remaining digits of . The number is divisible by if and only if the number thus obtained is divisible by 37. Divisibility criteria of numbers of the type can be deduced in a similar manner.

References

[1]	N.N. Vorob'ev, "Divisibility criteria" , Moscow (1974) (In Russian)