# Substitutions in Modular Arithmetic

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_1\cdot 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_k\cdot 10^k + d_{k-1}\cdot 10^{k-1} + \dots + d_1\cdot 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 $$10\equiv 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=x\cdot x=a\cdot 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 $$x\equiv 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 = 4\cdot10^2 + 5\cdot10^1 + 6\cdot10^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 $$5\equiv5\pmod 3$$ and $$10^1\equiv 1\pmod 3$$, it follows that $$5\cdot10^1 \equiv 5\cdot1 \pmod 3$$. Note that all powers of ten are equivalent to one modulo three. You can make the same argument for $$400\equiv 4\pmod 3$$. Therefore:

$$456 = 4\cdot10^2 + 5\cdot10^1 + 6\cdot10^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$$?