# congruent mod 9

• January 11th 2007, 10:36 AM
Jenny20
congruent mod 9
question

Prove that every integer is congruent mod 9 to the sum of its digits.

Thank you very much.
• January 11th 2007, 11:22 AM
ThePerfectHacker
Quote:

Originally Posted by Jenny20
question

Prove that every integer is congruent mod 9 to the sum of its digits.

Thank you very much.

There is a useful theorem.

$a\equiv b (\mbox{ mod } n)$
Then,
$P(a)\equiv P(b) (\mbox{ mod } n)$.

Where $P(x)$ is some polynomial in $\mathbb{Z}[x]$.

Thus, we know that,
$10\equiv 1 (\mbox{ mod }n)$.

If the digits of the number are,
$A_1A_2...A_n$
Then define a polynomial,
$P(x)=x^{n-1}A_1+...+xA_{n-1}+A_n$
Thus,
$P(10)=N$
And,
$P(1)$ is sum of digits.
Thus,
$N\equiv \mbox{ SUM }(\mbox{ mod }n)$
• January 11th 2007, 07:07 PM
Soroban
Hello, Jenny!

Here's a more "primitive" proof . . .

Quote:

Prove that every integer is congruent mod 9 to the sum of its digits.

We have an integer of the form: $a_na_{n-1}a_{n-2}\hdots a_1a_o$

Its value is: . $N \:=\:10^na_n + 10^{n-1}a_{n-1} + 10^{n-2}a_{n-2} + \hdots + 10a_1 + a_o$

The sum of its digits is: . $S \:=\:a_n + a_{n-1} + a_{n-2} + \hdots + a_1 + a_0$

Consider their difference:
. . $N - S \;=\;(10^n-1)a_n + (10^{n-1}-1)a_{n-1} + (10^{n-2}-1)a_{n-2} + \hdots$ $+ (10^2-1)a_2 + (10-1)a_1$

All the coefficients are of the form: $10^k-1 \:=\:999\hdots9$
. . and hence are divisible by 9.

Since $N - S$ is a multiple of 9: . $N \equiv S \pmod 9$