# 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.

## 2 Answers

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$$?