In 1861, A. Zbikowski (pronounced zih-bih-KOW-skee) of Minsk published a short article on divisibility tests in the Bulletin de la Classe physico-mathématique de l'Académie impériale des sciences de St. Pétersbourg [51]. Here he introduced a divisibility technique that appears to have been previously unknown. It also seems to have gone largely unnoticed for the better part of the following century. His method (and variations of it) has been independently rediscovered many times since. An excellent introduction to Zbikowski's criterion by Cherniavsky and Mouftakhov [6] is highly recommended to anyone with an interest in the subject of divisibility. For a discussion and comparison of the techniques of both Zbikowski and Pascal, we recommend [11].
3.1. Standard (subtraction) style Zbikowski tests
In [51], Zbikowski observed the following "curious property" concerning the divisibility of numbers by \(7\) (translated from French):
double the given integer units and subtract the product from the number of tens; if the remainder is divisible by \(7,\) the whole number will be also.
Symbolically, this says that if \(N=10a+b,\) then \(N\) is divisible by \(7\) provided that \(a-2b\) is divisible by \(7.\) Zbikowski proceeded to verify this assertion as follows: If \(N=10^n a_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0,\) then \(a_0\) represents the "integer units," and the "number of tens" is represented by
\[\frac{N-a_0}{10}=10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots+10a_2+a_1.\]
Subtracting \(2a_0\) from both sides yields
\[\frac{N-21a_0}{10}=10^{n-1}a_n+10^{n-2}a_{n-1}+\cdots+10a_2+a_1-2a_0\]
and so
\[N-21a_0=10(10^{n-1} a_n+10^{n-2}a_{n-1}+\cdots+a_1-2a_0).\]
Thus,
\[N=10\left(\frac{N-a_0}{10}-2a_0\right)+21a_0.\]
Therefore, since \(7\) divides the number of tens minus twice the units digit (by assumption), and \(7\) divides \(21a_0,\) it follows that \(7\) divides \(N,\) as was to be shown.
Though Zbikowski didn't mention it, even more is true: Since \(7\) and \(10\) are relatively prime it follows that if \(N\) is divisible by \(7\) then, since \(21a_0\) is necessarily divisible by \(7,\) then \((N-a_0)/10-2a_0\) must be divisible by \(7\) as well. In other words, a number \(N=10a+b\) is divisible by \(7\) if and only if \(a-2b\) is divisible by \(7.\) Brief consideration will confirm that this divisibility test for \(7\) works for both \(3\) and \(21\) as well.
Later in the same article, Zbikowski extended his method to develop divisibility tests for other divisors, \(d,\) that have multiples of the form \(10k+1\) (just as \(21=10(2)+1\) is a multiple of \(7\)). He provided specific tests for most of the primes from \(7\) to \(101.\) Zbikowski's method was rediscovered almost exactly by Paul Cohn in 1943 [7]. A delightful recounting of another rediscovery of Zbikowski's method by an 11-year-old boy named "Gus" is given in [33].
Zbikowski's generalization to divisors other than \(7\) can be stated as follows: If \(10k+1\) is a multiple of \(d,\) then \(d\) divides a number \(N=10a+b\) if and only if \(d\) divides \(a-kb\). To prove this, observe that since \(d\) divides \(10k+1\) we have that \(10k\equiv -1\,\,({\rm{mod}}\,\,d)\). Thus,
\[N=10a+b = 10a-(-1)b\equiv10a-10kb =10(a-kb)\,\,({\rm{mod}}\,\,{d}).\]
Thus, \(d\) divides \(N\) if and only if \(d\) divides \(10(a-kb)\). But \(d\) is relatively prime to \(10\) since \(d\) divides \(10k+1\). Therefore, \(d\) divides \(N\) if and only if \(d\) divides \(a-kb\).
We hasten to note that \(10(a-kb)\) and \(a-kb\) do not, in general, yield the same remainder upon division by \(d.\) Thus, Zbikowski's algorithm will not necessarily yield a number that is congruent to the integer being tested for divisibility by \(d.\) This is in stark contrast to Pascal's approach and its variations.
Developing your own subtraction style Zbikowski test for a divisor \(d\): Find a multiple of \(d\) that ends in \(1.\) (This can be done for any \(d\) ending in \(1, 3, 7,\) or \(9,\) but not otherwise.) Truncate the \(1\) from this multiple and let \(k\) denote the integer that results. Then a number \(N=10a+b\) is divisible by \(d\) if and only if \(a-kb\) is divisible by \(d.\)
Example 3.1. A subtraction style Zbikowski test for \(13\) can be recognized by noting that \(91\) is a multiple of \(13\) that ends in \(1.\) Truncating the \(1\) from \(91\) produces \(k=9.\) So, we can test \(608374\) for divisibility by \(13\) by multiplying \(4\) (the last digit of \(608374\)) by \(9\) and subtracting the result from \(60837\) to obtain \(60837-36=60801.\) Continuing this process produces the following string of intermediate calculations:
\[608374\rightarrow 60801\rightarrow 6071\rightarrow 598\rightarrow -13.\]
Since \(-13\) is divisible by \(13,\) so is \(608374.\)
In [46], it is observed that determinants can be used to describe subtraction style Zbikowski tests; e.g., \(13\) divides \(608374\) if and only if \(13\) divides
\[\left| \begin{array}{cc} 60837 & 4\\ 9 & 1\end{array}\right|.\]
This determinant style approach is used to generalize Zbikowski style tests to other bases in [47]. Alternative base Zbikowski tests are also discussed in [26] and [22].
3.2. Addition style Zbikowski tests
The subtraction style Zbikowski test can be easily modified as follows: If \(10k-1\) is a multiple of \(d,\) then \(d\) divides a number \(N=10a+b\) if and only if \(d\) divides \(a+kb\). The proof is almost identical to the proof of the subtraction style and we encourage you to complete the details. Articles in which both subtraction and addition style Zbikowski tests have been rediscovered include [31], [25], [30], [50], [44], [24], and [49].
Developing your own addition style Zbikowski test for a divisor \(d\): Find a multiple of \(d\) that ends in \(9.\) (This can be done for any \(d\) ending in \(1, 3, 7,\) or \(9\) but not otherwise.) Truncate the \(9\) from this multiple and let \(k\) denote the integer that results plus 1. Then a number \(N=10a+b\) is divisible by \(d\) if and only if \(a+kb\) is divisible by \(d.\)
Example 3.2. An addition style Zbikowski test for \(13\) can be recognized by noting that \(39\) is a multiple of \(13\) that ends in \(9.\) Truncating the \(9\) from \(39\) produces \(3,\) and so \(k=3+1=4\). Thus, we can test \(608374\) for divisibility by \(13\) by multiplying \(4\) (the last digit of \(608374\)) by \(4\) and adding the result to \(60837\) to obtain \(60837+16=60853\). Continuing this process produces the following string of intermediate calculations:
\[608374\rightarrow 60853\rightarrow 6097\rightarrow 637\rightarrow 91 \rightarrow 13.\]
Since \(13\) is divisible by \(13,\) so is \(608374.\)
3.3. Chunk style Zbikowski tests
The subtraction and addition style Zbikowski tests for a divisor \(d\) can be easily modified by using multiples of \(d\) of the form \(10^ik\pm 1\) \((i>1)\) rather than restricting our multiples to the form \(10k\pm 1.\) The proofs verifying the resulting tests are virtually identical to their counterparts and are left as exercises. For more details regarding this chunk style approach, see [21], [42], and [19].
Developing your own chunk style Zbikowski test (subtraction) for a divisor \(d\): Find a multiple of \(d\) of the form \(10^ik+1\). Truncate the \(1\) and the preceding \(i-1\) zeros from this multiple and let \(k\) denote the integer that results. Then a number \(N=10^ia+b\) is divisible by \(d\) if and only if \(a-kb\) is divisible by \(d.\)
Example 3.3. A chunk style Zbikowski test (subtraction) for \(7\) can be recognized by noting that \(301\, (=10^2\cdot 3 +1)\) is a multiple of \(7.\) Truncating \(01\) from \(301\) leaves \(k=3\). Thus, we can test \(239813\) for divisibility by \(7\) by multiplying \(13\) (the last two digits of \(239813\)) by \(3\) and subtracting the result from \(2398\) to obtain \(2398-39=2359.\) Repeating the process yields \(23-3(59)=-154,\) which is divisible by \(7.\) Thus, \(239813\) is divisible by \(7\) as well.
Developing your own chunk style Zbikowski test (addition) for a divisor \(d\): Find a multiple of \(d\) of the form \(10^ik-1.\) Truncate the last \(i\) nines from this multiple and let \(k\) denote the integer that results plus \(1.\) Then a number \(N=10^ia+b\) is divisible by \(d\) if and only if \(a+kb\) is divisible by \(d\).
Example 3.4. A chunk style Zbikowski test (addition) for \(7\) can be recognized by noting that \(399\, (=10^2\cdot 4-1)\) is a multiple of \(7.\) Truncating \(99\) from \(399\) and adding \(1\) to the result leaves \(k=4\). Thus, we can test \(239813\) for divisibility by \(7\) by multiplying \(13\) (the last two digits of \(239813\)) by \(4\) and adding the result to \(2398\) to obtain \(2398+52=2450.\) Repeating the process gives \(24+4(50)=224.\) Repeating once more gives \(2+96=98,\) which is divisible by \(7.\) Thus, \(239813\) is also divisible by \(7.\)
Algorithms that provide the multipliers that are used in the various styles of Zbikowski tests are discussed in [9], [40], [38], [13], [36], and [48]. It is interesting to note that Zbikowski style tests can also be developed by using fractional multipliers. In [34], Olsen developed a divisibility test for \(13\) by using a multiplier of \(1/3\) (since \(1/3\) of \(3\) is \(1,\) and \(1\) minus \(1\) is \(0\)): Thinking of \(585\) as "five hundred and seventy-fifteen" (rather than five hundred and eighty-five), he multiplied \(15\) by \(1/3\) and subtracted the result from \(57\) (giving \(52\)). Then, thinking of \(52\) as "forty-twelve," he multiplied \(12\) by \(1/3\) and subtracted from \(4\) (giving \(0\)). Since \(13\) divides \(0,\) it also divides \(585.\)
3.4. Flow-from-the-right style Zbikowski tests
We earlier discussed a flow-from-the-left style Pascal test and suggested that you consider whether a similar style divisibility test might exist that flows from the right. To our knowledge, no such test has been considered in the literature. Nonetheless, flow-from-the-right divisibility tests do exist and are simple consequences of the Zbikowski style tests already discussed. We will verify this by considering addition style Zbikowski tests. The case for the subtraction style test is left as an exercise.
Suppose that an integer \(d\) divides a positive integer of the form \(10k-1.\) Then \(10k\equiv 1\,\,({\rm{mod}}\,\,{d})\). Let \(N=[a_n a_{n-1} \cdots a_1 a_0].\) Then
| \(N\) | \(=10^n a_n+10^{n-1} a_{n-1}+\cdots+10^1 a_1 +a_0\) |
| \(=10(10^{n-1} a_n+\cdots+10^1 a_2+a_1)+a_0\) | |
| \(\equiv 10(10^{n-1} a_n+\cdots+ 10^1 a_2 +a_1)+10ka_0\,\,({\rm{mod}}\,\,{d})\) | |
| \(=10(10^{n-1} a_n+\cdots+ 10^1 a_2+(a_1+ka_0))\) | |
| \(=10^2(10^{n-2} a_n+\cdots+10^1 a_3 +a_2)+10(a_1+ka_0)\) | |
| \(\equiv 10^2(10^{n-2} a_n+\cdots+10^1 a_3 +a_2)+10\cdot 10k(a_1+ka_0)\,\,({\rm{mod}}\,\,{d})\) | |
| \(=10^2(10^{n-2} a_n+\cdots+10^1 a_3 +a_2+k(a_1+ka_0))\) | |
| \(\quad\quad\quad\vdots\) | |
| \(\equiv 10^{n}(a_n+k(a_{n-1}+k(a_{n-2}+\cdots+k(a_1+ka_0)\cdots)))\,\,({\rm{mod}}\,\,{d}).\) |
Since \(d\) divides \(10k-1\) (an integer ending in \(9\)), it follows that neither \(2\) nor \(5\) is a factor of \(d.\) Therefore, \(d\) does not divide \(10^{n}\) (since the only prime factors of \(10^{n}\) are \(2\) and \(5\)). Thus, we have that \(d\) divides \(N\) if and only if \(d\) divides \(a_n+k(a_{n-1}+k(a_{n-2}+\cdots+k(a_1+ka_0)\cdots)).\)
Developing your own flow-from-the-right style Zbikowski test (addition) for a divisor \(d\): Find an integer \(k\) such that \(d\) divides \(10k-1\). (This can be done for any \(d\) ending in \(1, 3, 7,\) or \(9,\) but not otherwise.) Let \(N=[a_n a_{n-1} \cdots a_1 a_0]\) and let \(N^\prime\) be the number obtained by multiplying \(a_0\) by \(k\) and adding \(a_1,\) then multiplying the result by \(k\) and adding \(a_2,\) etc. Then \(N\) is divisible by \(d\) if and only if \(N^\prime\) is divisible by \(d\).
Note that intermediate calculations can be replaced by \(({\rm{mod}}\,\,{d})\) equivalents in this (or any) Zbikowski style test.
Example 3.5. We can develop a flow-from-the-right divisibility test for \(19\) by noting that \(19=10(2)-1.\) To test whether \(78527\) is divisible by \(19,\) we begin by multiplying \(7\) (the last digit of \(78527\)) by \(2\) and adding \(2\) (the next-to-last digit). This gives \(16.\) Then, multiply \(16\) by \(2\) and add \(5\) to get \(37.\) Continuing this process gives \(82\) and \(171,\) respectively. Start the process anew with \(171\) and you will obtain \(19\) after \(2\) steps. Thus, \(78527\) is divisible by \(19.\)
3.5. Generalized Zbikowski tests
The addition and subtraction (chunk) style Zbikowski tests for a divisor \(d\) were constructed using multiples of \(d\) of the form \(10^i\pm 1.\) A generalization of these constructions is explored by E. Paul Goldenberg (without proof) in [18]. In this article, Goldenberg mused whether a divisibility test for \(23\) can be developed by recognizing that three times the first digit of \(23\) minus two times the second digit is equal to \(0.\) This prompted him to express \(18883\) in the form \(10a+b\) and observe that \(3a-2b=3(1888)-2(3)=5658.\) Continuing, he calculated \(3(565)-2(8)=1679,\) \(3(167)-2(9)=483,\) \(3(48)-2(3)=138,\) and \(3(13)-2(8)=23.\) From this evidence he suggested that \(10a+b\) is divisible by \(23\) provided that \(3a-2b\) is divisible by \(23.\) Upon further exploration, he noted that both \(138\) and \(15(1)-38\) are divisible by \(23,\) and used this evidence to purport that \(100a+b\) is divisible by \(23\) provided that \(15a-b\) is divisible by \(23.\) Goldenberg's observations can be summarized by the following theorem.
Theorem 3.6. Suppose that \(d\) divides both \(10^ia+b\) and \(ak_1-bk_2,\) and that \(d\) is relatively prime to both \(10\) and \(ab.\) Then \(d\) divides \(10^ix+y\) if and only if \(d\) divides \(xk_1-yk_2.\)
We offer the following justification of Goldenberg's claim.
Proof. Recall that for any integers \(m\) and \(n\) we have that \(d\,|\,(m-n)\Longleftrightarrow m\equiv n\,\,({\rm{mod}}\,\,{d}).\) Using (2) of Theorem 1.1 several times yields:
| \(d|(10^ix+y)\) | \(\Longleftrightarrow 10^ix\equiv -y\,\,({\rm{mod}}\,\,{d})\) |
| \(\Longleftrightarrow 10^ix(-b)\equiv -y(10^ia)\,\,({\rm{mod}}\,\,{d})\,\,\, ({\rm{since}}\,\, -b\equiv 10^ia\,\,({\rm{mod}}\,\,{d}))\) | |
| \(\Longleftrightarrow xb\equiv ya\,\,({\rm{mod}}\,\,{d})\) | |
| \(\Longleftrightarrow xb(ak_1)\equiv ya(bk_2)\,\,({\rm{mod}}\,\,{d})\,\,\, ({\rm{since}}\,\, ak_1\equiv bk_2\,\,({\rm{mod}}\,\,{d}))\) | |
| \(\Longleftrightarrow xk_1 \equiv yk_2\,\,({\rm{mod}}\,\,{d})\) | |
| \(\Longleftrightarrow d|(xk_1-yk_2).\,\Box\) |
This generalized technique provides a consistent means of constructing divisibility tests for any integer; however, the tests that result are often unappealing. For example, consider the divisibility test for \(29\) that is suggested by recognizing that \(9(2)-2(9)=0\):
A number \(10x+y\) is divisible by \(29\) if and only if \(9x-2y\) is divisible by \(29.\)
Testing \(902509\) for divisibility by \(29\) using this test yields the following string of intermediate calculations:
\[902509\rightarrow 812232\rightarrow731003\rightarrow 657894\rightarrow 592093\rightarrow\cdots\rightarrow 98658,\]
where the ellipsis represents \(16\) different numbers. On the other hand, since \(29\) divides \(203,\) we have that \(29\) divides \(100x+y\) if and only if \(29\) divides \(3x-2y.\) Testing \(902509\) with this rule gives:
\[902509\rightarrow 27057\rightarrow 696\rightarrow -174\rightarrow -145\rightarrow -87\]
(always ignoring the negative sign at each stage). Even better, since \(29\) divides \(1102,\) we have that \(100x+y\) is divisible by \(29\) if and only if \(2x-11y\) is divisible by \(29\):
\[902509\rightarrow 17951\rightarrow -203 \rightarrow -29.\]
Developing your own Generalized Zbikowski test for a divisor \(d\) \((d\) relatively prime to \(10)\): Find integers \(a,\) \(b\) and \(i\) such that \(d\) divides \(10^i a+b\) and \(d\) is relatively prime to \(ab.\) Find integers \(k_1\) and \(k_2\) for which \(ak_1-bk_2\) is a multiple of \(d.\) (Note that \(k_1=b\) and \(k_2=a\) will always work.) Then a Generalized Zbikowski test for \(d\) can be stated as follows:
An integer \([a_n a_{n-1} \cdots a_0]\) is divisible by \(d\) if and only if \(k_1[a_n \cdots a_i]-k_2[a_{i-1} \cdots a_0]\) is divisible by \(d.\)
Example 3.7. We can develop a Generalized Zbikowski test for \(223\) by noting that \(23(2)-2(23)=0\) is a multiple of \(223.\) Since this calculation used the last two digits of \(223,\) we can test \(368173\) for divisibility by \(223\) by separating it into \(3681\) and \(73\) and then calculating \(23(3681)-2(73)=84517.\) Beginning anew with \(84517\) yields \(23(845)-2(17)=19401.\) Continuing, we obtain
\[368173\rightarrow 84517\rightarrow 19401 \rightarrow 4460\rightarrow 892\rightarrow 0.\]
Since \(223\) divides \(0,\) we have that \(223\) divides \(368173\) as well.