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) |
How to Cite This Entry:
Divisibility criterion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Divisibility_criterion&oldid=46758
This article was adapted from an original article by V.I. Nechaev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098.
See original article