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 be an integer we wish to divide by 9. We will claim that divided by 9 has the same remainder as the sum of the digits of 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 be an integer with digits . We can write as a polynomial
For each term in the polynomial, we see that
We can rewrite our polynomial as follows:
Notice that for any nonnegative integer value of , is divisible by 9. Therefore, the terms on the left side of our rewritten polynomial are divisible by 9, and the result of mod 9 is clearly determined by the sum of the terms to on the right side.
As with the Songer Theorem, this argument can be extended to any base when dividing by .
(This article was inspired by my friend Mohammadreza who saw the original Songer Theorem article and pointed out the extension. Thanks!)