OMath!
Divisibility checking tricks - Printable Version

+- OMath! (http://math.elinkage.net)
+-- Forum: Math Forums (/forumdisplay.php?fid=4)
+--- Forum: Number Theory (/forumdisplay.php?fid=7)
+--- Thread: Divisibility checking tricks (/showthread.php?tid=20)



Divisibility checking tricks - elim - 02-21-2010 06:40 PM

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} \)


Some Results - elim - 03-01-2010 02:46 PM

\(\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\)


RE: Divisibility checking tricks - elim - 04-28-2010 10:27 AM

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}\)


More analysis - elim - 04-28-2010 09:00 PM

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}\)