A College Level Proof of the Laws Discovered at My Elementary Level

A simple rule from number theory that I stumbled upon in elementary school, and only learned how to prove in college.

Preface

Back in elementary school, when we were first taught a bit of number theory, I came across a rather neat rule:

If a number is a multiple of 3, its digits add up to a multiple of 3.

We were learning division at the time, and this felt like a treasure. It made me unbeatable on multiple-choice questions involving remainders — one type I still remember: given a handful of digits, which combination of them forms a multiple of some given number? From then on I kept wondering which other numbers had rules like this.

Working through them one by one starting from 1, I was delighted to find that the digits of a multiple of 9 also add up to a multiple of 9!

I took the rule to Ms. Yang, my math teacher, all excited. She tried a few numbers, saw that it held, and was pleased — but she couldn’t satisfy my curiosity: “Maybe you’ll be able to explain it once you get to junior high.”

I put the same question to my junior high math teacher, who spent a whole evening on it and came back with: “I think this comes up in high school. I’ve forgotten some of it.”

In high school I learned about number bases, and after playing around with a few examples I extended the rule to:

For a base-N $(N\ge2)$ system, if $\overline{d_{k}d_{k-1}...d_1} _{(N)}$ is a multiple of $(N-1)$, where $d_{i}$ is the $i$-th digit of this number counting from the right, then $S_{(N)}=\sum_{i=1}^{k}d_{i}$ is divisible by (N-1). Here the parenthesized subscript of $X_{(N)}$ means written in base N.

For example, in the decimal system we use every day, $1233$ is a multiple of $9$, and $S=1+2+3+3=9$ is indeed divisible by $9$.

Or take a base-7 system: $435_{(7)}$ is a multiple of $6$ ($435_{(7)}$ is $222_{(10)}$ in decimal), and $S_{(7)} = 4_{(7)} + 3_{(7)} + 5_{(7)} = 15_{(7)} = 12_{(10)} $ is divisible by $6$. It is worth noting here that whether one number is divisible by another is an intrinsic property of the number itself, and has nothing to do with the base it happens to be written in.

My math wasn’t particularly good in high school, and my teacher advised me to spend the time on what was actually in the college entrance exam syllabus — so the rule got shelved once again.

Proof

After all that rambling: the proof is in fact quite simple (which may well be why I could never find one written down anywhere). A little familiarity with modular arithmetic is all it takes.

Write: $$ \begin{equation} n_{(N)} = \overline{d_{k}d_{k-1}...d_1} _{(N)} \end{equation} $$

We also have:

$$
\begin{equation}
n_{(N)} = \sum_{i=1}^{k}{d_i} \times N^{i-1}
\end{equation}
$$

Then:

$$
\begin{equation}
\begin{aligned}
n_{(N)}\mod (N-1) & \equiv \sum_{i=1}^{k}d_{i} \times N^{i-1} \mod (N-1) \\
& \equiv (d_{k} \times N^{k-1} + d_{k-1} \times N^{k-2} + … + d_{1} \times N^{0}) \mod (N-1) \\
& \equiv [(d_{k} \times N^{k-1}) \mod (N-1)\ + … +\ (d_{1} \times N^{0}) \mod (N-1)] \\ & \space \mod (N-1) \\
& \equiv [[d_{k} \mod (N-1) \times N^{k-1} \mod (N-1)] \\
& \space \mod (N-1) + … + [d_{1} \mod (N-1) \times N^{0} \mod (N-1)] \\
& \space \mod (N-1)] \mod (N-1) \\
& \equiv [d_{k} \times 1 \mod (N-1) + d_{k-1} \times 1 \mod (N-1) \\
& \space + … + d_{1} \times 1 \mod (N-1)] \mod (N-1) \\
& \equiv \sum_{i=1}^{k} d_{i} \mod (N-1)
\end{aligned}
\end{equation}
$$

So if $n_{(N)} = \sum_{i=1}^{k}d_{i} \times N^{i-1}$ is a multiple of $(N-1)$ — in other words, $n_{(N)} \mod (N-1) \equiv 0$ — then $\sum_{i=1}^{k} d_{i} \mod (N-1) \equiv 0$ must hold as well.

The proof also lets us state the rule in a more general form:

For a base-N $(N\ge2)$ system, if $n_{(N)} = \overline{d_{k}d_{k-1}d_{k-2}…d_{1}}_{(N)} $,

that is, $n_{(N)} = \sum_{i=1}^{k}d_{i} \times N^{i-1}$,
then $n_{(N)}$ and $\sum_{i=1}^{k} d_{i}$ are congruent modulo $(N-1)$.

Epilogue

It’s a simple proof of a simple theorem, but working it out for myself and finally filling in a hole left over from elementary school still feels pretty satisfying.

PS: Hexo + MathJax really is painful to work with. This layout is the best I could manage… If you have any questions, feel free to leave a comment.

Cite this post

@misc{brandozhang2019college,
  title  = {A College Level Proof of the Laws Discovered at My Elementary Level},
  author = {Brando ZHANG},
  year   = {2019},
  url    = {https://brando.dev/2019/04/18/A-College-Level-Proof-of-the-Laws-Discovered-at-My-Elementary-Level/},
  month  = apr
}