Divisibility rules/Rule 2 for 13 proof

Proof

This is based on divisibility by 11 rule or divisibility by 7 rule

Assume N has 3k digits, otherwise add zeros to the left. WLOG let $N = a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6a_5a_4a_3a_2a_1a_0$ where the $a_i$ are base-ten numbers. Then $N = 10^{3k-1} a_{3k-1} + 10^{3k-2} a_{3k-2} + 10^{3k-3} a_{3k-3} \cdots + 10^8 a_8 + 10^7 a_7 + 10^6 a_6 + 10^5 a_5 + 10^4 a_4 + 10^3 a_3 + 10^2 a_2 + 10 a_1 + a_0.$ $= 1000^{k-1} (100 a_{3k-1} + 10 a_{3k-2} + a_{3k-3}) \cdots + 1000^2 (100 a_8 + 10 a_7 + a_6) + 1000 (100 a_5 + 10 a_4 + a_3) + (100 a_2 + 10 a_1 + a_0).$ Rewriting as 3 digit numbers, that is, partitioning $N$ into 3 digit numbers ( $a_{3k-1}a_{3k-2}a_{3k-3}\cdots a_8a_7a_6 a_5a_4a_3 a_2a_1a_0$ ). $= 1000^{k-1} (a_{3k-1}a_{3k-2}a_{3k-3}) \cdots + 1000^2 (a_8a_7a_6) + 1000 (a_5a_4a_3) + (a_2a_1a_0).$

Since $1000\equiv -1\pmod{13}$ ,

$1000^{k-1} (a_{3k-1}a_{3k-2}a_{3k-3}) \cdots + 1000^2 (a_8a_7a_6) + 1000 (a_5a_4a_3) + (a_2a_1a_0)$ $\equiv (-1)^{k-1} (a_{3k-1}a_{3k-2}a_{3k-3}) \cdots + (-1)^2 (a_8a_7a_6) - (a_5a_4a_3) + (a_2a_1a_0) \pmod {13}.$

This is the alternating sum of groups of 3 digit numbers of $N$ , which is what we wanted.

Page

Toolbox

Search

Divisibility rules/Rule 2 for 13 proof

Proof

See also