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