How can we find fast if a number is divisible by 9?

We just add its digits and test if the result is divisible by 9.

Examples:

Is 126 divisible by 9?
1 + 2 + 6 = 9
9 is divisible by 9, so 126 is also (126 = 9 * 14).

Is 576 divisible by 9?
5 + 7 + 6 = 18
18 is divisible by 9, so 576 is also (576 = 9 * 64).

Is 878 divisible by 9?
8 + 7 + 8 = 23
23 is not divisible by 9, so 878 is neither (878 = 9 * 97 + 5).

How does it work?

Let's say we have a 4 digits number:
= 1000 * a + 100 * b + 10 * c + d =
= 999 * a + a + 99 * b + b + 9 * c + c + d =
= 9 * (111 * a + 11 * b + c) + (a + b + c + d)

So is divisible by 9 if and only if (a + b + c + d) is divisible by 9