Divisibility checking tricks

[elim]

Most of us know how to tell whether an integer is divisible by 2, 3, 4, 5, 6, 9, 10, 11
Not so many know why and just very few know how to tell the divisibility of a number by 7, 13, 17,...
Let's see what we can learn about this kind of questions.

First of all, let's define some notation to make things easier:
Let \(n = \sum_{k=0}^m d_{k} 10^k\) be an arbitrary positive integer \((d_{k} \in \mathbf{N} \cap [0,9], \; k=\overline{0,m})\),
Denote \(L_{r}(n) = \displaystyle{\underset{r\leq k \leq m}{\sum} d_{k} 10^k}\) and \(R_{r}(n) =\displaystyle{\underset{0\leq k < r}{\sum} d_{k} 10^k}\)
So \(L_{r}(n)\) is obtained by drop \(R_{r}(n)\) from n. \(R_r(n) = n \% 10^r\) and \(L_r(n) = (n-R_r(n))/10^r\) and \(R_r\) is \(r\)-tail function while \(L_r\) is \(r\)-drop-Left function. And we have \[n = 10^r L_r(n)+R_r(n) \] 2ndly, Some general observattions
\(\begin{array}{rl}
\quad\textrm{(1)} & (p | n) \Leftrightarrow (p| (n + mp) \quad \forall m \in \mathbf{Z})\\
\textrm{(2)} & (p | n) \Leftrightarrow (p | qn, \quad (p,q) =1)\\
\textrm{(3)} & (p | n) \Leftrightarrow (p | n/q, \quad ((p,q) =1)\wedge (q|n))
\end{array} \)

[elim]

\(\begin{array}{rl}
\quad\textrm{(0)} & \textrm{Characteristic of }0 \textrm{ and } 1 \textrm{:} \quad\forall a,m \in \mathbf{N}^+ (a | 0, 1|m)\\
\textrm{(1)} & (2| n) \Leftrightarrow (2| R_1(n))\\
\textrm{(2)} & (3 | \sum_{k=0}^{n} a_k 10^k) \Leftrightarrow (3 | \sum_{k=0}^{n} a_k) \Leftrightarrow (3 \mid (L_1(n)-2R_1(n)))\\
\textrm{(3)} & (4 | n) \Leftrightarrow ( 4 | R_2(n))\\
\textrm{(4)} & (5 | n) \Leftrightarrow R_1(n) \in \left\{0,5\right \}\\
\textrm{(5)} & (6 | n) \Leftrightarrow \left((2 | n) \wedge (3|n)\right)\\
\textrm{(6)} & (7 | n) \Leftrightarrow ( 7 | (L_3(n)-R_3(n)))\Leftrightarrow ( 7 | ( L_1(n) - 2R_1(n)))\\
\textrm{(7)} & (8 | n) \Leftrightarrow (8 | R_3(n)) \Leftrightarrow ((2|n)\wedge(4 | R_2(n/2) ))\\
\textrm{(8)} & (9 | \sum_{k=0}^n a_k 10^k) \Leftrightarrow (9 | \sum_{k=0}^n a_k) \Leftrightarrow 9 \mid (L_1(n)+R_1(n))\\
\textrm{(9)} & (10 | n) \Leftrightarrow (R_1(n)=0) \\
\textrm{(10)} & (11 | \sum_{k=0}^n a_k 10^k) \Leftrightarrow (11 | \sum_{k=0}^n \left( a_{2k+1}-a_{2k}\right)) \Leftrightarrow ( 11 | (L_1(n) - R_1(n)))\\
\textrm{(11)} & (12 | n) \Leftrightarrow ((3 | n) \wedge (4|n))\\
\textrm{(12)} & (13 | n) \Leftrightarrow (13 | (L_3(n)-R_3(n)))\Leftrightarrow ( 13 | (L_1(n) + 4R_1(n)))\\
\textrm{(13)} & (17 | n) \Leftrightarrow (17 | (L_8(n)-R_8(n)))\Leftrightarrow 17 | (L_1(n) - 5R_1(n)) \Leftrightarrow (17 | R_3(n) - 3L_3(n))\\
\textrm{(14)} & (19 | n) \Leftrightarrow (19 | (L_9(n)-R_9(n)))\Leftrightarrow (19 | (L_1(n) + 2R_1(n))) \Leftrightarrow (19 | (R_3(n) - 7L_3(n)))\\
\textrm{(15)} & (23 | n) \Leftrightarrow (23 | (L_11(n)-R_11(n)))\Leftrightarrow (23 | (R_4(n) - 5L_4(n)))\\
\textrm{(16)} & (29 | n) \Leftrightarrow (29 | (L_14(n)-R_14(n)))\Leftrightarrow (29 | (R_4(n) - 5L_4(n)))
\end{array} \)
Examples:
To check if \(314159265\) is divisible by \(7\), combine the results in the main post, we have
\(314159265\to 30603202 \to 204040-4 \to 60501 \to 401-2 = 399 \to 39-18 = 21 \) or
\(314159265 \to 34159-265=33894\to 33-894\to 861\to 16-2\) so \(7|314159265\)

[elim]

The Theory
We have \(n = 10^r L_r(n) + R_r(n)\) and for any \(k \in \mathbb{Z}\) we have
\(L_r(n) + kR_r(n) = \displaystyle{\frac{n-R_r(n)+k10^rR_r(n)}{10^r}=\frac{n-(k10^r-1)R_r(n)}{10^r}}\)
When \((10^r, p)=1\), \(\exists k,m \in \mathbb{Z} \; (k10^r + mp = 1) \Leftrightarrow \exists k \in \mathbb{Z}\; (p \mid (k10^r -1)))\)
Take such \(k\), we then have
\(\quad (p \mid n) \Leftrightarrow (p\mid (L_r(n)+kR_r(n))), \quad \quad n \equiv 10^r (L_r(n)+kR_r(n)) \pmod{p}\)

[elim]

Lemma Fix \(r \in \mathbb{N}^+\), then for any \(n \in \mathbb{N}\), there is a unique sequence of integers \(a_0,\cdots, a_m \in \mathbb{N}\) such that \(n=\sum_{k=0}^m a_k (10^r)^k\). If \(n > 0\) then \(a_m > 0 \quad \square\)
Consider \(P(x)=\sum_{k=0}^m a_k x^k \quad \quad (m > 0)\), let \(Q(x) = P(x)-\sum_{k=0}^m (-1)^k a_k\), then \(Q(-1)=0\) and so
Theorem \(P(x) = (x+1)U(x)+\sum_{k=0}^m (-1)^k a_k\) for some polynomial \(U(x)\) of degree \(m-1\) and
\(\quad \quad \quad P(x) \equiv \sum_{k=0}^m (-1)^k a_k \pmod{x+1}\quad\) In fact \(U(x) = \sum_{k=0}^{m-1}(\sum_{j=k+1}^{m}(-1)^{j-k-1} a_j) x^k \quad \square\)

Let \(x = 10^r, \quad a_k \in \mathbb{Z}\) with \(|a_k| < 10^r\), \(P(x)\) can represent any integer and we have \(P(10^r) \equiv \sum_{k=0}^m (-1)^k a_k \pmod{10^r+1}\). The similar argument gives \(P(10^r) \equiv \sum_{k=0}^m a_k \pmod{10^r-1}\)