The earliest known divisibility test we have found comes from the Babylonian Talmud.  It was used to calculate the given year within a Sabbatical Cycle; that is, it provides the remainder obtained upon dividing an integer \(N\) by \(7\):

... put aside the hundreds as Jubilee Cycles and convert the remainder into Sabbatical Cycles [of seven years each] after adding thereto two years for every complete century; what is left over will give him the number of the given year in the current Sabbatical Cycle [1].

Translated into the language of mathematics, the passage implies that for integers \(N,\) \(a,\) and \(b\) with \(N=100a+b,\) we have that

\[100a+b\equiv 2a+b\,\,({\rm{mod}}\,\,7).\]

In other words, \(100a+b\) and \(2a+b\) yield the same remainder upon division by \(7.\)  For example, \(1866=100(18)+66\equiv 2(18)+66 = 102\,\,({\rm{mod}}\,\,7),\) and \(102\equiv 2(1)+2=4\,\,({\rm{mod}}\,\,7).\)  Therefore, \(1866\equiv4\,\,({\rm{mod}}\,\,7).\)  Consequently, since \(4\) is not divisible by \(7,\) neither is \(1866.\)

The Talmud test is a minor variant of a class of divisibility tests that was described by Blaise Pascal (1623-1662) in an essay entitled De Numeris Multiplicibus [37] that was likely written prior to 1654.  As we shall see, Pascal's method can be used to devise divisibility tests of a variety of styles for any integer \(d\).  In the case that a number fails to be divisible by \(d,\) all of these tests have the ability to recognize the remainder obtained upon division by \(d.\)  They are all explained easily by the following theorem:

Theorem 1.1.  Let \(d\) be a positive integer, and let \(a,\) \(a^\prime,\) \(b\) and \(b^\prime\) be integers for which \(a\equiv a^\prime\,\,({\rm{mod}}\,\,d)\) and \(b\equiv b^\prime\,\,({\rm{mod}}\,\,d).\) Then

(1)  \(a+b\equiv a^\prime+b^\prime\,\,({\rm{mod}}\,\,d)\)

(2)  \(ab\equiv a^\prime b^\prime\,\,({\rm{mod}}\,\,d).\)

Proof.  To prove (1), note first that \((a+b)-(a^\prime+b^\prime)= (a-a^\prime)+(b-b^\prime).\)  But since \(a-a^\prime=dq_1\) and \(b-b^\prime=dq_2\) for some integers \(q_1\) and \(q_2,\) it follows that \((a+b)-(a^\prime+b^\prime)=d(q_1+q_2)\).  Thus, \(a+b\equiv a^\prime+b^\prime\,\,({\rm{mod}}\,\,d).\) \(\Box\)

To prove (2), observe that

	\(ab-a^\prime b^\prime\)	\(=ab - a^\prime b + a^\prime b - a^\prime b^\prime\)
		\(=(a-a^\prime) b+(b-b^\prime)a^\prime\)
		\(=dq_1 b + dq_2a^\prime\)
		\(=d(q_1 b+q_2a^\prime).\)

Thus, \(ab\equiv a^\prime b^\prime\,\,({\rm{mod}}\,\,d).\)

The method that Blaise Pascal introduced in De Numeris Multiplicibus is elementary yet powerful.  It is accessible to anyone with a basic understanding of arithmetic (and an interest in mathematical discovery), yet it can be used to provide divisibility tests for every positive integer.

2.1.  Standard style Pascal tests

In [37], Pascal observed that the following remainders are obtained upon dividing powers of \(10\) by \(7:\)

\(10^k\)	\(10^9\)	\(10^8\)	\(10^7\)	\(10^6\)	\(10^5\)	\(10^4\)	\(10^3\)	\(10^2\)	\(10^1\)	\(10^0\)
\(({\rm{mod}}\,\, 7)\)	\(6\,\,\,\)	\(2\,\,\,\)	\(3\,\,\,\)	\(1\,\,\,\)	\(5\,\,\,\)	\(4\,\,\,\)	\(6\,\,\,\)	\(2\,\,\,\)	\(3\,\,\,\)	\(1\,\,\,\)

He then used Theorem 1.1 to conclude that

\(287,542,178\)	\(= [2\,8\,7\,5\,4\,2\,1\,7\,8]\)
	\(= 10^8(2)+10^7(8)+10^6(7)+10^5(5)+10^4(4)+10^3(2)+10^2(1)+10^1(7)+10^0(8)\)
	\(\equiv 2(2)+3(8)+1(7)+5(5)+4(4)+6(2)+ 2(1)+3(7)+1(8)\,\,({\rm{mod}}\,\, 7)\)
	\(= 119\)
	\(\equiv 2\cdot 1+3\cdot 1+1\cdot 9\,\,({\rm{mod}}\,\, 7)\)
	\(= 14.\)

Thus, since \(7\) divides \(14,\) he concluded that \(7\) divides \(287,542,178\) as well.

Note that we are using \([a_n a_{n-1} \cdots a_1 a_0]\) to represent  \(10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0\).  This notation will be employed throughout the paper.  When expressing numbers in bases other than \(10,\) we will use \([a_n a_{n-1} \cdots a_1 a_0]_b\) to mean \(b^na_n+b^{n-1}a_{n-1}+\cdots+b\cdot a_1+a_0\).

Divisibility tests for any positive integer \(d\) can be similarly designed by constructing tables of remainders that are obtained upon dividing powers of \(10\) by \(d.\)  In [29], McCaffrey noted that such tables can be found systematically by dividing \(d\) into \(1\) (by hand) and keeping track of the remainders along the way.  He further observed that since the division algorithm ensures only \(d\) possible remainders (\(0\) through \(d-1\)) when dividing by \(d,\) this process must eventually yield a repeating cycle.  (When \(1/d\) has a terminating decimal expansion, the resulting list of remainders is a cycle of zeroes.)  Adapting [11], we denote this ordered list of remainders by \(\{r_k, r_{k-1},\cdots, r_j|r_{j-1},\cdots, r_0\}\) where \(10^i\equiv r_i\,\,({\rm{mod}}\,\,d)\) for each \(i\ge 0\) and \(10^{k+1}\equiv r_j\equiv 10^j\,\,({\rm{mod}}\,\,d)\) begins the first repeated cycle. (Alternatively, we may write \(10^i\equiv r_{i-(k-j+1)}\,\,({\rm{mod}}\,\,d)\) for each \(i>k.\))  We refer to this list of remainders as a divisibility list for \(d.\)  Other divisibility lists for \(d\) can be generated by replacing any \(r_i\) with an integer that is congruent to \(r_i\,\,({\rm{mod}}\,\,d).\)  Thus, \(\{5, 4, 6, 2, 3, 1\}\) and \(\{-2, -3, -1, 2, 3, 1\}\) are both divisibility lists for \(7.\)

Some of our most familiar tests for divisibility can be described as Pascal tests that are efficiently explained by providing the associated divisibility list.  For example, the rule asserting that an integer \(N\) is divisible by \(9\) if and only if the sum of its digits is divisible by \(9\) can be explained by noting that \(\{1\}\) is a divisibility list for \(9.\)  This is immediately verified by noting that \(9\) clearly divides \(10^i-1\) for every \(i\) since every digit of the base \(10\) representation \(10^i-1\) is a \(9.\)  Thus, \(10^i\equiv 1 \,\,({\rm{mod}}\,\,{9}).\)  It is clear that Pascal tests for divisibility exist for every positive integer.  Divisibility lists that explain some of our most familiar divisibility tests as Pascal tests are provided in the table below:

\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(8\)	\(10\)	\(11\)
\(\{0|1\}\)	\(\{1\}\)	\(\{0|2,1\}\)	\(\{0|1\}\)	\(\{4|1\}\)	\(\{0|4,2,1\}\)	\(\{0|1\}\)	\(\{-1,1\}\)

How to develop your own Pascal test for a divisor \(d\):  Calculate the remainders (\(r_0,\) \(r_1,\) \(r_2,\) etc.) obtained by dividing \(d\) into consecutive powers of \(10\) (\(10^0,\) \(10^1,\) \(10^2,\) etc.).  Recognize that a repeating remainder begins a repeating cycle.  Generate the divisibility list that results from this process, \(\{r_k,\cdots,r_j | r_{j-1},\cdots, r_0\}\).  Modify any of the \(r_i\) to an equivalent integer \(({\rm{mod}}\,\,d)\) if you wish.  Your divisibility test for \(d\) can then be stated as follows:

An integer \(N=[a_n a_{n-1} \cdots a_1 a_0]\) is divisible by \(d\) if and only if \(N^\prime=r_n a_n + r_{n-1} a_{n-1} + \cdots + r_0 a_0\) is divisible by \(d\).  (If \(k<n,\) then \(r_{k+1},\) etc. follow the repeating pattern that began with \(r_j\).)  This test can be repeated with \(N^\prime,\) if desired.

Example 2.1.  Suppose that a Pascal divisibility test is desired for the divisor \(110.\)  Dividing \(1\) by \(110\) (by hand) produces remainders \(r_0=1,\) \(r_1=10,\) and \(r_3=100\).  Since \(r_4=10,\) the remaining remainders will repeatedly cycle between \(10\) and \(100;\) thus, a divisibility list for \(110\) is \(\{100,10|1\}.\)  Since \(100\equiv -10\,\,({\rm{mod}}\,\,{110}),\) then \(\{-10,10|1\}\) is also a divisibility list for \(110.\)  Therefore, we can test whether \(7408170\) is divisible by \(110\) by noting that

\[-10(7)+10(4)+(-10)(0)+10(8)+(-10)(1)+10(7)+1(0)=110.\]

Since \(110\) is clearly divisible by \(110,\) so is \(7408170.\)

2.2.  Change-of-base style Pascal tests

Pascal used the base \(10\) representation of numbers when describing his method of testing for divisibility.  However, it is clear that his test works in any base (see [16] for a discussion of bases \(2\) through \(9\) and [43] for an example in base \(30\)).  In [27], Joseph-Louis Lagrange (1736-1813) observed that if a number is expressed in any base \(d+1,\) its remainder upon division by \(d\) is equal to the remainder obtained when dividing the sum of its digits by \(d.\)  This is just an extension of the divisibility rule for \(9\) (for numbers expressed in base \(10\)) that was discussed above.  It also works for any divisor of \(d\) (for numbers expressed in base \(d+1\)), just as it works for \(3\) in base \(10.\)  It is amusing to note that in base \(61,\) the sum-of-digits test applies to divisors \(2, 3, 4, 5, 6, 10, 12, 15, 20, 30\) and \(60\)!

Of course, most change-of-base calculations require at least as many steps as ordinary division.  Thus, change-of-base style divisibility tests are usually impractical.  We do note that a recent article by Sandy Ganzell offers suggestions that might simplify change-of-base calculations for small multiples of \(10,\) thereby providing useful change-of-base style Pascal tests for specific cases [17].

How to develop your own change-of-base style Pascal test for a divisor \(d\):  Express a number \(N\) in base \(b+1\) where \(b\) is a multiple of \(d.\)  Then \(N\) is divisible by \(d\) if and only if the sum of the digits of \(N\) is divisible by \(d.\)

Example 2.2 (from [17]). Since \(21506\) (in base \(10\)) is equal to \([13\, 17\,26]_{40}\) (in base \(40\)), we have that \(13+17+26=56\) is congruent to \(21506\) modulo each of \(3, 13,\) and \(39.\)

Pascal's method (in base \(10\)) has been rediscovered many times by many authors (for example, see [20], [29], [8], [28], [4], and [11]).  Some authors (see [32] and [35]) have published divisibility tests that are devised by applying a minor modification to Pascal's approach.  This modification is discussed in the next subsection.

2.3.  The "chunk"-style Pascal test

This variation of the Pascal test considers blocks of digits of a number \(N\) rather than considering each place value individually.  From the table of values of \(10^k\,\,({\rm{mod}}\,\, 7),\) we have that when \(7\) is divided into \(10^0,\) \(10^3,\) \(10^6,\) etc., the resulting remainders alternate between \(1\) and \(6.\)  Since  \(6\equiv -1\,\,({\rm{mod}}\,\,{7})\) it follows that

\(287,542,178\)	\(=  10^6\cdot 287+10^3\cdot 542+178\)
	\(\equiv 1\cdot 287+(-1)\cdot 542+1\cdot 178 \,\,({\rm{mod}}\,\,7)\)
	\(=  -77,\)

which is clearly divisible by \(7.\)  Thus, \(287,542,178\) is divisible by \(7\) as well.  By "chunking" a number into groups of three digits each (beginning at the right) and alternately adding and subtracting the resulting three-digit numbers (the leftmost of these might have fewer than three digits), we arrive at a new number that is congruent to our original number \(({\rm{mod}}\,\,7).\)  One need not use blocks of equal length when designing tests via this method.  Indeed, Pascal-type tests that use blocks of digits of various lengths have been frequently rediscovered in the literature (e.g., [45], [23], and [2]).  As an example, we could "chunk" \(287,542,178\) into blocks of sizes \(2, 3,\) and \(4\) (beginning at the right).  This yields

\(287,542,178\)	\(=  10^5\cdot 2875+10^2\cdot 421+78\)
	\(\equiv 5\cdot 2875+1\cdot 421+ 1\cdot 78\,\,({\rm{mod}}\,\,7)\)
	\(=  15295.\)

Then, by chunking in blocks of \(3\) as we did earlier we see that \(15295\equiv -15 + 295\,\,({\rm{mod}}\,\, 7)\).  This equals \(280,\) which is clearly divisible by \(7.\)

The Talmud test for divisibility of a number \(N\) by \(7\) is a Pascal test that uses two blocks of potentially unequal length.  The rightmost block consists of the last two digits of \(N\) while the leftmost block consists of the remaining digits.  Writing \(N\) as \([a_n a_{n-1} \cdots a_1 a_0],\) the Talmud test asserts that \([a_n a_{n-1} \cdots a_1 a_0]\) is divisible by \(7\) if and only if \(2\cdot [a_n a_{n-1} \cdots a_3 a_2] + [a_1 a_0]\) is divisible by \(7\) since \(100\equiv 2\,\,({\rm{mod}}\,\, 7)\) and

\([a_n a_{n-1} \cdots a_1 a_0]\)	\(=  100\cdot [a_n a_{n-1} \cdots a_3 a_2]+ [a_1 a_0]\)
	\(\equiv 2\cdot [a_n a_{n-1} \cdots a_3 a_2]+ [a_1 a_0]\,\,({\rm{mod}}\,\, 7).\)

This and all Pascal-type tests can be applied repeatedly as desired.  Applying the Talmud test repeatedly to \(287,542,178\) produces the following sequence of numbers:

\[287,542,178 \rightarrow 5,750,920 \rightarrow 115,038 \rightarrow 2338 \rightarrow 84.\]

Since \(84\) is divisible by \(7,\) so is \(287,542,178\).

Designing your own chunk-style Pascal test for a divisor \(d\):  Begin by deciding on how you'd like to chunk the integers to be tested.  We'll illustrate by chunking \(N=[a_n \cdots a_0]\) into \([a_n\cdots a_4], [a_3 a_2]\) and \([a_1 a_0]\).  Calculate \(r_2\equiv10^2\,\,({\rm{mod}}\,\,d)\) and \(r_4\equiv10^4\,\,({\rm{mod}}\,\,d)\) (for this illustration).  Modify any of these remainders to an equivalent integer \(({\rm{mod}}\,\,d)\) if you wish.  Your divisibility test for \(d\) can then be stated as follows:

An integer \(N=[a_n a_{n-1} \cdots a_1 a_0]\) is divisible by \(d\) if and only if \(N^\prime=r_4[a_n\cdots a_4]+r_2[a_3 a_2]+[a_1 a_0]\) is divisible by \(d.\)  This test can be repeated with \(N^\prime,\) if desired.

Example 2.3.  Suppose that a chunk-style Pascal test is desired for the divisor \(49.\)  We'll choose to chunk our numbers as described in the illustration above.  Observe that \(2\equiv 10^2\,\,({\rm{mod}}\,\,{49})\) and \(4\equiv 10^4\,\,({\rm{mod}}\,\,{49})\).  Therefore, we can test whether \(322351\) is divisible by \(49\) by noting that

\[4(32)+2(23)+51=128+46+51=225.\]

Repeating the test with \(225\) gives \(2(2)+25=29\) which is clearly not divisible by \(49.\)  Therefore, \(322351\) is also not divisible by \(49.\)  However, we note that \(29\) is the remainder obtained upon dividing \(322351\) by \(49.\)  Again, the reason for this "coincidence" is completely explained by Theorem 1.1.

2.4.  Flow-from-the-left style Pascal tests

Observe that if \(r\equiv 10\,\,({\rm{mod}}\,\,d),\) then \(r^i\equiv 10^i\) for all positive integers \(i\) by (2) of Theorem 1.1.  It follows that:

If \(\{r_n, r_{n-1},\cdots,r_1,r_0\}\) is a divisibility list for \(d,\) then so is \(\{r^n, r^{n-1},\cdots,r,1\}.\)

This observation is used in [3] to show that \(168\) is divisible by \(7\):  Since \(3\equiv 10\,\,({\rm{mod}}\,\, 7),\) it follows that

\[168=10^2\cdot 1+10^1\cdot 6 + 8 \equiv 3^2 \cdot 1+3\cdot 6+8 = 35\,\,({\rm{mod}}\,\,7),\]

which is clearly divisible by \(7.\)

By writing \(3^2\cdot 1+3\cdot 6 + 8\) as \(3\cdot (3\cdot 1 + 6)+8\) and interpreting this nested expression appropriately, we obtain a new style of the Pascal test that appears in [14] and [19].  We have chosen to call this the "flow-from-the-left" style because of the way that the test is executed:  Beginning with the innermost parenthesized expression above, we multiply the first (leftmost) digit of \(168\) by \(3\) and add the second digit (\(3\cdot 1 + 6=9\)).  Then, multiply this result by \(3\) and add the third digit (\(3\cdot 9+8=35\)).  Since \(35\) is divisible by \(7,\) so is \(168.\)  Clearly, this procedure might become unwieldy for numbers with many digits.  However, the process is greatly facilitated by converting each calculation along the way to a smaller \(({\rm{mod}}\,\,7)\) equivalent.  Testing \(287,542,178\) (again!) for divisibility by \(7\) using the flow-from-the-left approach yields the following sequence of intermediate \(({\rm{mod}}\,\,7)\) calculations (beginning with \(3\cdot 2+8\equiv 0\)):

\[0 \rightarrow 0 \rightarrow 5 \rightarrow 5 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 0.\]

So, \(287,542,178\equiv 0\,\,({\rm{mod}}\,\, 7)\).

It is interesting to note that this flow-from-the-left style of Pascal test for divisibility was known before Pascal was born.  According to Leonard Eugene Dickson (1874-1954) [10], Pierre Forcadel included the test provided above for divisibility by \(7\) in L'Arithmeticqve de P. Forcadel de Beziers in 1556.

We now show how flow-from-the-left can be combined with chunking to develop more powerful tests of divisibility.

Observe again that \(10^3\equiv -1\,\,({\rm{mod}}\,\, 7)\).  It follows that

\(287,542,178\)	\(=10^6\cdot 287+10^3\cdot 542+178\)
	\(= (10^3)^2\cdot 287+10^3\cdot 542+178\)
	\(\equiv (-1)^2\cdot 287+ (-1)\cdot 542 + 178\,\,({\rm{mod}}\,\, 7).\)

This can be rewritten as \(-1\cdot (-1\cdot 287 + 542) + 178,\) illustrating how the flow-from-the-left style Pascal test can be combined with the chunk style.  By employing these styles together, the divisibility of \(287,542,178\) by \(7\) can be determined in two steps:

\[(-1)287+542=255 \rightarrow (-1) 255+178=-77.\]

Developing your own flow-from-the-left style Pascal test for a divisor \(d\):  Let \(k\) be any integer for which \(k\equiv 10^i\,\,({\rm{mod}}\,\,d)\).  Your divisibility test for \(d\) can then be stated as follows: 

Chunk an integer \(N\) into groups of \(i\) digits beginning at the right.  (The leftmost group may have fewer than \(i\) digits.)  Let \(N^\prime\) be the number formed as follows:  multiply the leftmost group by \(k\) and add the next group; multiply the result by \(k\) and add the next group; etc.  Replace any intermediate calculation with a \(({\rm{mod}}\,\,d)\) equivalent, if desired. Continue until the last group has been added.  Then \(N\) is divisible by \(d\) if and only if \(N^\prime\) is divisible by \(d\).

Observe that we must have \(-10^i<k<10^i\) in order for this test to be of any practical value.

Example 2.4.  Noticing that \(100\equiv -2\,\,({\rm{mod}}\,\,{17}),\) we begin testing \(84592\) for divisibility by \(17\) by first chunking it into groups of two (beginning at the right).  We multiply the leftmost chunk by \(-2\) and add the next chunk; then, multiply the result by \(-2\) and add the last chunk:

\[-2(8)+45=29 \rightarrow -2(29)+92=34.\]

Alternatively, if we had recognized that \(45\equiv 11\) and \(92\equiv 7\,\,({\rm{mod}}\,\,{17}),\) then the above sequence of intermediate calculations would have been somewhat simplified:

\[-2(8)+11\equiv -5 \rightarrow -2(-5)+7=17\,\,({\rm{mod}}\,\,17).\]

Is \(102\) divisible by \(17\)?  Using the test just described provides an answer almost immediately: \(-2\) times the first digit plus the number formed by the last two digits gives \(0,\) a multiple of \(17.\)  Let's probe a bit further.  Notice that \(1003\) is also a multiple of \(17,\) and that \(-3\) times the first digit (of \(1003\)) plus the number formed by the last three digits also gives \(0.\)  Does this suggest another divisibility rule for \(17\)?  Let's test \(84592\) by multiplying \(-3\) times \(84\) and adding \(592.\)  This gives \(340,\) which is certainly a multiple of \(17.\)  Indeed, by recognizing that \(d\) divides \(10^i+b\) for any integer \(b,\) we can always develop a flow-from-the-left divisibility test for \(d\):  Just chunk integers into groups of \(i\) digits (beginning at the right) and apply the flow-from-the-left algorithm with \(-b\) as the multiple. The reason this works is straightforward:  if \(d\) divides \(10^i+b,\) then \(10^i\equiv -b\,\,({\rm{mod}}\,\,{d})\).  So, since \(17\) (\(=10^1+7\)) is a multiple of \(17,\) we could chunk numbers into groups of \(1\) and use \(-7\) as our multiple for an alternative flow-from-the-left style Pascal test for \(17.\)  Similarly, we can use \(-3\) and \(-9\) as the multiples defining flow-from-the-left style tests for \(13\) and \(19,\) respectively.  Also, \(-11\) could be used as a multiple defining a flow-from-the-left test for \(111\) (using chunks of \(2\) digits) as well as for \(3\) and \(37\) (which are factors of \(111\)).

All of this raises a very natural question:  If we can obtain a flow-from-the-left divisibility test for \(19\) by noting that \(-9\) times the first (leftmost) digit of \(19,\) plus the second digit, is equal to \(0,\) might we also obtain a  flow-from-the-right test for \(91\) by recognizing that \(-9\) times the last digit of \(91,\) plus the preceding digit, is equal to \(0\)?  We'll answer this question later, but we hope that you might investigate it on your own before reading further.

2.5.  Leap-from-the-left style Pascal tests

In 1859, Francis Elefanti proposed a curious test in [15] to determine that \(71491\) is divisible by \(7\):  Truncate the first digit (\(7\)) and subtract it from the digit three places to its right (\(9\)).  (As we shall see, the \(7\) is actually to be subtracted from \(149\).)  Keep all other digits as they were.  This yields \(1421.\)  Repeating the process, \(421\) minus \(1\) yields \(420.\)  Since \(420\) is clearly divisible by \(7,\) Elefanti asserted that \(71491\) is as well.  Why does this work?  Perhaps you associated "three places to the right" with \(10^3\) and recalled that \(1000\) is congruent to \(-1\,\,({\rm{mod}}\,\,{7})\).  This is not a coincidence.  Indeed, we can use the fact that \(100\) is congruent to \(2\,\,({\rm{mod}}\,\, 7)\) to hypothesize a similar test:  Multiply the first digit of \(71491\) by \(2\) and add the result to \(14.\)  After truncating the first digit, this yields \(2891.\)  Doubling \(2\) and adding to \(89\) yields \(931.\)  Finally, \(2(9)+31=49\) which is a multiple of \(7.\)

Leap-from-the-left is really just a chunk-style Pascal test in disguise.  To see why Elefanti's test works, note that \(71491\) is equal to \(10(7149)+1\) and chunk \(7149\) into groups of \(3\) starting at the right \((7\) and \(149).\)  Since \[7149=10^3\cdot 7+149\equiv -1\cdot 7+149\,\,({\rm{mod}}\,\,{7}),\] we have that

\(71491\)	\(= 10(7149)+1\)
	\(= 10(10^3\cdot 7+149)+1\)
	\(\equiv 10(-1\cdot 7+149)+1\,\,({\rm{mod}}\,\,{7})\)
	\(= 10(142)+1\)
	\(= 1421.\)

A general proof for divisibility of \([a_n a_{n-1} \cdots a_1 a_0]\) by \(d\) can be given as follows:  Let \(i<n\) and let \(k\equiv 10^i\,\,({\rm{mod}}\,\,{d})\).  Then we have that

\([a_n \cdots a_{n-i} a_{n-i-1} \cdots a_1 a_0]\)	\(=10^{n-i}[a_n a_{n-1} \cdots a_{n-i}]+[a_{n-i-1} \cdots a_1 a_0]\)
	\(\equiv 10^{n-i}[a_{n-1} \cdots (a_{n-i}+ka_n)]+[a_{n-i-1} \cdots a_1 a_0]\,\,({\rm{mod}}\,\, {d})\)
	\(= [a_{n-1} a_{n-2} \cdots a_{n-i+1} (a_{n-i}+ka_n) a_{n-i-1} \cdots a_1 a_0].\)

Observe that if \(a_{n-i}+ka_n\ge 10,\) digits to the left of \(a_{n-i}+ka_n\) in the above lines may change due to "carries."

Developing your own leap-from-the-left style Pascal test for a divisor \(d\):  Let \(i\) denote the size of the "leap" that you wish to use.  Let \(k\) be any integer congruent to \(10^i\,\,({\rm{mod}}\,\,d).\)  To test an integer \(N\) for divisibility by \(d,\) let \(N^\prime\) be the number formed by truncating the first digit from \(N,\) multiplying that digit by \(k,\) and adding this product to the \(i\)th digit of the truncated number.  Then \(N\) is divisible by \(d\) if and only if \(N^\prime\) is divisible by \(d\).

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.

Nearly all of the divisibility tests that appear in the literature fall under either the Pascal or Zbikowski umbrellas.  This section is devoted to those several that do not.  The first of these that we will discuss was published in 1897 by Alice in Wonderland author Charles Dodgson (1832-1898) [12].  (While all of his fiction was published under the pseudonym Lewis Carroll, Dodgson used his given name for the publication of his mathematical works.)

4.1.  Charles Dodgson's Divisibility Tests for \(9\) and \(11\)

In [12], Dodgson remarked that

if you put a "0" over the unit-digit of a given number, which happens to be a multiple of 9, and subtract all along, always putting the remainder over the next digit, the final subtraction gives remainder "0," and the upper line, omitting its final "0," is the "9-quotient" of the given number (i.e. the quotient produced by dividing it by 9).  Having discovered this, I was at once led, by analogy, to the discovery that, if you put a "0" under the unit-digit of a given number, which happens to be a multiple of 11, and proceed in the same way, you get an analogous result.

He later quipped that

...quite lately, it occurred to me to try what would happen if, after discovering the remainder, I were to put it, instead of a "0," over or under the unit-digit, and then subtract as before.  And I was charmed to find that the old result followed: the final subtraction yielded remainder "0," and the new line, omitting its unit-digit, was the required quotient.

Dodgson offered no proof of these assertions.  Nonetheless, his observations are easier to justify than they are to decipher:  Using the division algorithm, let \(N,\) \(q,\) and \(r\) be nonnegative integers with \(0\le r<9\) such that \(N=9q+r\).  Then \(N=10q-q+r,\) which implies that

\[q=(10q+r)-N.\]

So by putting the remainder \(r\) over the unit digit of \(N\) and subtracting "all along, always putting the remainder (i.e., the difference) over the next digit," the number that materializes in the upper line will be \(10q+r\) and the difference between this number and \(N\) will be \(q.\)  We clarify this fact with the following example:

Example 4.1.  Observe that when \(9\) is divided into \(284558\) we obtain a remainder of \(5.\)  (This is most easily seen by adding the digits of \(284558 \,\,({\rm{mod}}\,\, 9)\).)  Placing the \(5\) above the unit digit of \(284558\) looks like

\[\begin{array}{rr} {} & 5\\ - & 284558\\\hline\end{array}\]

Using the standard subtraction algorithm, we borrow \(1\) from the mystery digit to the left of \(5\) and subtract, placing the difference (what Dodgson called the "remainder") "over the next digit":

\[\begin{array}{rr} {} & 75\\ - & 284558\\\hline {} & 7\end{array}\]

Recognizing that we had borrowed \(1\) from the \(7,\) we repeat the process by subtracting \(5\) from \(6\) and placing the difference "over the next digit":

\[\begin{array}{rr} {} & 175\\ - & 284558\\\hline {} & 17\end{array}\]

Continuing yields:

\[\begin{array}{rr} {} & 316175\\ - & 284558\\\hline {} & 31617\end{array}\]

A quick check will verify that \(31617\) is in fact the quotient obtained upon dividing \(9\) into \(284558.\)

This algorithm can always be used to determine whether a given integer is divisible by \(9\):  Simply begin by placing a "0" over the unit digit and proceed as above.  The given integer is divisible by \(9\) if and only if the resulting expression is a true statement.  As Dodgson later remarked, it is easier to determine divisibility by adding the digits of the number (mod \(9\)); however, if the number is divisible by \(9,\) Dodgson's method has the benefit of revealing the quotient.

Divisibility by \(11\) is explained similarly:  If \(N=11q+r,\) then \(N=10q+q+r\).  Therefore,

\[q=N-(10q+r).\]

Example 4.2.  A Pascal test for divisibility by \(11\) shows that dividing \(284558\) by \(11\) gives a remainder of \(10.\)  Dodgson instructed us to place the \(10\) under the units digit.  Instead, we'll place a \(0\) under the \(8\) (increasing our eventual difference by \(10\)) and compensate by decreasing the \(5\) (in the tens place) to a \(4:\)

\[\begin{array}{rr} {} & 284548\\ - & 0\\\hline\end{array}\]

Continuing as before, and placing differences below the next digit eventually yields:

\[\begin{array}{rr} {} & 284548\\ - & 258680\\\hline {} & 25868\end{array}\]

As anticipated, \(25868\) is the quotient obtained upon dividing \(11\) into \(284548.\)

4.2.  Divisibility tests via synthetic division

A routine calculation confirms that dividing \(x-3\) into \(4x^4+x^3+6x^2+3x+1\) yields \(4x^3+13x^2+45x+138\) with a remainder of \(415.\)  If we consider the case whenever \(x=10,\) this says that dividing \(7\) into \(41631\) yields \(4000+1300+450+138=5888\) with a remainder of \(415.\)  In other words, \(41631\equiv 415\,\,({\rm{mod}}\,\,{7})\).  Using synthetic division, the calculation looks like:

\[\begin{array}{c|rrrrr} 3 & 4 & 1 & 6 & 3 & 1\\ {} & {} & 12 & 39 & 135 & 414\\ \hline {} & 4 & 13 & 45 & 138 & 415\end{array}\]

Notice we can express \(13=3(4)+1,\) \(45=3(3(4)+1)+6,\) and so forth, until

\[415=3(3(3(3(4)+1)+6)+3)+1.\]

Using Theorem 1.1 we may proceed as Pruitt did in [39] by replacing some of the intermediate calculations above with smaller \(({\rm{mod}}\,\,{7})\) equivalents:

\[\begin{array}{c|rrrrr} 3 & 4 & 1 & 6 & 3 & 1\\ {} & {} & 5 & -3 & 2 & 1\\ \hline {} & 4 & -1 & 3 & 5 & 2\end{array}\]

Sure enough, \(2\) is the remainder obtained when \(7\) is divided into \(41631.\)

Actually, the expression of nested calculations above looks uncannily familiar.  The innermost calculation indicates that the first digit of \(41631\) is being multiplied by \(3\) and then added to the second digit.  This result is multiplied by \(3\) and added to the third digit, etc.  Intermediate results can be replaced with \(({\rm{mod}}\,\,{7})\) equivalents as desired.  This is exactly the flow-from-the-left style Pascal test described earlier!  It turns out that this adventure in the rabbit hole isn't so different after all.

Conclusion

Tests for divisibility have a rich history, and while modern technology has diminished their apparent practicality, their ongoing popularity is evidenced by their continued appearance in the literature.  There's a captivating mystique to answering questions about numbers by playing games with their digits.  Educators have an opportunity to capitalize on this allure by using divisibility tests as an entertaining "hook" to encourage students to learn about place value, congruence, various base systems, etc.  After all, who doesn't want to understand how a favorite magic trick works?  From this vantage point, divisibility tests have a continued practical use as a captivating pedagogical tool for teaching serious mathematics.  We hope your students will enjoy learning the lessons that these tests have to offer, and that their enhanced understanding will lead them to experience the delight of mathematical creation.

Acknowledgments

The author expresses his gratitude to Mr. William (Matt) Leonard, Dr. Greg Richardson, Dr. Janet Beery and the referees for valuable comments which helped to improve this article.

About the Author

Eric McDowell is a professor of Mathematics at Berry College near Rome, Georgia.  He has published a number of articles in his research area of continuum theory, but his more recent papers have been pedagogical.  Eric enjoys singing, and acting in community theatre, and writes songs about mathematical topics that he produces with his students.  ("The Derivative Rag" and other videos can be found on YouTube.)  He lives in Rome with his wife, Jackie.

[1] Abodah Zarah. Babylonian Talmud, folio 9b. Soncino Press, 1961.

[2] G. B. Attwood and D. Yih. Divisibility rules. Mathematics in School, 11(2):25, 1982.

[3] Aaron Bakst. Mathematical recreations. The Mathematics Teacher, 46(1):55-57, 1953.

[4] Lewis Berenson. A divisibility test for amateur discoverers. The Arithmetic Teacher, 17(1):39-41, 1970.

[5] Edward Brooks. The Philosophy of Arithmetic. Normal Publishing Company, 1880.

[6] Yonah Cherniavsky and Artour Mouftakhov. Zbikowski's divisibility criterion. The College Mathematics Journal, 45(1):17-21, 2014.

[7] Paul Cohn. Note 1644: Tests for divisibility. The Mathematical Gazette, 27(273):28-29, 1943.

[8] Louis J. Cote. More on divisibility tests. The Mathematics Teacher, 102(9):650, 2009.

[9] S. S. Dalal. Note 2983. A divisibility test. The Mathematical Gazette, 46(355):31-32, 1962.

[10] Leonard Eugene Dickson. History of the Theory of Numbers. Chelsea Publishing Company, 1952. (Originally published in 1919 by the Carnegie Institution, Washington, D.C., all three volumes of this text are now available in paperback from Dover Publications, Mineola, NY, 2005.)

[11] Clayton W. Dodge. Divisibility tests - making order out of chaos. Pi Mu Epsilon Journal, 10(10):779-790, 1999.

[12] Charles L. Dodgson. Brief method of dividing a given number by 9 or 11. Nature, 56(1459):565-566, 1897.

[13] William Donnell. Discovering divisibility tests. Mathematics in School, 37(3):14-15, 2008.

[14] John Edge and Edwin Norris. Test for divisibility by 7. Mathematics in School, 10(5):24-25, 1981.

[15] Francis Elefanti. Problem on the divisibility of numbers. Proceedings of the Royal Society of London, 10:208-214, 1859.

[16] Richard English. Tests for divisibility in all number bases. Mathematics in School, 14(2):6-7, 1985.

[17] Sandy Ganzell. Divisibility tests, old and new. The College Mathematics Journal, 48(1):36-40, 2017.

[18] E. Paul Goldenberg. How does one know if a number is divisible by 17? The Mathematics Teacher, 99(7):502-505, 2006.

[19] J. B. S. Haldane. Note 1986: Tests for divisibility. The Mathematical Gazette, 31(296):239, 1947.

[20] Wm. E. Heal. Some divisibility tests. The American Mathematical Monthly, 4(6/7):171-172, 1897.

[21] Harry Hutchins. License numbers and divisibility rules. The Two-Year College Mathematics Journal, 14(2):122-125, 1983.

[22] John Q. Jordan. Divisibility tests of the noncongruence type. The Mathematics Teacher, 58(8):709-712, 1965.

[23] J. Kashangaki. Note 80.3: A test for divisibility by seven. The Mathematical Gazette, 80(487):226, 1996.

[24] Robert E. Kennedy. Divisibility by integers ending in 1, 3, 7, or 9. The Mathematics Teacher, 64(2):137-138, 1971.

[25] Alma Jean Kilgour. Divisibility by odd numbers. The Arithmetic Teacher, 7(3):150-151, 1960.

[26] Robb T. Koether. A general test for divisibility. Pi Mu Epsilon Journal, 5(8):420-424, 1973.

[27] Joseph-Louis Lagrange. Leçons élémentaires sur les math. données á l'école normale en 1795. Journal de l'école polytechnique, 7,8:194-199, 1812.

[28] Calvin T. Long. A simpler "7" divisibility rule. The Mathematics Teacher, 64(5):473-475, 1971.

[29] Kenneth J. McCaffrey. Digital sum divisibility tests. The Mathematics Teacher, 69(8):670-674, 1976.

[30] M. E. Mortimer and F. H. C. Oates. Divisibility revisited. Mathematics in School, 14(2):8-9, 1985.

[31] R. L. Morton. Divisibility by 7, 11, 13, and greater primes. The Mathematics Teacher, 61(4):370-373, 1968.

[32] Fletcher R. Norris. 1001 properties. The Mathematics Teacher, 69(7):577-578, 1976.

[33] Charlene Oliver. Gus's magic numbers: A key to the divisibility test for primes. The Arithmetic Teacher, 19(3):183-189, 1972.

[34] Allen Olsen. Divisibility tests. The Mathematics Teacher, 100(1):46-52, 2006.

[35] S. Parameswaran. Note 1920: Tests for divisibility. The Mathematical Gazette, 30(290):164-165, 1946.

[36] A. R. Pargeter. Divisibility tests. Mathematics in School, 2(4):40, 1973.

[37] Blaise Pascal. Oeuvres complètes. Gallimard, 1954.

[38] Phil Plummer. Divisibility tests for primes greater than 5. Pi Mu Epsilon Journal, 10(2):96-98, 1995.

[39] Robert Pruitt. A general divisibility test. The Mathematics Teacher, 59(1):31-33, 1966.

[40] Don Redmond. Divisibility tests. The Mathematics Teacher, 102(2):87-89, 2008.

[41] Marc Renault. Stupid divisibility tricks: 101 ways to stupefy your friends. Math Horizons, 14(2):18-21, 42, November 2006.

[42] Kenneth A. Seymour. A general test for divisibility. The Mathematics Teacher, 56(3):151-154, 1963.

[43] Richard Singer. Modular arithmetic and divisibility criteria. The Mathematics Teacher, 63(8):653-656, 1970.

[44] Lehi T. Smith. A general test of divisibility. The Mathematics Teacher, 71(8):668-669, 1978.

[45] Walter Szetela. A general divisibility test for whole numbers. The Mathematics Teacher, 73(3):223-225, 1980.

[46] R. A. Watson. Note 87.54: Tests for divisibility. The Mathematical Gazette, 87(510):493-494, 2003.

[47] Jonathan Weitsman. A general test for divisibility by primes. The Mathematical Gazette, 64(430):255-262, 1980.

[48] Joseph Whittaker. A new divisibility algorithm. The College Mathematics Journal, 16(4):268-276, 1985.

[49] Wendell M. Williams. A complete set of elementary rules for testing for divisibility. The Mathematics Teacher, 56(6):437-442, 1963.

[50] Najib Yazbak. Some unusual tests of divisibility. The Mathematics Teacher, 69(8):667-668, 1976.

[51] A. Zbikowski. Note sur la divisibilité des nombres. Bull. Acad. Sci. St. Pétersbourg, 3:151-153, 1861.