Prove that every positive integer is congruent to the sum of its digits modulo 3.

$\begingroup$

Prove that every positive integer is congruent to the sum of its digits modulo 3.So I start with rewrite as $n = c_r 10^r + c_{r-1} 10^{r-1}...$?

$\endgroup$ 1

2 Answers

$\begingroup$

Yes, start by writing $n = c_r 10^r + c_{r-1} 10^{r-1} + \dots + c_0$ and note that $10^k \equiv 1 \mod 3$ for every $k \geq 0$.

$\endgroup$ 2 $\begingroup$

First note that for any power of $10$ we have

$10^r=99...9+ 1$ (with $r$ digits of $9$) (e.g. $100=99+1, 1000=999+1$)

$=3(33...3)+1$

$=1$ $(mod 3)$

Therefore given any $n$ we have

$n = c_r 10^r + c_{r-1} 10^{r-1}+ ... + c_1 10+c_0=c_r + c_{r-1} + ... + c_1 +c_0$$(mod 3)$

$\endgroup$