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,
- $a+c \equiv b+d \pmod m$
- $a-c \equiv b-d \pmod m$
- $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.
Best Answer
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$?