# 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 $a$ be an integer we wish to divide by 9. We will claim that $a$ divided by 9 has the same remainder as the sum of the digits of $a$ 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 $a$ be an integer with digits $a_1 a_2 \cdots a_k$. We can write $a$ as a polynomial

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

For each term in the polynomial, we see that

$a_i 10^j = a_i ((10^j - 1) + 1) = a_i (10^j - 1) + a_i.$

We can rewrite our polynomial as follows:

$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 $j$, $10^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 $a$ mod 9 is clearly determined by the sum of the terms $a_1$ to $a_k$ on the right side.

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

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