Mixing
Divisibility criteria for $7,11,13,17,19$
$begingroup$
A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for divisibility.
I am interested in simple criteria for divisibility by $7,11,13,17,19$.
elementary-number-theory divisibility
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
$endgroup$
add a comment |
$begingroup$
A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for divisibility.
I am interested in simple criteria for divisibility by $7,11,13,17,19$.
elementary-number-theory divisibility
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
$endgroup$
8
$begingroup$
You may want to look at this. There are many other accessible sources.
$endgroup$
– André Nicolas
Mar 12 '13 at 16:18
4
$begingroup$
I think it's worth noting that since $7cdot11cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits.
$endgroup$
– Harald Hanche-Olsen
Mar 12 '13 at 17:02
$begingroup$
A cheap answer
$endgroup$
– Antonio Hernandez Maquivar
Oct 4 '16 at 10:53
add a comment |
$begingroup$
A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for divisibility.
I am interested in simple criteria for divisibility by $7,11,13,17,19$.
elementary-number-theory divisibility
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
$endgroup$
A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for divisibility.
I am interested in simple criteria for divisibility by $7,11,13,17,19$.
elementary-number-theory divisibility
elementary-number-theory divisibility
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
edited Mar 12 '13 at 16:25
user4594
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
asked Mar 12 '13 at 16:14
Milingona AnaMilingona Ana
4911520
4911520
8
$begingroup$
You may want to look at this. There are many other accessible sources.
$endgroup$
– André Nicolas
Mar 12 '13 at 16:18
4
$begingroup$
I think it's worth noting that since $7cdot11cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits.
$endgroup$
– Harald Hanche-Olsen
Mar 12 '13 at 17:02
$begingroup$
A cheap answer
$endgroup$
– Antonio Hernandez Maquivar
Oct 4 '16 at 10:53
add a comment |
8
$begingroup$
You may want to look at this. There are many other accessible sources.
$endgroup$
– André Nicolas
Mar 12 '13 at 16:18
4
$begingroup$
I think it's worth noting that since $7cdot11cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits.
$endgroup$
– Harald Hanche-Olsen
Mar 12 '13 at 17:02
$begingroup$
A cheap answer
$endgroup$
– Antonio Hernandez Maquivar
Oct 4 '16 at 10:53
8
8
$begingroup$
You may want to look at this. There are many other accessible sources.
$endgroup$
– André Nicolas
Mar 12 '13 at 16:18
$begingroup$
You may want to look at this. There are many other accessible sources.
$endgroup$
– André Nicolas
Mar 12 '13 at 16:18
4
4
$begingroup$
I think it's worth noting that since $7cdot11cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits.
$endgroup$
– Harald Hanche-Olsen
Mar 12 '13 at 17:02
$begingroup$
I think it's worth noting that since $7cdot11cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits.
$endgroup$
– Harald Hanche-Olsen
Mar 12 '13 at 17:02
$begingroup$
A cheap answer
$endgroup$
– Antonio Hernandez Maquivar
Oct 4 '16 at 10:53
$begingroup$
A cheap answer
$endgroup$
– Antonio Hernandez Maquivar
Oct 4 '16 at 10:53
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
$(1)$
The formulae for $2,3,5,9,11$ can be derived from $sum_{0le rle n}{a_r10^r}$
Observe that $sum_{0le rle n}{a_r10^r}equiv a_0pmod 2$
$sum_{0le rle n}{a_r10^r}equiv a_0pmod 5$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}a_rpmod 3$ as $9mid(10^r-1)$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}(-1)^ra_rpmod {11}$ as $10^requiv(-1)^rpmod{11}$
$sum_{0le rle n}a_r10^requiv(a_0+a_2+a_4+cdots)-(a_1+a_3+a_5+cdots)pmod{11}$
$(2)$
$N=sum_{0le rle n}a_r10^requiv sum_{0le rle m-1}a_r10^rpmod {10^m}equiv sum_{0le rle m-1}a_r10^rpmod {2^m}$ as $2^smid 10^s$ where integer $sge0$
This explains why $2^mmid Niff $ the numbers with lower $m$ digits of $N$ is divisible by $2^m$
For example, $2524$ will be divisible by $2^2=4$ as $24$ is, but $2514$ will not be divisible by $2^2=4$ as $14$ is not.
Similarly for $5^m$
$(3)$
For any number $y$ co-prime with $10,$ we can have a reduction formula as follows:
If a number be $10a+b,$ we can find $u,v$ in integers such that $10u+ycdot v=1$ (using Bézout's Identity)
So, $u(10a+b)+vcdot ycdot a=a(10u+ycdot v)+ucdot b=a+ucdot bimplies 10a+b$ will be divisible by $yiff ymid(a+ucdot b)$
For example if $y=7, $ we find $3cdot7+(-2)10=1implies u=-2,v=3$
So, $(a+ucdot b)$ becomes $a-2b$
If $y=19,$ we find $2cdot10+(-1)19=1implies u=2implies a+ucdot b=a+2b$
We can always use convergent property of continued fractions to find $u,v$.
There is no strong reason why this can not be generalized to any positive integer bases.
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
add a comment |
$begingroup$
General approach
For divisibility test by odd divisor except ending with 5:
first find multiple of number in the form of $10^n-1$ or $10^n +1$
Now compute remainder by $10^n-1$ or $10^n +1$ which is easy to compute
If this remainder is exactly divisible, then the original number is divisible.
Example
$7 | N$ if and only if $7 | (N % 1001)$
i.e. $N % 7 = (N % 1001) % 7 $
Similarly, $N % 13 = (N % 1001) % 13$.
Cross divisibility test
(VJ's universal divisibility test)
- $7 | 10 T + U$ if and only if $7 | (1T-2U)$, or
- $7 | 10 T + U$ if and only if $7 | (2T+3U)$, or
$7 | 10 T + U$ if and only if $7 | (T+5U)$ etc.
$13 | 10 T + U$ if and only if $13 | (3T-U)$, or
- $13 | 10 T + U$ if and only if $13 | (2T-5U)$, or
- $13 | 10 T + U$ if and only if $13 | (T+4U)$, or
- $13 | 1000 T + U$ if and only if $13 |(T-U)$ etc.
In short, there are many approaches to check divisibility test by number.
You can also check divisibility
- Using least Recurring length concept
- Using Fermat's little theorem
- Using vedic mathematics
To know more, read my Modern approach to speed math secret. This book explores the unique secret behind speed math, Booths multiplication etc.
It explains whole speed math using Zero.
edited Oct 4 '16 at 9:58
Community♦
1
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
$endgroup$
add a comment |
$begingroup$
Let $n=text{'abcdef'}=10^5a+10^4b+10^3c+10^2d+10e+f$. Using modular arithmetic,
$$nequiv 5a+4b+6c+2d+3e+fmod 7.$$
As $10^6bmod7=1$, this repeats for the next groups of $6$ digits.
To get smaller coefficients, you can reduce some of them by $-7$, giving
$$nequiv (f-c)+2(d-a)+3(e-b)mod 7.$$
For instance
$$123456equiv (6-3)+2(4-1)+3(5-2)equiv18mod7$$ isn't divisible by $7$.
You can generalize the method to other divisors.
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f328562%2fdivisibility-criteria-for-7-11-13-17-19%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$(1)$
The formulae for $2,3,5,9,11$ can be derived from $sum_{0le rle n}{a_r10^r}$
Observe that $sum_{0le rle n}{a_r10^r}equiv a_0pmod 2$
$sum_{0le rle n}{a_r10^r}equiv a_0pmod 5$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}a_rpmod 3$ as $9mid(10^r-1)$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}(-1)^ra_rpmod {11}$ as $10^requiv(-1)^rpmod{11}$
$sum_{0le rle n}a_r10^requiv(a_0+a_2+a_4+cdots)-(a_1+a_3+a_5+cdots)pmod{11}$
$(2)$
$N=sum_{0le rle n}a_r10^requiv sum_{0le rle m-1}a_r10^rpmod {10^m}equiv sum_{0le rle m-1}a_r10^rpmod {2^m}$ as $2^smid 10^s$ where integer $sge0$
This explains why $2^mmid Niff $ the numbers with lower $m$ digits of $N$ is divisible by $2^m$
For example, $2524$ will be divisible by $2^2=4$ as $24$ is, but $2514$ will not be divisible by $2^2=4$ as $14$ is not.
Similarly for $5^m$
$(3)$
For any number $y$ co-prime with $10,$ we can have a reduction formula as follows:
If a number be $10a+b,$ we can find $u,v$ in integers such that $10u+ycdot v=1$ (using Bézout's Identity)
So, $u(10a+b)+vcdot ycdot a=a(10u+ycdot v)+ucdot b=a+ucdot bimplies 10a+b$ will be divisible by $yiff ymid(a+ucdot b)$
For example if $y=7, $ we find $3cdot7+(-2)10=1implies u=-2,v=3$
So, $(a+ucdot b)$ becomes $a-2b$
If $y=19,$ we find $2cdot10+(-1)19=1implies u=2implies a+ucdot b=a+2b$
We can always use convergent property of continued fractions to find $u,v$.
There is no strong reason why this can not be generalized to any positive integer bases.
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
add a comment |
$begingroup$
$(1)$
The formulae for $2,3,5,9,11$ can be derived from $sum_{0le rle n}{a_r10^r}$
Observe that $sum_{0le rle n}{a_r10^r}equiv a_0pmod 2$
$sum_{0le rle n}{a_r10^r}equiv a_0pmod 5$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}a_rpmod 3$ as $9mid(10^r-1)$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}(-1)^ra_rpmod {11}$ as $10^requiv(-1)^rpmod{11}$
$sum_{0le rle n}a_r10^requiv(a_0+a_2+a_4+cdots)-(a_1+a_3+a_5+cdots)pmod{11}$
$(2)$
$N=sum_{0le rle n}a_r10^requiv sum_{0le rle m-1}a_r10^rpmod {10^m}equiv sum_{0le rle m-1}a_r10^rpmod {2^m}$ as $2^smid 10^s$ where integer $sge0$
This explains why $2^mmid Niff $ the numbers with lower $m$ digits of $N$ is divisible by $2^m$
For example, $2524$ will be divisible by $2^2=4$ as $24$ is, but $2514$ will not be divisible by $2^2=4$ as $14$ is not.
Similarly for $5^m$
$(3)$
For any number $y$ co-prime with $10,$ we can have a reduction formula as follows:
If a number be $10a+b,$ we can find $u,v$ in integers such that $10u+ycdot v=1$ (using Bézout's Identity)
So, $u(10a+b)+vcdot ycdot a=a(10u+ycdot v)+ucdot b=a+ucdot bimplies 10a+b$ will be divisible by $yiff ymid(a+ucdot b)$
For example if $y=7, $ we find $3cdot7+(-2)10=1implies u=-2,v=3$
So, $(a+ucdot b)$ becomes $a-2b$
If $y=19,$ we find $2cdot10+(-1)19=1implies u=2implies a+ucdot b=a+2b$
We can always use convergent property of continued fractions to find $u,v$.
There is no strong reason why this can not be generalized to any positive integer bases.
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
add a comment |
$begingroup$
$(1)$
The formulae for $2,3,5,9,11$ can be derived from $sum_{0le rle n}{a_r10^r}$
Observe that $sum_{0le rle n}{a_r10^r}equiv a_0pmod 2$
$sum_{0le rle n}{a_r10^r}equiv a_0pmod 5$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}a_rpmod 3$ as $9mid(10^r-1)$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}(-1)^ra_rpmod {11}$ as $10^requiv(-1)^rpmod{11}$
$sum_{0le rle n}a_r10^requiv(a_0+a_2+a_4+cdots)-(a_1+a_3+a_5+cdots)pmod{11}$
$(2)$
$N=sum_{0le rle n}a_r10^requiv sum_{0le rle m-1}a_r10^rpmod {10^m}equiv sum_{0le rle m-1}a_r10^rpmod {2^m}$ as $2^smid 10^s$ where integer $sge0$
This explains why $2^mmid Niff $ the numbers with lower $m$ digits of $N$ is divisible by $2^m$
For example, $2524$ will be divisible by $2^2=4$ as $24$ is, but $2514$ will not be divisible by $2^2=4$ as $14$ is not.
Similarly for $5^m$
$(3)$
For any number $y$ co-prime with $10,$ we can have a reduction formula as follows:
If a number be $10a+b,$ we can find $u,v$ in integers such that $10u+ycdot v=1$ (using Bézout's Identity)
So, $u(10a+b)+vcdot ycdot a=a(10u+ycdot v)+ucdot b=a+ucdot bimplies 10a+b$ will be divisible by $yiff ymid(a+ucdot b)$
For example if $y=7, $ we find $3cdot7+(-2)10=1implies u=-2,v=3$
So, $(a+ucdot b)$ becomes $a-2b$
If $y=19,$ we find $2cdot10+(-1)19=1implies u=2implies a+ucdot b=a+2b$
We can always use convergent property of continued fractions to find $u,v$.
There is no strong reason why this can not be generalized to any positive integer bases.
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
$(1)$
The formulae for $2,3,5,9,11$ can be derived from $sum_{0le rle n}{a_r10^r}$
Observe that $sum_{0le rle n}{a_r10^r}equiv a_0pmod 2$
$sum_{0le rle n}{a_r10^r}equiv a_0pmod 5$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}a_rpmod 3$ as $9mid(10^r-1)$
$sum_{0le rle n}a_r10^requiv sum_{0le rle n}(-1)^ra_rpmod {11}$ as $10^requiv(-1)^rpmod{11}$
$sum_{0le rle n}a_r10^requiv(a_0+a_2+a_4+cdots)-(a_1+a_3+a_5+cdots)pmod{11}$
$(2)$
$N=sum_{0le rle n}a_r10^requiv sum_{0le rle m-1}a_r10^rpmod {10^m}equiv sum_{0le rle m-1}a_r10^rpmod {2^m}$ as $2^smid 10^s$ where integer $sge0$
This explains why $2^mmid Niff $ the numbers with lower $m$ digits of $N$ is divisible by $2^m$
For example, $2524$ will be divisible by $2^2=4$ as $24$ is, but $2514$ will not be divisible by $2^2=4$ as $14$ is not.
Similarly for $5^m$
$(3)$
For any number $y$ co-prime with $10,$ we can have a reduction formula as follows:
If a number be $10a+b,$ we can find $u,v$ in integers such that $10u+ycdot v=1$ (using Bézout's Identity)
So, $u(10a+b)+vcdot ycdot a=a(10u+ycdot v)+ucdot b=a+ucdot bimplies 10a+b$ will be divisible by $yiff ymid(a+ucdot b)$
For example if $y=7, $ we find $3cdot7+(-2)10=1implies u=-2,v=3$
So, $(a+ucdot b)$ becomes $a-2b$
If $y=19,$ we find $2cdot10+(-1)19=1implies u=2implies a+ucdot b=a+2b$
We can always use convergent property of continued fractions to find $u,v$.
There is no strong reason why this can not be generalized to any positive integer bases.
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
edited Mar 12 '13 at 16:46
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
answered Mar 12 '13 at 16:27
lab bhattacharjeelab bhattacharjee
227k15158275
227k15158275
add a comment |
add a comment |
$begingroup$
General approach
For divisibility test by odd divisor except ending with 5:
first find multiple of number in the form of $10^n-1$ or $10^n +1$
Now compute remainder by $10^n-1$ or $10^n +1$ which is easy to compute
If this remainder is exactly divisible, then the original number is divisible.
Example
$7 | N$ if and only if $7 | (N % 1001)$
i.e. $N % 7 = (N % 1001) % 7 $
Similarly, $N % 13 = (N % 1001) % 13$.
Cross divisibility test
(VJ's universal divisibility test)
- $7 | 10 T + U$ if and only if $7 | (1T-2U)$, or
- $7 | 10 T + U$ if and only if $7 | (2T+3U)$, or
$7 | 10 T + U$ if and only if $7 | (T+5U)$ etc.
$13 | 10 T + U$ if and only if $13 | (3T-U)$, or
- $13 | 10 T + U$ if and only if $13 | (2T-5U)$, or
- $13 | 10 T + U$ if and only if $13 | (T+4U)$, or
- $13 | 1000 T + U$ if and only if $13 |(T-U)$ etc.
In short, there are many approaches to check divisibility test by number.
You can also check divisibility
- Using least Recurring length concept
- Using Fermat's little theorem
- Using vedic mathematics
To know more, read my Modern approach to speed math secret. This book explores the unique secret behind speed math, Booths multiplication etc.
It explains whole speed math using Zero.
edited Oct 4 '16 at 9:58
Community♦
1
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
$endgroup$
add a comment |
$begingroup$
General approach
For divisibility test by odd divisor except ending with 5:
first find multiple of number in the form of $10^n-1$ or $10^n +1$
Now compute remainder by $10^n-1$ or $10^n +1$ which is easy to compute
If this remainder is exactly divisible, then the original number is divisible.
Example
$7 | N$ if and only if $7 | (N % 1001)$
i.e. $N % 7 = (N % 1001) % 7 $
Similarly, $N % 13 = (N % 1001) % 13$.
Cross divisibility test
(VJ's universal divisibility test)
- $7 | 10 T + U$ if and only if $7 | (1T-2U)$, or
- $7 | 10 T + U$ if and only if $7 | (2T+3U)$, or
$7 | 10 T + U$ if and only if $7 | (T+5U)$ etc.
$13 | 10 T + U$ if and only if $13 | (3T-U)$, or
- $13 | 10 T + U$ if and only if $13 | (2T-5U)$, or
- $13 | 10 T + U$ if and only if $13 | (T+4U)$, or
- $13 | 1000 T + U$ if and only if $13 |(T-U)$ etc.
In short, there are many approaches to check divisibility test by number.
You can also check divisibility
- Using least Recurring length concept
- Using Fermat's little theorem
- Using vedic mathematics
To know more, read my Modern approach to speed math secret. This book explores the unique secret behind speed math, Booths multiplication etc.
It explains whole speed math using Zero.
edited Oct 4 '16 at 9:58
Community♦
1
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
$endgroup$
add a comment |
$begingroup$
General approach
For divisibility test by odd divisor except ending with 5:
first find multiple of number in the form of $10^n-1$ or $10^n +1$
Now compute remainder by $10^n-1$ or $10^n +1$ which is easy to compute
If this remainder is exactly divisible, then the original number is divisible.
Example
$7 | N$ if and only if $7 | (N % 1001)$
i.e. $N % 7 = (N % 1001) % 7 $
Similarly, $N % 13 = (N % 1001) % 13$.
Cross divisibility test
(VJ's universal divisibility test)
- $7 | 10 T + U$ if and only if $7 | (1T-2U)$, or
- $7 | 10 T + U$ if and only if $7 | (2T+3U)$, or
$7 | 10 T + U$ if and only if $7 | (T+5U)$ etc.
$13 | 10 T + U$ if and only if $13 | (3T-U)$, or
- $13 | 10 T + U$ if and only if $13 | (2T-5U)$, or
- $13 | 10 T + U$ if and only if $13 | (T+4U)$, or
- $13 | 1000 T + U$ if and only if $13 |(T-U)$ etc.
In short, there are many approaches to check divisibility test by number.
You can also check divisibility
- Using least Recurring length concept
- Using Fermat's little theorem
- Using vedic mathematics
To know more, read my Modern approach to speed math secret. This book explores the unique secret behind speed math, Booths multiplication etc.
It explains whole speed math using Zero.
edited Oct 4 '16 at 9:58
Community♦
1
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
$endgroup$
General approach
For divisibility test by odd divisor except ending with 5:
first find multiple of number in the form of $10^n-1$ or $10^n +1$
Now compute remainder by $10^n-1$ or $10^n +1$ which is easy to compute
If this remainder is exactly divisible, then the original number is divisible.
Example
$7 | N$ if and only if $7 | (N % 1001)$
i.e. $N % 7 = (N % 1001) % 7 $
Similarly, $N % 13 = (N % 1001) % 13$.
Cross divisibility test
(VJ's universal divisibility test)
- $7 | 10 T + U$ if and only if $7 | (1T-2U)$, or
- $7 | 10 T + U$ if and only if $7 | (2T+3U)$, or
$7 | 10 T + U$ if and only if $7 | (T+5U)$ etc.
$13 | 10 T + U$ if and only if $13 | (3T-U)$, or
- $13 | 10 T + U$ if and only if $13 | (2T-5U)$, or
- $13 | 10 T + U$ if and only if $13 | (T+4U)$, or
- $13 | 1000 T + U$ if and only if $13 |(T-U)$ etc.
In short, there are many approaches to check divisibility test by number.
You can also check divisibility
- Using least Recurring length concept
- Using Fermat's little theorem
- Using vedic mathematics
To know more, read my Modern approach to speed math secret. This book explores the unique secret behind speed math, Booths multiplication etc.
It explains whole speed math using Zero.
edited Oct 4 '16 at 9:58
Community♦
1
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
edited Oct 4 '16 at 9:58
Community♦
1
edited Oct 4 '16 at 9:58
Community♦
1
edited Oct 4 '16 at 9:58
Community♦
1
1
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
answered Jul 6 '13 at 13:14
Vitthal JadhavVitthal Jadhav
195
195
add a comment |
add a comment |
$begingroup$
Let $n=text{'abcdef'}=10^5a+10^4b+10^3c+10^2d+10e+f$. Using modular arithmetic,
$$nequiv 5a+4b+6c+2d+3e+fmod 7.$$
As $10^6bmod7=1$, this repeats for the next groups of $6$ digits.
To get smaller coefficients, you can reduce some of them by $-7$, giving
$$nequiv (f-c)+2(d-a)+3(e-b)mod 7.$$
For instance
$$123456equiv (6-3)+2(4-1)+3(5-2)equiv18mod7$$ isn't divisible by $7$.
You can generalize the method to other divisors.
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
$endgroup$
add a comment |
$begingroup$
Let $n=text{'abcdef'}=10^5a+10^4b+10^3c+10^2d+10e+f$. Using modular arithmetic,
$$nequiv 5a+4b+6c+2d+3e+fmod 7.$$
As $10^6bmod7=1$, this repeats for the next groups of $6$ digits.
To get smaller coefficients, you can reduce some of them by $-7$, giving
$$nequiv (f-c)+2(d-a)+3(e-b)mod 7.$$
For instance
$$123456equiv (6-3)+2(4-1)+3(5-2)equiv18mod7$$ isn't divisible by $7$.
You can generalize the method to other divisors.
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
$endgroup$
add a comment |
$begingroup$
Let $n=text{'abcdef'}=10^5a+10^4b+10^3c+10^2d+10e+f$. Using modular arithmetic,
$$nequiv 5a+4b+6c+2d+3e+fmod 7.$$
As $10^6bmod7=1$, this repeats for the next groups of $6$ digits.
To get smaller coefficients, you can reduce some of them by $-7$, giving
$$nequiv (f-c)+2(d-a)+3(e-b)mod 7.$$
For instance
$$123456equiv (6-3)+2(4-1)+3(5-2)equiv18mod7$$ isn't divisible by $7$.
You can generalize the method to other divisors.
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
$endgroup$
Let $n=text{'abcdef'}=10^5a+10^4b+10^3c+10^2d+10e+f$. Using modular arithmetic,
$$nequiv 5a+4b+6c+2d+3e+fmod 7.$$
As $10^6bmod7=1$, this repeats for the next groups of $6$ digits.
To get smaller coefficients, you can reduce some of them by $-7$, giving
$$nequiv (f-c)+2(d-a)+3(e-b)mod 7.$$
For instance
$$123456equiv (6-3)+2(4-1)+3(5-2)equiv18mod7$$ isn't divisible by $7$.
You can generalize the method to other divisors.
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
edited Oct 4 '16 at 11:03
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
answered Oct 4 '16 at 10:14
Yves DaoustYves Daoust
131k676229
131k676229
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f328562%2fdivisibility-criteria-for-7-11-13-17-19%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
8
$begingroup$
You may want to look at this. There are many other accessible sources.
$endgroup$
– André Nicolas
Mar 12 '13 at 16:18
4
$begingroup$
I think it's worth noting that since $7cdot11cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits.
$endgroup$
– Harald Hanche-Olsen
Mar 12 '13 at 17:02
$begingroup$
A cheap answer
$endgroup$
– Antonio Hernandez Maquivar
Oct 4 '16 at 10:53