Help with Understanding Congruence Statement in Divisibility Proof

Question

I am trying to understand the proof of a divisibility rule from this website. I've had very little exposure to modular arithmetic, so in order to attempt to understand the proof I spent the afternoon studying some modular arithmetic to get a simple understanding of a few of the theorems and the syntax.

Despite this I am not understanding how the proof from the above site goes from this: $$ 10^m \equiv1^m \equiv1(mod3)$$ To this: $$ (a_0+a_1*10+a_2*10^2...+a_n*10^n)\equiv1*(a_0+a_1+a_2...+a_n)(mod3)$$

I understand why the first statement is true, but I fail to see how it allows the second statement to be made. How is it that the second statement follows from the first?

Answer 1

Modular arithmetic basically works just like ordinary arithmetic in respect of addition, subtraction and multiplication (but not division or cancellation). So for example, if you know that $x_1=y_1$ you can conclude that $$a_0+a_1x_1=a_0+a_1y_1\ .$$ Likewise, if $x_1=y_1$, $x_2=y_2$, . . . , $x_n=y_n$, then you can conclude $$a_0+a_1x_1+a_2x_2+\cdots+a_nx_n=a_0+a_1y_1+a_2y_2+\cdots+a_ny_n\ .$$ Just so, if you know that $$x_1\equiv y_1\,,\ x_2\equiv y_2\,,\ldots,\ x_n\equiv y_n\pmod m\ ,$$ then you have $$a_0+a_1x_1+a_2x_2+\cdots+a_nx_n \equiv a_0+a_1y_1+a_2y_2+\cdots+a_ny_n\pmod m\ .$$ Now take $x_k=10^k$ and $y_k=1$ and $m=3$, and you have exactly your situation.

Hope this helps.

Answer 2

HINT:

For integer $a_r$ if $\displaystyle b_r\equiv c_r\pmod m, 0\le r\le n$

$\displaystyle\sum_{r=0}^n a_r\cdot b_r\equiv\sum_{r=0}^n a_r\cdot c_r\pmod m$

$$\sum_{r=0}^n a_r\cdot10^r\equiv\sum_{r=0}^n a_r\cdot1^r\pmod3$$