logo

Division Test for 3 and Proof of the Division Test for 9 📂Number Theory

Division Test for 3 and Proof of the Division Test for 9

Theorem

If the sum of all digits is a multiple of 33, it is a multiple of 33, and if it is a multiple of 99, it is a multiple of 99.

Explanation

For example,

  • 81428142 is a multiple of 33 by 8142=3⋅27148142=3 \cdot 2714, and indeed 8+1+4+2=158+1+4+2=15 is a multiple of 33.
  • 19451251945125 is a multiple of 99 by 1945125=9⋅2161251945125=9 \cdot 216125, and indeed 1+9+4+5+1+2+5=271+9+4+5+1+2+5=27 is a multiple of 99.

Although the significance of divisibility tests has diminished in modern times, they are still an interesting tool. Multiples of 2,4,5,82,4,5,8 are very easy to determine, but numbers like 3,7,9,113, 7, 9, 11 require separate proofs. Fortunately, except for 7, proofs and understanding are generally easy.

Proof

Strategy: The key to the proof is to break down the powers of 10 into 1 and 99..99 and only consider the digits. For convenience in proving, we will use the following notation in this post.

[anan−1…a1a0]=an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100 [a_{n} a_{n-1} … a_{1} a_{0}]= a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} For example, 57145714 can be represented as follows. [5714]=5000+700+10+4=5⋅103+7⋅102+1⋅101+4⋅100 [5714]=5000+700+10+4=5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} If the proof is not clear, it may be helpful to think about it with a real example.

[anan−1…a1a0]=an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100=an⋅(10n−1)+an−1⋅(10n−1−1)+⋯+a1⋅(101−1)+a0+(an+an−1+…+a1)=∑k=1nak(10k−1)+∑k=0nak \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} \\ =& a_{n} \cdot \left( 10^{n} -1 \right) + a_{n-1} \cdot \left( 10^{n-1} -1 \right) + \cdots + a_{1} \cdot \left( 10^{1} -1 \right) \\ & + a_{0} +\left( a_{n} + a_{n-1} +…+ a_{1} \right) \\ =& \sum_{k=1}^{n} a_{k} \left( 10^{k} - 1 \right) + \sum_{k=0}^{n} a_{k} \end{align*}

Here, 10n−1=[99…99]10^{n} -1=[99…99] is a multiple of both 33 and 99 (for example, 103−1=99910^{3} -1=999). Therefore, if ∑k=0nak\displaystyle \sum_{k=0}^{n} a_{k} is a multiple of 3, [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] is also a multiple of 3. Similarly, if ∑k=0nak\displaystyle \sum_{k=0}^{n} a_{k} is a multiple of 9, [anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] is also a multiple of 9.

■