Skip to content
April 1, 2011 / oop123

Why Permutations of a Number are Congruent Modulo 9

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

Advertisements

One Comment

Leave a Comment
  1. kwizatz / Sep 7 2011 3:59 pm

    I just came across the same Euler post and wondered why this was so — thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: