# congruent mod 9

• Jan 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.
• Jan 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.

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

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

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

If the digits of the number are,
$\displaystyle A_1A_2...A_n$
Then define a polynomial,
$\displaystyle P(x)=x^{n-1}A_1+...+xA_{n-1}+A_n$
Thus,
$\displaystyle P(10)=N$
And,
$\displaystyle P(1)$ is sum of digits.
Thus,
$\displaystyle N\equiv \mbox{ SUM }(\mbox{ mod }n)$
• Jan 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: $\displaystyle a_na_{n-1}a_{n-2}\hdots a_1a_o$

Its value is: .$\displaystyle 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: .$\displaystyle S \:=\:a_n + a_{n-1} + a_{n-2} + \hdots + a_1 + a_0$

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

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

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