A bit of trivia

Tests for divisibility by 9 and 11

If one adds the digits of a number and the sum is divisible by 9, then the number is divisible by 9. Similarly, if one alternates the signs of a multi-digit number's digits and the sum is divisible by 11, then the number is divisible by 11.Example
The sum of the digits of 99 is 18, which is divisible by 9. Likewise, the sum 1+8 is also divisible by 9.
The sum of the alternately signed digits of 99 is 9 + (-9) = 0, and 0 is divisible by 9.
And, of course, 99 = 9(11).
How do these tests of divisibility work?
This description is for people with no background in number theory.

Proposition I

A number is divisible by 9 (with a remainder of 0) if and only if the sum of its digits, in base-10 notation, is divisible by 9.
That is, if n is divisible by 9, the sum of its digits is divisible by 9 and if the sum of its digits is divisible by 9, n is divisible by 9.
So our method of proof can either begin with the assumption that n is divisible by 9 or with the assumption that the sum of n's digits is divisble by 9. Below we have chosen to assume n is divisible by 9. But, first some background.

What is base 10?

It is customary to use a place system for numbers of any base. The base-10 system, with its 10 digits, uses digit position to tell us what multiple of 10 we have.
When we write, say 231, this tells us that we are to add 200 + 30 + 1. Each place represents a power of 10. That is, 200 + 30 + 1 = 2 · 10² + 3 · 10¹ + 1 · 10⁰ (where any number with exponent 0 is defined as equal to 1).
If we wish to write 23 in binary, or base-2, notation, we first write:
1 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ + 1 · 2⁰.
Then, limiting ourselves to the digit set {0,1}, we write 10111, knowing that the place signifies a power of 2.

Sets of numbers differing by multiples of q

Now we want to think about some sets of numbers, each of which is divisible by some number n.For example, let's consider the series
{...-17, -10, -3, 4, 11...} where any two members differ by some multiple of 7.
As we see,
(-17) - (-10) = -7
(-17) - 11 = -28
Another such series is
{...-15, -8, -1, 6, 13, 20...}
where subtraction of any two numbers in the series also yields a number divisible by 7.
Once we know one member of such a set, we know them all. That is, the set is writable:
{-3 + 7k|k e K}, with K the set of integers.
It is customary to express such a set thus:
[-3]₇. We can also express this set as [-10]₇. In fact, in this notation,
[-3]₇ = [-10]₇
In general, a series denoted [n]_q is identical to the series denoted [n + qk]_q, where k is any integer.
The set [n]_q is known as congruence class n modulo q.
Note that
[0]_q = [0 + qk]. Every member of this series is divisible by q for all k. That is, every element of this series, when divided by q, equals an integer k.
[q]_q = [q + qk]. Every member of this series is divisible by q. That is, every member, when divided by q, equals k+1.
What happens if we add elements of [m]_q and [n]_q?
We have m + qk + n + qj = m+n + q(k+j), letting j be an integer.
If we set k+j to 0, this gives m+n, which we use to establish the series [m+n]_q = [m+n + qk]_q.
For example, we have [-3]₇ + [-1]₇ = [-4]₇,
which means,
{...-17,-10,-3,4,11...} + {...-15,-8,-1,6,13,20...} = {...-18,-11,-4,3,10,17...}
We see that -18 - 3 = -21, which is indeed divisible by 7.
By kindred reasoning we can show that it is possible to multiply an element from each of two similar series to obtain a third series similar to the other two. By 'similar' is meant a series in which elements differ by an integer multiple of q.

That is, [p]_q · [r]_q = [pr]_q.

Proof of Proposition I

Let d_n, d_n-1 ... d₁, d₀ represent the decimal expansion of some number N.Then, by definition, we have N = d_n · 10ⁿ + d_n-1 · 10^n-1+...+d₀ · 10⁰
[See explanation above.]
Since both sides of the expression are equal, each must belong to the same congruence class.
That is, putting N as a member of the series [N]_q means that the right side of the equation is also a member of [N]_q.
That is, [N]_q = [d_n · 10ⁿ + d_n-1 · 10^n-1 +...+ d₀ · 10⁰]_q.
Now our condition is that N be divisible by 9. In that case N is a member of the congruence class [0]₉. That is, [N]₉ = [0]₉. Likewise, the decimal expansion is also a member of [0]₉.
That is, [N]₉ = [0]₉ = [N's decimal expansion]₉.
Because [p+r]_q = [p]_q+[r]_q and [pr]_q = [p]_q · [r]_q, we may write:
[N]₉ = [0]₉ = [d_n]₉ · [10]₉ⁿ + [d_n-1] · [10]₉^n-1 + ... + [d₁]₉ · [10]₉⁰
Now we know that [10]₉ = [1]₉, since 10-9 = 1.
Hence we can substitute the number 1 for the number 10, obtaining
[0]₉ = [d_n]₉ · [1]₉ⁿ + [d_n-1]₉ · [1]₉^n-1+...+ [d₀]₉ · [1]₉⁰ ...
Obviously 1^m = 1. So we may write
[N]₉ = [d_n]₉ + [d_n-1]₉+...+[d₀]₉
which equals
[d_n+d_n-1+...+d₀]₉, which equals [N]₉, which equals [0]₉.
Since the sum of the digits is equal to congruence class [0]₉, it must be divisible by 9.
QED

Proposition II

A number is divisible by 11 only if the alternating sum of its digits is divisible by 0.That is, d_n - d_n-1 + d_n-2 etc. must equal a sum divisible by 11.
The proof for 9 can be used for 11, noting that [10]₁₁ = [-1]₁₁, since 10 - (-1) = 11. And it should be remembered that (-1)²ⁿ is positive, while (-1)^{2n ± 1}
is negative.
First published ca. 2002