Vrftsjtryk

I've just learned modular arithmetic today, and am really struggling to understand a certain theorem.

The theorem given to us states the following:

Let m $in mathbb{N}$. For any integers a, b, c, and d, if $a equiv b pmod m$ and $c equiv d pmod m$ then,

1. $a+c equiv b+d pmod m$


2. $a-c equiv b-d pmod m$


3. $ac equiv bd pmod m$

In the next section, the notes state the following: "We can use properties of congruence to prove the (familiar) rule that an
integer is divisible by 3 if and only if the sum of its decimal digits is divisible
by 3. The key is to observe that $10 equiv 1 pmod 3$ and so by Theorem 5.10.3 [theorem stated above]
you can change 10 to 1 wherever it occurs. Remember that $3|n$ if and only
if $n equiv 0 pmod 3$."

Next, it goes through the proof it was talking about at the beginning of the first quote:

Suppose $n=d_k cdot b_k + d_{k-1}cdot b_{k-1} + dots + d_1cdot b + d_0$ where $d_k, d_{k-1},dots, d_0$ are the digits of $n$. Also assume that $3|n$. We now have the following:

begin{align}
n equiv 0 pmod 3 &iff d_kcdot 10^k + d_{k-1}cdot 10^{k-1} + dots + d_1cdot 10 + d_0 equiv 0 pmod 3\
&iff d_k cdot 1^k + d_{k-1}cdot 1^{k-1} + dots + d_1 cdot 1 + d_0 equiv 0 pmod 3
end{align}
since $10 equiv 1 pmod 3$.

I don't quite understand how any parts of the theorem stated above allows for substitution.

Thanks for any help.

We are not substituting anything. In an intuitive manner (though not completely rigorous), you can think of numbers congruent in a certain modulo as being equal. Hence since $10equiv 1$ modulo $3$, we have
$$ d_k10^k+d_{k-1}10^{k-1}+cdots+d_010^0= d_k1^k+cdots+d_01^0=d_k+cdots+d_0 pmod 3.$$
Note that the only difference that occurred is that we changed all the $10$s which occurred in the expression to $1$s [to emphasize the thinking that $10$ and $1$ are really the same element, I've used $=$ in place of $equiv$]. The reason we do this is because they are congruent mod $3$.

If you want a more formal explanation, note that regardless of $x$ and $n$, if $x=a$, then $ x^2=xcdot x=acdot a=a^2$ modulo $n$ (this is part 3 of your theorem). By induction it is also true that $x^k=a^k$. Hence we can take linear combinations (this is parts 1 and 2 of your theorem) of $(1,x,x^2,ldots,x^k)$ and get that the result is congruent to the same linear combination of $a$s. In other words, if $p$ is a polynomial and $xequiv a$ modulo $n$, then $p(x)equiv p(a)$ modulo $n$ as well. Now, apply this to your problem with $x=10$, $a=1$ and $n=3$. Do you see how everything works out?

When writing a number in base ten, we understand each digit to be some multiple of a power of ten. This is what the "suppose..." section is trying to generalize. Lets look at a specific example:

$$456 = 4cdot10^2 + 5cdot10^1 + 6cdot10^0$$

Now that the number is expressed as a sum of products, we can apply the theorems. For example, take the fifty part of four hundred and fifty six:

Let
begin{align}
a&=5\
b&=5\
c&=10^1\
d&=1
end{align}

By the third theorem, since $5equiv5pmod 3$ and $10^1equiv 1pmod 3$, it follows that $5cdot10^1 equiv 5cdot1 pmod 3$. Note that all powers of ten are equivalent to one modulo three. You can make the same argument for $400equiv 4pmod 3$. Therefore:

$$456 = 4cdot10^2 + 5cdot10^1 + 6cdot10^0 equiv 4 + 5 + 6 pmod 3$$

The real trick is being able to make this argument for an arbitrary number with an unknown number of digits. Can you show $10^n equiv 1^n equiv 1$?