question

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

Thank you very much.

Printable View

- Jan 11th 2007, 10:36 AMJenny20congruent 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 AMThePerfectHacker
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 PMSoroban
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$