Divisibility Tests: A History and User's Guide - Down a Different Rabbit Hole

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.