Quy tắc tổng chữ số để chia hết cho 9 (và 3)

Bước 1. Chứng minh bằng quy nạp rằng $10^i \equiv 1 \pmod 9$ với mọi $i\ge0$. Cơ sở $i=0$: $10^0=1\equiv1\pmod9$. Bước quy nạp: nếu $10^i\equiv1\pmod9$, thì $10^{i+1}=10\cdot10^i\equiv10\cdot1=10\equiv1\pmod9$ (dùng $10 \equiv 1 \pmod 9$). Vậy $10^i\equiv1\pmod9$ với mọi $i$.

Bước 2. Thay vào khai triển theo hàng vị trí: $n=\sum_i d_i 10^i \equiv \sum_i d_i\cdot1 = \sum_i d_i \pmod9$. Vậy $n$ và tổng chữ số của nó luôn để lại cùng số dư khi chia cho $9$.

Bước 3. Kết luận: $9\mid n$ đúng khi $n\equiv0\pmod9$, mà theo Bước 2 điều này xảy ra đúng khi $\sum_i d_i\equiv0\pmod9$, tức đúng khi $9$ chia hết tổng chữ số. Vì $9=3\times3$ và cùng đồng dư thức $10\equiv1\pmod3$ cũng đúng, lập luận giống hệt với $3$ thay cho $9$ ở mọi chỗ chứng minh phiên bản chia hết cho $3$.