Divisibility Criteria

Divisibility criteria are ways of telling whether one number divides another without actually carrying the division through. Implicit in this concept is the assumption that the criteria in question affords a simpler way than the the outright division to answer the question of divisibility. Divisibility criteria constructed in terms of the digits that compose a given number.

To fix the notation, \(A\) will be the number whose divisibility by another number \(d\) we are going to investigate on this page. In the decimal system,

\( A = 10^{n}a_{n} + 10^{n-1}a_{n-1} + ... + 10^{1}a_{1} + a_{0} \)

\(a_{n} \ne 0\). We readily have several examples. But let's first define

\( s_{+}(A) = a_{n} + a_{n-1} + ... + a_{0}, \\ s_{\pm}(A) = a_{0} - a_{1} + \ldots +(-1)^{n}a_{n}. \)

Using these two functions we formulate the criteria of divisibility by \(3,\) \(9,\) and \(11:\)

Divisibility by \(3\).

\(A\) is divisible by \(3\) iff \(s_{+}(A)\) is divisible by \(3.\)

Divisibility by \(9\).

\(A\) is divisible by \(9\) iff \(s_{+}(A)\) is divisible by \(9.\)

Divisibility by \(11\).

Then \(A\) is divisible by \(11\) iff \(s_{\pm}(A)\) is.

All three critera follow from the two basic properties of the modulo arithmetic

  1. \([A]_{d} + [B]_{d} = [A + B]_{d}\)
  2. \([A]_{d}\cdot [B]_{d} = [A\cdot B]_{d}\)

and the fact that \(10 = 1\space (\mbox{mod}\space 9)\) and \(10 = -1\space (\mbox{mod}\space 11),\) from which we successively get \(10^{2} = 1\space (\mbox{mod}\space 9)\) and \(10^{2} = 1\space (\mbox{mod}\space 11),\) \(10^{3} = 1\space (\mbox{mod}\space 9)\) and \(10^{3} = -1\space (\mbox{mod}\space 11),\) and so on.

Note that both \(s_{+}(A)\) and \(s_{\pm}(A)\) are linear combinations of the digits of \(A.\) This is the kind of functions we shall allow on this page. (One generalization would be to consider other bases.)

We formalize the definition the following way:

Definition

A function \(f(A) = f(a_{n}, \ldots , a_{0})\) is called a divisibility criterion by an integer \(d\) provided, starting with some \(A,\) \(|f(A)| \lt A\) and \(A\) is divisible by d iff \(f(A)\) is divisible by \(d.\)

\(O(d)\) is defined as the set of all divisibility criteria by \(d.\)

    Here are a few examples:

  • \(s_{+} \in O(9)\) and \(s_{+} \in O(3).\) (Incidently, \(O(9) \subset O(3).\) Why?)
  • \(s_{\pm} \in O(11)\)
  • \(f_{1}(A) = a_{0} \in O(2) \cap O(5)\)
  • \(f_{2}(A) = 10a_{1} + a_{0} \in O(4) \cap O(25)\)
  • \(f_{3}(A) = 10^{2}a_{2} + 10a_{1} + a_{0} \in O(8) \cap O(125)\)
  • \(f_{4}(A) = 2a_{1} + a_{0} \in O(4)\)

We have more. Indeed, since \(100 = 1\space (\mbox{mod}\space 11),\)

  • \(f_{5}(A) = (a_{1}a_{0})_{10} + (a_{3}a_{2})_{10} + (a_{5}a_{4})_{10} + ... \in O(11)\)

(\(f_{5}\) is obtained by splitting \(A\) right-to-left into \(2\)-digit numbers.) Similarly,

  • \(f_{6}(A) = (a_{1}a_{0})_{10} - (a_{3}a_{2})_{10} + (a_{5}a_{4})_{10} - ... \in O(101)\)

In the same spirit,

  • \(f_{7}(A) = (a_{2}a_{1}a_{0})_{10} - (a_{5}a_{4}a_{3})_{10} + (a_{8}a_{7}a_{6})_{10} - ... \in O(1001)\)

Interestingly, since \(1001 = 7\cdot 11\cdot 13,\) \(f_{7} \in O(7) \cap O(11) \cap O(13).\) The fact may appear uninspiring for it does not relieve one from drudging through the division by \(7\) or \(11\) or \(13.\) However, in some cases this rule is of great help indeed:

  1. \(2,003,008\) is divisible by \(7\) for so is \((008) - (003) + 2 = 7.\)
  2. \(524784\) is divisible by \(13\) for so is \(784 - 524 = 260.\)

Would you rather go on with the long division?

Stuart Anderson developed a general framework for deriving divisibility criteria. In particular, he noticed that

  • \(f_{8}(A) = 2\cdot (... 2\cdot (2\cdot (a_{n}a_{n-1})_{10} + (a_{n-2}a_{n-3})_{10}) + (a_{n-4}a_{n-5})_{10}) + ... \in O(7),\)

which holds for odd \(n.\) For even \(n,\) modification is obvious. This also follows from the fact that \(10^{2} = 2\space (\mbox{mod}\space 7).\)

There is another approach that uses the following generalization of the Euclid's Proposition VII.30:

Let \(a\) and \(d\) be mutually prime (coprime). Then \(d|ab\) is equivalent to \(d|b.\)

Let \(d\) be a divisor of \((10c - 1)\) for some \(c.\) Then clearly \(d\) and \(c\) are coprime. Denote

  • \(A_{1} = 10^{n-1}a_{n} + 10^{n-2}a_{n-1} + ... + a_{1},\)

so that \(A = 10A_{1} + a_{0}.\) We have

  • \(Ac = (ca_{0} + A_{1}) + (10c - 1)A_{1}\)

from which it follows that

  • \(f(A) = ca_{0} + A_{1} \in O(d)\)

This leads to a recursive criterion. For example, let \(d = 19,\) \(c = 2.\) Then \((10c - 1)\) is divisible by \(19.\) Given a number \(A,\) remove \(a_{0},\) add \(2a_{0}\) to the remaining number \(A_{1}.\) Proceed with these steps until you obtain a number which is obviously divisible by \(19\) or is obviously not divisible by \(19.\) Whatever the case, the same will be true of the original number \(A.\) Thus, we get a sequence \(12311,\) \(1233,\) \(129,\) \(30.\) The latter is not divisible by \(19.\) Hence neither is \(12311.\) On the other hand, as the same calculations show, \(20311\) is divisible by \(19.\) (Additional examples are available elsewhere. An ingenious example was found by Gustavo Toja from Brasil.)

References

  1. N. N. Vorob'ev, Criteria for Divisibility, University of Chicago Press, 1980.

|Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

71930216