congruent mod 9

**Jenny20** · January 11th 2007, 10:36 AM

question

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

Thank you very much.

**ThePerfectHacker** · January 11th 2007, 11:22 AM

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)$

**Soroban** · January 11th 2007, 07:07 PM

Hello, Jenny!

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

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$

Thread: congruent mod 9

LinkBack

Thread Tools

Display

congruent mod 9

Similar Math Help Forum Discussions

Is S_3 congruent to D_3?

x^6 congruent to 1 (mod 19)

Congruent Triangles

Congruent Triangles

Congruent Angles

Search Tags