Namespaces
Variants
Actions

Difference between revisions of "Divisibility criterion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
''by a natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336401.png" />''
+
<!--
 +
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.
 +
-->
  
A condition which is satisfied by a natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336402.png" /> if and only if it is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336403.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336404.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336405.png" /> would be.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
If the difference between two numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336406.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336407.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336408.png" />, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d0336409.png" /> will be divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364010.png" /> if and only if the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364011.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364012.png" />. This property forms the basis of many divisibility criteria. Let the notation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364013.png" /> in the decimal system have the form
+
''by a natural number d $''
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364014.png" /></td> </tr></table>
+
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
 
then
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364015.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364016.png" />;
+
$  A = a _ {0} + 10 A _ {1} $,  
 +
where $  A _ {1} = a _ {1} + 10 a _ {2} + \dots + 10  ^ {n-} 1 a _ {n} $;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364017.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364018.png" />;
+
$  A = a _ {0} + 10 a _ {1} + 100 A _ {2} $,  
 +
where $  A _ {2} = a _ {2} + 10 a _ {3} + \dots + 10  ^ {n-} 2 a _ {n} $;
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364019.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364020.png" />;
+
$  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} $;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364021.png" /></td> </tr></table>
+
$$
 +
{\dots \dots \dots \dots \dots \dots \dots . }
 +
$$
  
These equalities immediately yield divisibility criteria by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364022.png" />. Also, for a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364023.png" /> to be divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364025.png" /> it is necessary and sufficient for its last digit, i.e. the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364026.png" />, to be divisible by 2; for the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364027.png" /> to be divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364029.png" /> (by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364031.png" />) it is necessary and sufficient for the number represented by the two (respectively, three) last digits of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364032.png" />, i.e. the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364033.png" /> (the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364034.png" />) to be divisible by 4 (by 8). Since the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364035.png" /> is a multiple of 4, the divisibility criterion by 4 may also be stated as follows: A number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364036.png" /> is divisible by 4 if and only if the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364037.png" /> is divisible by 4.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364038.png" /> makes it possible to replace the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364039.png" /> (unless this number is too small) by some non-negative integer smaller than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364040.png" /> which is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364041.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364042.png" /> itself is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364043.png" />. In other words, each divisibility criterion by a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364044.png" /> is defined by some function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364045.png" />, assuming integral values and satisfying the conditions: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364046.png" /> for each natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364047.png" />; and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364048.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364049.png" /> if and only if the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364050.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364051.png" />. Any integer-valued function that satisfies the above conditions is known as a divisibility function for the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364052.png" />; the set of all such functions is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364053.png" />. It is clear that
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364054.png" /></td> </tr></table>
+
$$
 +
f _ {1} ( A)  = a _ {0}  \in  \Omega ( 2) \cap \Omega ( 5) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364055.png" /></td> </tr></table>
+
$$
 +
f _ {2} ( A)  = a _ {0} + 10 a _ {1}  \in  \Omega ( 4) \cap \Omega ( 25) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364056.png" /></td> </tr></table>
+
$$
 +
f _ {3} ( A)  = a _ {0} + 10 a _ {1} + 100 a _ {2}  \in  \Omega ( 8) \cap \Omega ( 125) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364057.png" /></td> </tr></table>
+
$$
 +
f _ {4} ( A)  = a _ {0} + 2 a _ {1}  \in  \Omega ( 4) .
 +
$$
  
 
Since
 
Since
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364058.png" /></td> </tr></table>
+
$$
 +
= ( a _ {0} + A _ {1} ) + 9 A _ {1}  = ( a _ {0} + a _ {1} +
 +
A _ {2} ) + 9 ( A _ {1} + A _ {2} ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364059.png" /></td> </tr></table>
+
$$
 +
=  
 +
\dots = ( a _ {0} + \dots + a _ {n} ) + 9 ( A _ {1} + \dots + A _ {n-} 1 ) ,
 +
$$
  
 
one has
 
one has
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364060.png" /></td> </tr></table>
+
$$
 +
f _ {5} ( A)  = a _ {0} + \dots + a _ {n}  \in  \Omega
 +
( 9)  \subset  \Omega ( 3) .
 +
$$
  
Thus, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364061.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364063.png" /> (by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364065.png" />) if and only if the sum of its digits is divisible by 3 (by 9). In a similar manner
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364066.png" /></td> </tr></table>
+
$$
 +
= ( a _ {0} - A _ {1} ) + 11 A _ {1}  = ( a _ {0} - a _ {1} +
 +
A _ {2} ) + 11 ( A _ {1} - A _ {2} ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364067.png" /></td> </tr></table>
+
$$
 +
=  
 +
\dots = ( a _ {0} - a _ {1} + \dots + ( - 1 )  ^ {n} a _ {n} ) +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364068.png" /></td> </tr></table>
+
$$
 +
+
 +
11 ( A _ {1} - A _ {2} + \dots + ( - 1 )  ^ {n-} 2 A _ {n-} 1 ) ,
 +
$$
  
 
so that
 
so that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364069.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364070.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364071.png" /> it is possible to find divisibility criteria by divisors of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364072.png" />. Thus, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364073.png" />, one obtains the following divisibility functions by 11 and by 101:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364074.png" /></td> </tr></table>
+
$$
 +
f _ {7} ( A)  = ( a _ {1} a _ {0} ) _ {10} +
 +
( a _ {3} a _ {2} ) _ {10} + ( a _ {5} a _ {4} ) _ {10} + \dots
 +
\in  \Omega ( 11) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364075.png" /></td> </tr></table>
+
$$
 +
f _ {8} ( A)  = ( a _ {1} a _ {0} ) _ {10} - ( a _ {3} a _ {2} ) _ {10} + ( a _ {5} a _ {4} ) _ {10} - \dots \in  \Omega ( 101) .
 +
$$
  
Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364076.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364081.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364082.png" /> if and only if the original number is divisible by 7, 11 or 13, respectively. Thus,
+
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,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364083.png" /></td> </tr></table>
+
$$
 +
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
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364084.png" /></td> </tr></table>
+
$$
 +
{} \dots \in  \Omega ( 7) \cap \Omega ( 11) \cap \Omega ( 13) .
 +
$$
  
If the integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364086.png" /> are coprime, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364087.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364088.png" /> if and only if the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364089.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364090.png" />. This idea is also frequently employed in constructing divisibility criteria. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364091.png" /> be some divisor of the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364092.png" />; the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364093.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364094.png" /> are then coprime, and it follows from the equation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364095.png" /></td> </tr></table>
+
$$
 +
Ac  = ( c a _ {0} + A _ {1} ) + ( 10 c - 1 ) A _ {1}  $$
  
that the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364096.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364097.png" /> if and only if the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364098.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d03364099.png" />. For instance, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640100.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640101.png" />, the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640102.png" /> is divisible by 19. Therefore
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640103.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640104.png" /> be some divisor of the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640105.png" />. It follows from the equation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640106.png" /></td> </tr></table>
+
$$
 +
Ac  = ( ca _ {0} - A _ {1} ) + ( 10c + 1 ) A _ {1}  $$
  
that the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640107.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640108.png" /> if and only if the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640109.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640110.png" />. Now, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640111.png" /> the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640112.png" /> is divisible by 37. Accordingly,
+
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,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640113.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640114.png" /> is divisible by 37, it is sufficient to remove the last digit of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640115.png" />, and to subtract the product of 11 and this digit from the number formed by the remaining digits of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640116.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640117.png" /> is divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640119.png" /> if and only if the number thus obtained is divisible by 37. Divisibility criteria of numbers of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033640/d033640120.png" /> can be deduced in a similar manner.
+
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====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,  "Divisibility criteria" , Moscow  (1974)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,  "Divisibility criteria" , Moscow  (1974)  (In Russian)</TD></TR></table>

Latest revision as of 19:36, 5 June 2020


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

[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