Divisibility Tests: A History and User's Guide

Author(s):

Eric L. McDowell (Berry College)

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