Prove that for any integer n, if n' is obtained by permuting the digits of n, then 9|n − n '.

Question

I'm having some trouble starting this problem. I know that any integer is divisible by 9 iff the sum of it's digits is divisible by 9. Can I say that if a number is permuted and then subtracted from itself, then the sum of its digits is 0 and 9|0, so 9|n-n'?

Answer 1

It is not true that if you permute a number and subtract it from itself, the sum of digits is zero. This is because, when you take two numbers and add/subtract one to/from the other, the digits sums don't get added/subtracted. You can take simple examples such as $99 + 1 = 100$, or $100 - 1 = 99$, to convince yourself of this.

As to the question itself, we have an observation that goes a little more into the divisibility rule than the usual.

The usual divisibility rule goes like you have stated : a number is divisible by nine if and only if the sum of its digits is divisible by $9$.

The stronger rule : the remainder left by a number upon division by $9$, is the same as the remainder left by the sum of its digits, upon division by $9$.

More precisely, every number, minus the sum of its digits, is a multiple of $9$.

This stronger rule, is the helpful one for us.

For any number $n$, let $S(n)$ be the sum of the digits of $n$. the strong divisibility rule states that $n - S(n)$ is divisible by $9$.

So, if $n'$ is any permutation of $n$, then $S(n) = S(n')$,therefore $n - n' = (n -S(n)) + (S(n) - n') = (n- S(n)) + (S(n') - n')$ is a sum of multiples of $9$, and hence a multiple of $9$.

Hence, the statement follows.

Answer 2

Let $n=a_k a_{k-1} \cdots a_1$ and $\pi$ be the permutation of $ [k]$ which gives $n'$ \begin{eqnarray*} n&=& \sum_{i=1}^{k} a_i 10^{i-1} \\ n'&=& \sum_{i=1}^{k} a_i 10^{\pi(i)-1} \\ n-n'&=& \sum_{i=1}^{k} a_i (10^{i-1}-10^{\pi(i)-1}) \\ \end{eqnarray*} Now note that $9 \mid (10^{i-1}-10^{\pi(i)-1})$.