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

A simple law of number theory discovered in elementary school, only after college did I know how to prove it.

Preface

When I was in elementary school, I got to know a very interesting law of number theory:

The sum of the digits in multiples of 3 can be divisible by 3.

At that time, I was learning division in elementary school. After understanding this law, I was invincible in some multiple-choice questions involving remainders (for example, given some digits, which combination of them can be selected to form a multiple of a certain number). Since then, I often wonder if there are any numbers with similar laws.

After examining one by one from 1 in this way, I was surprised to find that the sum of the digits in multiples of 9 can be divisible by 9!

I was excited to find Teacher Yang, who teaches mathematics with this rule. She tried a few numbers and found that it was true. She was very pleased, but she couldn’t satisfy my curiosity: “Maybe you can explain it when you go to junior high school.”

For the same problem, the junior high school math teacher studied it all night and told me: “High school should talk about this content, I forgot a little.”

I learned the base system in high school. After experimenting, I further extended the law 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 in base-N system, then $S_{(N)}=\sum_{i=1}^{k}d_{i}$ is a multiple of (N-1). Note that the parenthesized subscript of $X_{(N)}$ means represented in base-N system.

For example, in our commonly used decimal system, $1233$ is a multiple of $9$, then $S=1+2+3+3=9$ is divisible by $9$.

In a hexadecimal system, for example, $435_{(7)}$ is a multiple of $6$ ($435_{(7)}$ is $222_{(10)}$ in decimal system), then $S_{(7)} = 4_{(7)} + 3_{(7)} + 5_{(7)} = 15_{(7)} = 12_{(10)} $ is divisible by $6$. It should be noted that whether a number can be divisible by another number is an inherent property of this number and has nothing to do with the representation of the base.

My math was not good when I was in high school. The high school math teacher thereby advised me to spend more time in the content of the syllabus of College Entrance Examination. This law was put aside again.

Proof

The proof of this law is actually very simple (this may also be the reason why the proof could not be found before). Just having a few relevant knowledge of modular operation is enough to prove it.

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

And:

$$
\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}
$$

Hence, if $n_{(N)} = \sum_{i=1}^{k}d_{i} \times N^{i-1}$ is a multiple of $(N-1)$, which implies $n_{(N)} \mod (N-1) \equiv 0$, then $\sum_{i=1}^{k} d_{i} \mod (N-1) \equiv 0$ must hold.

Through this proof, we can further summarize the law as:

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

Although it is a very simple proof, I still feel satisfied when I came up with ideas to answer my concerns in elementary school.

PS: Hexo + MathJaX really sucks. I have tried my best to format it like this… If you have any concerns or questions, feel free to leave a message.