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ⁿa_n + 10^n-1a_n-1 + ... + 10¹a₁ + a₀

a_n ≠ 0. We readily have several examples. But let's first define

s₊(A) = a_n + a_n-1 + ... + a₀,
s_±(A) = a₀ - a₁ + ... +(-1)ⁿ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_±(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·[B]_d = [A·B]_d

and the fact that 10 = 1 (mod 9) and 10 = -1 (mod 11), from which we successively get 10² = 1 (mod 9) and 10² = 1 (mod 11), 10³ = 1 (mod 9) and 10³ = -1 (mod 11), and so on.

Note that both s₊(A) and s_±(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, ..., a₀) is called a divisibility criterion by an integer d provided, starting with some A, |f(A)| < 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 ₊ ∈ O(9) and s ₊ ∈ O(3). (Incidently, O(9) ⊂ O(3). Why?)
• s_± ∈ O(11)
• f₁(A) = a₀ ∈ O(2) ∩ O(5)
• f₂(A) = 10a₁ + a₀ ∈ O(4) ∩ O(25)
• f₃(A) = 10²a₂ + 10a₁ + a₀ ∈ O(8) ∩ O(125)
• f₄(A) = 2a₁ + a₀ ∈ O(4)

We have more. Indeed, since 100 = 1 (mod 11),

• f₅(A) = (a₁a₀)₁₀ + (a₃a₂)₁₀ + (a₅a₄)₁₀ + ... ∈ O(11)

• f₆(A) = (a₁a₀)₁₀ - (a₃a₂)₁₀ + (a₅a₄)₁₀ - ... ∈ O(101)

In the same spirit,

• f₇(A) = (a₂a₁a₀)₁₀ - (a₅a₄a₃)₁₀ + (a₈a₇a₆)₁₀ - ... ∈ O(1001)

Interestingly, since 1001 = 7·11·13, f₇ ∈ O(7) ∩ O(11) ∩ 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₈(A) = 2·(... 2·(2·(a_na_n-1)₁₀ + (a_n-2a_n-3)₁₀) + (a_n-4a_n-5)₁₀) + ... ∈ O(7),

which holds for odd n. For even n, modification is obvious. This also follows from the fact that 10² = 2 (mod 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₁ = 10^n-1a_n + 10^n-2a_n-1 + ... + a₁,

so that A = 10A₁ + a₀. We have

• Ac = (ca₀ + A₁) + (10c - 1)A₁

from which it follows that

• f(A) = ca₀ + A₁ ∈ 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₀, add 2a₀ to the remaining number A₁. 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.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
  • Divisibility by 7, 11, and 13
• Examples
• Equivalence relations
• A real life story

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

Copyright © 1996-2012 Alexander Bogomolny