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.