Generalization of Divisibility Rules for Primes

Published by Ganit Charcha | Category - Math Articles | 2014-09-27 11:56:15

For any prime $p$ other than $2$ and $5$ first find out some $x$ such that $px = 10y + 1,$ where $x$ and $y$ are both integers. In number theory, Bezout's Identity says that for any two non-zero integers $a$ and $b$ with $d$ = $g.c.d(a, b)$ there exists integers $x$ and $y$ such that $d$ = $g.c.d(a, b)$ = $ax + by$. If $p$ is a prime other than $2$ and $5$, then $g.c.d(p, 10)$ = $1$ and so from Bezout's Identity it is evident that integers $x$ and $y$ exists such that $$px = 10y + 1.$$
Now any integer $$N = 10^{k}.n_{k} + 10^{k-1}.n_{k-1} + 10^{k-2}.n_{k-2} + \ldots + 10^{2}.n_{2} + 10.n_{1} + n_{0},$$ is divisible by prime number $p$ if $$N^{'} = 10^{k-1}n_{k} + 10^{k-2}.n_{k-1} + 10^{k-3}.n_{k-2} + \ldots + 10.n_{2} + n_{1} - y.n_{0}$$ is divisible by $p$. Note that $N^{'}$ is also an integer. 
If $N^{'}$ is divisible by $p,$ then there exists an integer $m$ such that $$N^{'} = m.p$$$$=> \hspace{0.1in}10.N^{'} = 10.m.p$$$$=> \hspace{0.1in} 10^{k}.n_{k} + 10^{k-1}.n_{k-1} + 10^{k-2}.n_{k-2} + \ldots + 10^{2}.n_{2} + 10.n_{1} -10.y.n_{0} = 10.m.p$$$$=> N = 10.y.n_{0} + n_{0} + 10.m.p = p.x.n_{0} + 10.m.p$$$$=> N = (n_{0}.x + 10.m).p$$This proves that integer $N$ is also divisible by $p$. This result provides us with an algorithm to find out whether a given integer $N$ is divisible by any prime number $p$ ($p \neq 2$ and $p \neq 5$) or not. The algorithm is explained below through self explanatory examples and hence does not require to be menioned formally.

Illustration

1.
For $p = 7$, we have $7.3 = 10.2 + 1$ and therefore $x = 3$ and $y = 2$. Consider $N = 8645$, then $N^{'}$ = $864 - 2.5$ = $854$. We will now repeat the same procedure on $N^{'}$ = $854,$ and hence $N^{''}$ = $85 - 2.4$ = $77$. Since $77$ is known to be divisible by $7$, then so is $N^{'}$ and $N$. Infact we can quickly find out that $n_{0}.x + 10.m$ = $4.3 + 10.11$ = $122$ is the other factor of $N^{'}$ and $n_{0}.x + 10.m$ = $5.3 + 10.122$ = $1235$ is the other factor of $N$.

2. For $p = 11$, we have $11.1 = 10.1 + 1$ and therefore $x = 1$ and $y = 1$. Consider $N = 1232$, then $N^{'}$ = $123 - 1.2$ = $121$. Repeating the same procedure on $N^{'}$ = $121$, we have $N^{''}$ = $12 - 1.1$ = $11$ which is divisible by $11$. Hence, $N^{'}$ and $N$ both are divisible by $11$. We can quickly find out that $n_{0}.x + 10.m$ = $1.1 + 10.1$ = $11$ is the other factor of $N^{'}$ = $121$ and $n_{0}.x + 10.m$ = $2.1 + 10.11$ = $112$ is the other factor of $N$.

3. For $p = 31$, we have $31.1 = 10.3 + 1$ and therefore $x = 1$ and $y = 3$. Consider $N = 14136$, the $N^{'}$ = $1413 - 3.6$ = $1395$.We will now repeat the same procedure on $N^{'}$ = $1395$, and hence $N^{''}$ = $139 - 3.5$ = $124$. Since $124$ is known to be divisible by $31$, then so is $N^{'}$ and $N$. $n_{0}.x + 10.m$ = $5.1 + 10.4$ = $45$ is the other factor such that $45.31$ = $1235$ = $N^{'}$ and $n_{0}.x + 10.m$ = $6.1 + 10.45$ = $456$ is the other factor of $N$ such that $456.31$ = $14136$ = $N$.

Steps to find out $x$ and $y$ such that $px = 10y + 1$

Since $p$ ($p \neq 2$ and $p \neq 5$) is a prime number so $g.c.d(p, 10) = 1$. If $p > 10$, then $g.c.d(p, 10)$ = $g.c.d(p-10, 10)$ = $1$ or else if $p < 10$, then $g.c.d(p, 10)$ = $g.c.d(10-p, p)$ = $1$. This relation provides us with a method to find out the values of $x$ and $y$. We will illustrate the method through examples.

1. Let us take $p = 7 (< 10)$. Note that $g.c.d(10, 7)$ = $g.c.d(3,7)$ = $g.c.d(4,3)$ = $g.c.d(3,1)$ = $1$ and also we see $10 - 7 = 3$, $7 - 3 = 4$ and $4 - 3 = 1$. Moving backwards from $1$, we therefore have $1$ = $4 - 3$ = $7 - 2.3$ = $3.7 - 2.10$ and hence $7.3$ = $10.2 + 1$.

2. Consider $p = 31 (>10)$. Note that $g.c.d(10, 31)$ = $g.c.d(10,21)$ = $g.c.d(10,11)$ = $g.c.d(10, 1)$ = $1$ and so we have $31 - 10$ = $21$, $21 - 10$ = $11$ and $11 - 10$ = $1$. Moving backwards from $1$ in a similar fashion as above we have $1$ = $11 - 10$ = $21 - 2.10$ = $31 - 3.10$ and hence $31.1$ = $10.3 + 1$.

So this is certainly an way to find out the values of $x$ and $y$. If the prime $p$ is large enough then how many steps it would take to figure out the values for $x$ and $y$. Is it possible to improve the method further by minimizing the number of steps? I would like the readers of this article to find out an improvement over this method.

References

[1] C. C. Briggs, Simple Divisibility Rules for the 1st 1000 prime numbers, ArXiv Mathematics e-prints, math/0001012, January 2000, http://arxiv.org/abs/math/0001012v1.




comments powered by Disqus

Publication Pages


Publication Archive



Subscribe GanitCharcha


Enter your email address:


Delivered by FeedBurner


Join us