50
$\begingroup$

For example:

  • $12$ reversed is $21$ and $12$ + $9$ = $21$.

  • $17$ with the two values swapped is $71$, and $17$ + $9$ + $9$ + $9$ + $9$ + $9$ + $9$ = $71$.

  • Take the number $123$ and add $9$ a total of $22$ times you get $321$, which is the reverse.

It seems to work for every number. Why is this the case? Is it just a addition thing?

$\endgroup$
  • 25
    $\begingroup$ Because $10a+b-(a+10b)$ is a multiple of $9$ (Exercise: generalize to more than $2$ digits). $\endgroup$ – lulu May 18 '18 at 0:13
  • 12
    $\begingroup$ Next exercise: generalize to other bases (try base 8) $\endgroup$ – Ashwin Iyengar May 18 '18 at 0:18
  • 9
    $\begingroup$ Next exercise “this works for every number” - provide proof of this statement $\endgroup$ – Prince M May 18 '18 at 1:26
  • 3
    $\begingroup$ It is not just reversal: you can put the digits in any order. So while $321=123+22\times 9$, you also have $312=123+21\times 9$, $231=123+12\times 9$, $213=123+10\times 9$, $132=123+1\times 9$. $\endgroup$ – Henry May 18 '18 at 7:03
  • 5
    $\begingroup$ @AshwinIyengar - Shades of Tom Lehrer's New Math. :-) $\endgroup$ – T.J. Crowder May 18 '18 at 7:40
87
$\begingroup$

Any number is congruent modulo $9$ to the sum of its digits: $$a_na_{n-1}\ldots a_1a_0\equiv a_n+a_{n-1}+\ldots +a_1+a_0\pmod 9$$ If you reverse the digits, the sum is unchanged. Therefore $$a_0a_1\ldots a_{n-1}a_n\equiv a_na_{n-1}\ldots a_1a_0\pmod 9$$ which is equivalent to your statement.


Note a stronger statement implied by the same reasoning:

By adding or subtracting a suitable amount of $9$'s, you can reach any permutation of the digits.

$\endgroup$
20
$\begingroup$

This isn't a formal proof or anything, but it's the way that makes the most sense to me. Adding 9 to something is the same as adding 10 then subtracting 1, which means that you're bumping one place up and the other down. Therefore, the sum of the digits in a number doesn't change when you add or subtract 9 to it, and by repeatedly adding (or subtracting) 9 to a number you can cycle through all the different numbers whose digit sum equals your original number. As the reverse of a number still has the same digit sum as your original number, you can get to it through adding or subtracting 9's. Hope this makes sense!

$\endgroup$
  • 4
    $\begingroup$ This works well except when the number is a multiple of 10. Then the sum of the digits changes. However, in terms of simplicity, this is a good way to understand the process and can lead to an intuitive conclusion. $\endgroup$ – CJ Dennis May 18 '18 at 6:31
  • $\begingroup$ @CJ Dennis You are right, but then if we take the digit sum again, all the way down to a single digit number, that number shouldn't change. So 10 becomes 1, and 19 becomes 10, which becomes 1 as well. $\endgroup$ – ThatEvilChickenNextDoor May 18 '18 at 11:33
  • 1
    $\begingroup$ This seems nice as an intuitive starting point, but as a mathematical argument it has some problems. When I bump up the tens place and bump down the ones place, usually nothing special happens and it's clear the digit sum stays the same... but sometimes this causes a carry into or out of the tens place, and then the argument that the digit sum stays the same is harder (because it isn't, in fact, true!). And even if you did have a process that kept the digit sum the same, that doesn't mean you can cycle through all the numbers with the same digit sum just by iterating it. $\endgroup$ – Daniel Wagner May 18 '18 at 15:32
6
$\begingroup$

Well, take a number $N=a_na_{n-1}a_{n-2}.....a_2a1$.

This is $N=\sum_{k=0}^n a_i*10^n$. Reverse the digits and you get $M = \sum_{k=0}^n a_i 10^{n-i}$.

Subtract them and you get:

$N-M = \sum_{k=0}^n a_i*(10^i - 10^{n-i})$.

Now I claim that for any $j,k$ that $10^j - 10^k$ is a multiple of $9$. If $k< j$ then $10^j - 10^k = 10^k(10^{j-1} - 1) = 10^k*9999....9$. That's clearly a multiple of $9$. (Actually, if this were a formal proof we'd have to prove that... sigh... but we won't).

So $N - M$ is ... a multiple of $9$.

So.... if you add $9$ enough times, you'll eventually get from $N$ to $M$.

=====

It's actually kind of interesting.

Take $8364$ and $4638$ then $8364 - 4638= 8*1000 + 3*100 + 6*10 + 4 - 6*100 - 4*1000 - 3*100- 6*10 -4 = 8*(1000-1) + 3*(100 - 10) - 6*(100-10) - 4*(1000 -1)$.

Kind of an interesting symmetry, isn't it? (I had never noticed it before.)

Have you ever seen this trick:

Take a three digit number: $abc$, reverse it $cba$, subtract them $abc- cba = def$. Reverse it $fed$ and add them. $def + fed = 1089$. Always.

$\endgroup$
  • $\begingroup$ Your closing “trick” fails if a = c, since the three digit number is then a palindrome that is necessarily equal to its reverse causing the difference to be zero. $\endgroup$ – eggyal May 18 '18 at 7:04
  • $\begingroup$ The indices are a bit off in the beginning (eg $N=\sum_{k=0}^n a_i*10^n$ should be $N=\sum_{k=0}^n a_k*10^k$) $\endgroup$ – Arnaud Mortier May 18 '18 at 10:45
  • 1
    $\begingroup$ I think you want to use \cdot ($\cdot$) or \times ($\times$) instead of * for multiplication. $\endgroup$ – Ruslan May 18 '18 at 10:50
  • $\begingroup$ I don't reckon fleablood is going to change the $\ast$ \ast habit... but what's really unreadable are those inline chain equations. $\endgroup$ – leftaroundabout May 18 '18 at 14:19
5
$\begingroup$

Good observation! To flesh out the proof a little bit, let’s write out your number in base $b$, from right to left (like when you add, subtract or multiply). Call the smallest digit $a_0$, the next-smallest $a_1$ and so on, and since they’re digits, $0 \leq a_i < b$. Then any number has the form $a_0 b^0 + a_1 b^1 + a_2 b^2 + ...$ For example, the number 117 in base 10 is $7 \cdot 10^0 + 1 \cdot 10^1 + 1 \cdot 10^2 + 0 \cdot 10^3$, and we can write out as many more zero digits as we want.

Now let’s pick a $c$ so $b \equiv 1 \;(\operatorname{mod} c)$. (When $b = 10$, one value of $c$ that works is $9$. What’s the other?) Apply that equivalence to the general form we just found for any number in terms of its digits:

$$a_0 b^0 + a_1 b^1 + a_2 b^2 + ... \equiv a_0 1^0 + a_1 1^1 + a_2 1^2 + ... \equiv a_0 + a_1 + a_2 + ... \;(\operatorname{mod} c)$$

A special case of this is, that when $b = 10$ and $c = 9$, you can rearrange the digits any way you want and they will still have the same sum, which means the same remainder divided by 9, so the difference between them will be a multiple of 9.

This theorem has a number of mildly-practical applications. One is the method of “casting out nines,” which people have used to check their arithmetic for centuries. A corollary of that is that any number will be congruent, modulo 9, to the sum of its digits. So let’s say we want to check the answer $123 + 456 = 589$. $123 \equiv 1 + 2 + 3 \equiv 6 \;(\operatorname{mod} 9)$ and $456 \equiv 4 + 5 + 6 \equiv 9 + 6 \equiv 6 \;(\operatorname{mod} 9)$. So, we know $123 + 456 \equiv 6 + 6 \equiv 3 \;(\operatorname{mod} 9)$. But, $589 \equiv 5 + 8 + 9 \equiv 4 \;(\operatorname{mod} 9)$, and therefore, our answer was wrong. In fact, our intuition tells us that the sum of our digits was off by one, so probably one of our digits was also off by one. There are similar tricks we can use with the numbers 6, 7, and 11 in our heads. (Hint: what happens when $b \equiv -1 \;(\operatorname{mod} c)$ or $b \equiv b^2 \;(\operatorname{mod} c)$?)

Cheap microchips have made that particular trick less useful, and I don’t think it’s even taught any more. But it’s also created real-world applications for the technique in computer science. For example, we might want to interpret an object as some arbitrary sequence of 32-bit unsigned words, representing the digits of a number in base $2^{32}$, then take mod 65,537 in order to calculate a hash value for it. Or we might do bignum arithmetic, or find a remainder on a CPU with no mod instruction.

$\endgroup$
4
$\begingroup$

It's a simple consequence of 9 being 1 less than 10, the base of our system of numeration.

Consider $10^n$ for $n \in \mathbb Z^+$. The reversal of $10^n$ is 1, and $10^n - 1$ is all 9s.

Next consider the table of multiplication for 9: $1 \times 9 = 9$, $2 \times 9 = 18$, $3 \times 9 = 27$, etc. Notice how the one's place decreases by 1 each time, until getting to $10 \times 9 = 90$ and $11 \times 9 = 99$, and so the cycle repeats again.

This is not a proof either, but I hope it helps you see this more clearly.

$\endgroup$
  • 1
    $\begingroup$ This is what I was going to say. Each consecutive +9 is the same as saying +10 - 1. $\endgroup$ – Michael Richardson May 18 '18 at 13:00
3
$\begingroup$

Lemma: $\overline{ab}-\overline{ba}\equiv 0 \pmod 9$. Proof: $(10a+b)-(10b+a)=9(a-b)\equiv 0 \pmod 9$.

Based on the Lemma, $\overline{abc}-\overline{cba}\equiv 0\pmod 9$, because: $$\overline{abc}-\overline{acb}\equiv \overline{acb}-\overline{cab}\equiv \overline{cab}-\overline{cba}\equiv 0 \pmod 9 \iff \\ (\overline{abc}-\overline{acb})+(\overline{acb}-\overline{cab})+(\overline{cab}-\overline{cba})\equiv 0 \pmod 9 \iff \\ \overline{abc}-\overline{cba}\equiv 0\pmod 9.$$ Note: It is $T(2)=3:\overline{abc}\Rightarrow \color{red}{\overline{acb}\Rightarrow \overline{cab}\Rightarrow \overline{cba}}$.

In general, $\overline{a_1a_2...a_n}-\overline{a_na_{n-1}...a_1}\equiv 0 \pmod 9$ and: $$\overline{a_1a_2...a_n}\overbrace{\Rightarrow}^{T(n-1)} \overline{a_na_{n-1}...a_1}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.