# some divisibility tests

We want to derive the divisibility tests for 3, 9, and 11.

Let

 $A\;=\;a_{n}\!\cdot\!10^{n}\!+\!a_{n-1}\!\cdot\!10^{n-1}\!+\ldots+\!a_{0}$

be the digital representation of the integer $A$ in the decadic system ($0\leq a_{i}\leq 9$).

Since  $10\equiv 1\pmod{3,\,9}$,  we have also  $10^{i}\equiv 1\pmod{3,\,9}$  for each $i$,  and hence

 $a_{i}\!\cdot\!10^{i}\equiv a_{i}\!\pmod{3,\,9}.$

Consequently

 $A\;=\;\sum_{i=0}^{n}a_{i}\!\cdot\!10^{i}\;\equiv\;\sum_{i=0}^{n}a_{i}\!\pmod{3% ,\,9}.$

This congruence means that

 $\displaystyle\sum_{i=0}^{n}a_{i}\;\equiv\;0\;\pmod{3,\,9}\qquad\Leftrightarrow% \qquad A\;\equiv\;0\;\pmod{3,\,9}.$ (1)

The fact  $10\equiv-1\pmod{11}$  similarly yields

 $A\;=\;\sum_{i=0}^{n}a_{i}\!\cdot\!10^{i}\;\equiv\;\sum_{i=0}^{n}(-1)^{i}a_{i}% \!\pmod{11},$

whence

 $\displaystyle\sum_{i=0}^{n}(-1)^{i}a_{i}\;\equiv\;0\;\pmod{11}\qquad% \Leftrightarrow\qquad A\;\equiv\;0\;\pmod{11}.$ (2)

The results (1) and (2) may be rendered as the following:

• $A$ is divisible by 3 (resp. 9) if and only if  $a_{0}\!+\!a_{1}\!+\ldots+\!a_{n}$  is.

• $A$ is divisible by 11 if and only if  $a_{0}\!-\!a_{1}\!+-\ldots+\!(-1)^{n}a_{n}$  is.

Title some divisibility tests SomeDivisibilityTests 2014-05-29 11:26:48 2014-05-29 11:26:48 pahio (2872) pahio (2872) 7 pahio (2872) Derivation msc 11A63 msc 11A07