Post Reply 
 
Thread Rating:
  • 1 Votes - 3 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Divisibility checking tricks
02-21-2010, 06:40 PM
Post: #1
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,...
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} \)
Find all posts by this user
Quote this message in a reply
03-01-2010, 02:46 PM
Post: #2
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\)
Find all posts by this user
Quote this message in a reply
04-28-2010, 10:27 AM
Post: #3
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}\)
Find all posts by this user
Quote this message in a reply
04-28-2010, 09:00 PM
Post: #4
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}\)
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


Contact Us | Software Frontier | Return to Top | Return to Content | Lite (Archive) Mode | RSS Syndication