Songer Theorem

A friend of mine (whose last name is Songer) recently mentioned an unusual observation at a dinner party---if one subtracts a number from its reversal, the result is always divisible by nine. In a textbook example of nerd sniping, a couple of other friends and I whipped out calculators to convince ourselves and spent a few minutes trying to find a proof (as one does at dinner parties). Not all of the guests that night were fond of math, so we set the problem aside when the proof wasn't immediately forthcoming. However, an unresolved sense of mathematical angst propelled me toward a proof the next day, and it has an interesting consequence.

Now, we define the reversal of a number as the reversal of its digits. For instance, the reversal of 1234 would be 4321. If we define a reversal function rev:ZZ\text{rev}: \mathbb{Z} \longrightarrow \mathbb{Z} that performs this reversal, our theorem is formally stated as follows:

For every integer xx, there is an integer cc such that

xrev(x)=9c.x - \text{rev(\(x\))} = 9c.

There are a few different ways to think about integers. Most helpful to our proof is to think about them as polynomials. For instance, 271 is equivalent to 2×102+7×101+1×1002 \times 10^2 + 7 \times 10^1 + 1 \times 10^0. So, for any integer aa with nn digits a1a2a3ana_1 a_2 a_3 \ldots a_n, there is an equivalent polynomial a1×10n1+a2×10n2++an×100a_1 \times 10^{n-1} + a_2 \times 10^{n-2} + \cdots + a_n \times 10^0.

Let our value of xx in the theorem be an integer with nn digits x1xnx_1 \ldots x_n. Then our theorem can be restated as

(x1×10n1++xn×100)(xn×10n1++x1×100)=9c.\begin{aligned}(&x_1 \times 10^{n-1} + \cdots + x_n \times 10^0) \\ &- (x_n \times 10^{n-1} + \cdots + x_1 \times 10^0) = 9c.\end{aligned}

We can then pair up every xix_i term in xx with its corresponding term in the reversal. For each term, this gives us something like

+(xi×10i1xi×10ni)+.\cdots + (x_i \times 10^{i-1} - x_i \times 10^{n-i}) + \cdots.

This is equivalent to

+xi(10i110ni)+.\cdots + x_i(10^{i-1} - 10^{n-i}) + \cdots.

If i1i-1 is equal to nin-i, then we're right in the middle of both numbers and this term is equal to 0. So, let's assume without loss of generality, that i1i-1 is greater than nin-i. Then we can factor an extra 10ni10^{n-i} out of both of the powers of 10 to get

+xi[10ni(10i1(ni)1)]+.\cdots + x_i[10^{n-i}(10^{i-1-(n-i)} - 1)] + \cdots.

This term now has a factor that is a nonzero power of 10 minus 1 which will always give us an integer divisible by 9 (9, 99, 999, etc.). Since every digit of xx has a corresponding digit in the reversal, every one of these paired terms in the polynomial must be divisible by 9.

What's more, we see that 9 isn't particularly special. It just happens to be the value that's one less than the base we're working in. We could just as easily use any other base as a substitute for 10. So, for a base bb, a number minus its reversal is divisible by b1b-1. This gives us a more abstract formulation:

For every integer xx in base bb, there is an integer cc such that

xrev(x)=(b1)c.x - \text{rev(\(x\))} = (b-1)c.