View source for Divisibility criterion

<!--
d0336401.png
$#A+1 = 111 n = 0
$#C+1 = 111 : ~/encyclopedia/old_files/data/D033/D.0303640 Divisibility criterion
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''by a natural number  $  d $''

A condition which is satisfied by a natural number  $  A $
if and only if it is divisible by  $  d $. 
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  $  A $
by  $  d $
would be.

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

$$ 
A  =  ( a _ {n} \dots a _ {0} ) _ {10}  = \ 
a _ {0} + 10a _ {1} + \dots + 10  ^ {n} a _ {n} ;
$$

then

$  A = a _ {0} + 10 A _ {1} $, 
where  $  A _ {1} = a _ {1} + 10 a _ {2} + \dots + 10  ^ {n-} 1 a _ {n} $;

$  A = a _ {0} + 10 a _ {1} + 100 A _ {2} $, 
where  $  A _ {2} = a _ {2} + 10 a _ {3} + \dots + 10  ^ {n-} 2 a _ {n} $;

$  A = a _ {0} + 10 a _ {1} + 100 a _ {2} + 1000 A _ {3} $, 
where  $  A _ {3} = a _ {3} + 10 a _ {4} + \dots + 10  ^ {n-} 3 a _ {n} $;

$$ 
{\dots \dots \dots \dots \dots \dots \dots . }
$$

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

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

$$ 
f _ {1} ( A)  =  a _ {0}  \in  \Omega ( 2) \cap \Omega ( 5) ,
$$

$$ 
f _ {2} ( A)  =  a _ {0} + 10 a _ {1}  \in  \Omega ( 4) \cap \Omega ( 25) ,
$$

$$ 
f _ {3} ( A)  =  a _ {0} + 10 a _ {1} + 100 a _ {2}  \in  \Omega ( 8) \cap \Omega ( 125) ,
$$

$$ 
f _ {4} ( A)  =  a _ {0} + 2 a _ {1}  \in  \Omega ( 4) .
$$

Since

$$ 
A  =  ( a _ {0} + A _ {1} ) + 9 A _ {1}  =  ( a _ {0} + a _ {1} +
A _ {2} ) + 9 ( A _ {1} + A _ {2} ) =
$$

$$ 
= 
\dots =  ( a _ {0} + \dots + a _ {n} ) + 9 ( A _ {1} + \dots + A _ {n-} 1 ) ,
$$

one has

$$ 
f _ {5} ( A)  =  a _ {0} + \dots + a _ {n}  \in  \Omega
( 9)  \subset   \Omega ( 3) .
$$

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

$$ 
A  =  ( a _ {0} - A _ {1} ) + 11 A _ {1}  =  ( a _ {0} - a _ {1} +
A _ {2} ) + 11 ( A _ {1} - A _ {2} ) =
$$

$$ 
= 
\dots =  ( a _ {0} - a _ {1} + \dots + ( - 1 )  ^ {n} a _ {n} ) +
$$

$$ 
+ 
11 ( A _ {1} - A _ {2} + \dots + ( - 1 )  ^ {n-} 2 A _ {n-} 1 ) ,
$$

so that

$$ 
f _ {6} ( A)  =  a _ {0} - a _ {1} + \dots + ( - 1 )  ^ {n}
a _ {n}  \in  \Omega ( 11) .
$$

If the numbers are represented in the numeral system with base  $  10  ^ {k} $, 
where  $  k = 2 , 3 \dots $
it is possible to find divisibility criteria by divisors of the type  $  10  ^ {k} \pm  1 $. 
Thus, if  $  k = 2 $, 
one obtains the following divisibility functions by 11 and by 101:

$$ 
f _ {7} ( A)  =  ( a _ {1} a _ {0} ) _ {10} +
( a _ {3} a _ {2} ) _ {10} + ( a _ {5} a _ {4} ) _ {10} + \dots
\in  \Omega ( 11) ,
$$

$$ 
f _ {8} ( A)  =  ( a _ {1} a _ {0} ) _ {10} - ( a _ {3} a _ {2} ) _ {10} + ( a _ {5} a _ {4} ) _ {10} - \dots \in  \Omega ( 101) .
$$

Since  $  10  ^ {3} + 1 = 7 \cdot 11 \cdot 13 $, 
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  $  7 $, 
$  11 $
or  $  13 $
if and only if the original number is divisible by 7, 11 or 13, respectively. Thus,

$$ 
f _ {9} ( A)  =  ( a _ {2} a _ {1} a _ {0} ) _ {10} -
( a _ {5} a _ {4} a _ {3} ) _ {10} + ( a _ {8} a _ {7} a _ {6} ) _ {10} - \dots
$$

$$ 
{} \dots \in  \Omega ( 7) \cap \Omega ( 11) \cap \Omega ( 13) .
$$

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

$$ 
Ac  =  ( c a _ {0} + A _ {1} ) + ( 10 c - 1 ) A _ {1}  $$

that the number  $  A $
is divisible by  $  d $
if and only if the number  $  A _ {1} + ca _ {0} $
is divisible by  $  d $. 
For instance, if  $  d = 19 $, 
$  c = 2 $, 
the difference  $  10c - 1 $
is divisible by 19. Therefore

$$ 
f _ {10} ( A)  =  A _ {1} + 2 a _ {0}  \in  \Omega ( 19) .
$$

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

$$ 
Ac  =  ( ca _ {0} - A _ {1} ) + ( 10c + 1 ) A _ {1}  $$

that the number  $  A $
is divisible by  $  d $
if and only if the number  $  A _ {1} - ca _ {0} $
is divisible by  $  d $. 
Now, if  $  c = 11 $
the number  $  10c + 1 $
is divisible by 37. Accordingly,

$$ 
f _ {11} ( A)  =  A _ {1} - 11 a _ {0}  \in  \Omega ( 37) .
$$

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

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,   "Divisibility criteria" , Moscow  (1974)  (In Russian)</TD></TR></table>