• 1 Votes - 3 Average
• 1
• 2
• 3
• 4
• 5
 Divisibility checking tricks
02-21-2010, 06:40 PM
Post: #1
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
Divisibility checking tricks
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,...

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}$$
03-01-2010, 02:46 PM
Post: #2
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
Some Results
$$\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$$
04-28-2010, 10:27 AM
Post: #3
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
RE: Divisibility checking tricks
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}$$
04-28-2010, 09:00 PM
Post: #4
 elim Moderator Posts: 578 Joined: Feb 2010 Reputation: 0
More analysis
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}$$
 « Next Oldest | Next Newest »

Forum Jump: