Divisibility rules for 3 and 9

Divisibility by 3

A number is divisible by $3$ iff the sum of its digits is divisible by $3$.

Divisibility by 9

A number is divisible by $9$ iff the sum of its digits is divisible by $9$.

[!IMPORTANT] A base-10 integer $N$ has the same remainder mod $3$ and mod $9$ as its digit sum.

Why the digit-sum rule works: $10 \equiv 1 \pmod{3}$ and $\pmod{9}$

Write a positive integer in base 10:

$$N = d_0 + d_1\cdot 10 + d_2\cdot 10^2 + \cdots + d_n\cdot 10^n.$$

Modulo 3: We have $10 \equiv 1 \pmod{3}$, so $10^k \equiv 1 \pmod{3}$ for every $k \ge 0$. Therefore:

$$N \equiv d_0 + d_1 + d_2 + \cdots + d_n \pmod{3}.$$

So $N$ and the digit sum leave the same remainder when divided by $3$. In particular:

• $3 \mid N$ iff $3 \mid (\text{digit sum})$.

Modulo 9: Similarly $10 \equiv 1 \pmod{9}$, so $10^k \equiv 1 \pmod{9}$. Hence:

$$N \equiv d_0 + d_1 + \cdots + d_n \pmod{9}.$$

So $9 \mid N$ iff $9 \mid (\text{digit sum})$.

Example

• $4\,761$ has digit sum $4+7+6+1 = 18$. So $4\,761 \equiv 18 \equiv 0 \pmod{9}$, hence divisible by $9$ (and by $3$).