I came across this fact in one of the Project Euler posts. It’s very easy to prove, so I decided to post an informal proof here for the sake of it.

For those that don’t know what congruence is, here is the definition from Wolfram Mathworld:

“If two numbers b and c have the property that their difference is integrally divisible by a number m (i.e. (b – c) / m is an integer), then a and b are said to be ‘congruent modulo m.’ The number is called the modulus, and the statement “b is congruent to c (modulo m)” is written mathematically as $a\equiv b\ (mod\ m)$

For example, 25 is congruent to 43 modulo 9 because 43 – 25 = 18 and 9 can be evenly divided into 18.

A permutation of a number n is essentially any number that contains the same digits of the n but those digits are in a different order. For example, 122975 is a permutation of 215972.

The (informal) proof starts off with a number abcd (the number can be of any length and the proof will still work).

1. let n = abcd. It can be more formally express as 1000 * a + b * 100 + c * 10 + d, where a, b, c, d are each integer within the set {0, 1, 2… 8, 9}

2. 1000 * a + b * 100 + c * 10 + d = (999 * a + a) + (99 * b + b) +  (9 * c + c) + d

3. 1000 * a + b * 100 + c * 10 + d = (999 * a + 99 * b + 9 * c) + a + b + c + d

4. Let m = efgh and efgh be a permutation of abcd (or n) so each digit in m map to a digit in n

5. Using the same reasoning as abcd for m, we get:
(999 * e + 99 * f + 9 * g) + e + f + g + h

6. Let x = m – n (the difference between m and n). If x can be divided evenly by 9, then m is congruent to n modulo 9 (the definition of congruence)

6. x = m – n
= ((999 * e + 99 * f + 9 * g) + e + f + g + h) – ((999 * a + 99 * b + 9 * c) + a + b + c + d)
= ((999 * e + 99 * f + 9 * g) – (999 * a + 99 * b + 9 * c)) + ((e + f + g + h) – (a + b + c + d))

8. Note that a + b + c + d = e + f + g + h (they are permutations), then we can get:
x = (999 * e + 99 * f + 9 * g) – (999 * a + 99 * b + 9 * c)

7. This expression is divisible by 9, ergo m is congruent to $n\equiv m\ (mod\ 9)$

A really sucky and informal proof, but should give you the idea.

CU