Chia hết, ước và bội

Mọi lũy thừa của $10$ chia cho $9$ đều dư $1$ (vì $10=9+1$), nên việc dịch một chữ số lên hàng cao hơn không bao giờ làm thay đổi đóng góp của nó theo modulo $9$ — cả số đồng dư với tổng đơn giản các chữ số của nó.

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$.

Không giống $9$, các lũy thừa của $10$ không giữ đồng dư $1$ theo modulo $11$ — thay vào đó chúng đổi dấu ở mỗi bước, vì bản thân $10$ đồng dư $-1$ theo modulo $11$. Chữ số ở vị trí chẵn đóng góp bình thường, vị trí lẻ đóng góp âm.

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

Bước 2. Thay vào khai triển theo hàng vị trí: $n=\sum_i d_i10^i \equiv \sum_i d_i(-1)^i \pmod{11}$, đúng bằng tổng đan dấu $\sum_i (-1)^i d_i$.

Bước 3. Kết luận: $11\mid n$ đúng khi $n\equiv0\pmod{11}$, mà theo Bước 2 điều này xảy ra đúng khi $11$ chia hết $\sum_i (-1)^i d_i$.