Extended Songer Theorem

In a previous article, I gave a method for proving that an integer minus its reversal is always divisible by nine. However, this is a specific case of a more general idea. One can subtract any permutation of the digits of a number from the original and the result is still divisible by nine.

To make the statement a bit more concrete, let's look at a few examples. If we start with the number 7122, the "Songer Theorem" says that 7122 - 2217 is divisible by 9. What is even more interesting, however, is that the same is true no matter how we permute the digits of 7122. For instance, 7122 - 1227 (no longer just a reversal) equals 5895, and 5895 / 9 = 655. Similarly, 7122 - 2721 = 4401, and 4401 / 9 = 489. This holds for every permutation.

While we could prove this fact using a similar argument to the original "Songer Theorem", there is a simpler way that gives us an additional useful tool. Let aa be an integer we wish to divide by 9. We will claim that aa divided by 9 has the same remainder as the sum of the digits of aa divided by 9. For instance, 9 divides 18, and 9 also divides 1 + 8. 29 mod 9 is 2, and (2 + 9) mod 9 is also 2. If we assume this claim is true, we see that every permutation of the digits of any integer has the same remainder when divided by 9. Thus, when we subtract permutations from each other, their remainders cancel and the resultant value is divisible by 9. Now, all we must do to complete the proof is show that our claim is true.

Let aa be an integer with digits a1a2aka_1 a_2 \cdots a_k. We can write aa as a polynomial

a110k1+a210k2++ak100.a_1 10^{k-1} + a_2 10^{k-2} + \cdots + a_k 10^0.

For each term in the polynomial, we see that

ai10j=ai((10j1)+1)=ai(10j1)+ai.a_i 10^j = a_i ((10^j - 1) + 1) = a_i (10^j - 1) + a_i.

We can rewrite our polynomial as follows:

a1(10k11)++ak(1001)+a1++ak.a_1 (10^{k-1} - 1) + \cdots + a_k (10^0 - 1) + a_1 + \cdots + a_k.

Notice that for any nonnegative integer value of jj, 10j110^j - 1 is divisible by 9. Therefore, the terms on the left side of our rewritten polynomial are divisible by 9, and the result of aa mod 9 is clearly determined by the sum of the terms a1a_1 to aka_k on the right side.

As with the Songer Theorem, this argument can be extended to any base bb when dividing by b1b - 1.

(This article was inspired by my friend Mohammadreza who saw the original Songer Theorem article and pointed out the extension. Thanks!)