Divisibility Tests: A History and User's Guide - Pascal Divisibility Tests

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:\)

He then used Theorem 1.1 to conclude that

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:

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

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

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

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

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

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

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\).