Mixing
Show that among any consecutive $16$ natural numbers one is coprime to all others
$begingroup$
Show that among any consecutive $16$ natural numbers one is coprime to all others.
Is it useful to use the division algorithm on $16$?
$16k,16k+1,16k+2,...16k+15$
elementary-number-theory divisibility
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
$endgroup$
|
show 4 more comments
$begingroup$
Show that among any consecutive $16$ natural numbers one is coprime to all others.
Is it useful to use the division algorithm on $16$?
$16k,16k+1,16k+2,...16k+15$
elementary-number-theory divisibility
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
$endgroup$
3
$begingroup$
See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
$endgroup$
– Starfall
May 11 '16 at 14:26
1
$begingroup$
@HamidRezaEbrahimi modulo $30$ is used because $2cdot 3cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$.
$endgroup$
– Hagen von Eitzen
May 11 '16 at 14:59
2
$begingroup$
The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7.
$endgroup$
– almagest
May 11 '16 at 15:40
1
$begingroup$
A deceptively simple question.
$endgroup$
– Mr. Brooks
May 11 '16 at 21:16
1
$begingroup$
I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291.
$endgroup$
– Robert Soupe
May 12 '16 at 5:08
|
show 4 more comments
$begingroup$
Show that among any consecutive $16$ natural numbers one is coprime to all others.
Is it useful to use the division algorithm on $16$?
$16k,16k+1,16k+2,...16k+15$
elementary-number-theory divisibility
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
$endgroup$
Show that among any consecutive $16$ natural numbers one is coprime to all others.
Is it useful to use the division algorithm on $16$?
$16k,16k+1,16k+2,...16k+15$
elementary-number-theory divisibility
elementary-number-theory divisibility
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
asked May 11 '16 at 14:17
Hamid Reza EbrahimiHamid Reza Ebrahimi
1,701620
1,701620
3
$begingroup$
See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
$endgroup$
– Starfall
May 11 '16 at 14:26
1
$begingroup$
@HamidRezaEbrahimi modulo $30$ is used because $2cdot 3cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$.
$endgroup$
– Hagen von Eitzen
May 11 '16 at 14:59
2
$begingroup$
The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7.
$endgroup$
– almagest
May 11 '16 at 15:40
1
$begingroup$
A deceptively simple question.
$endgroup$
– Mr. Brooks
May 11 '16 at 21:16
1
$begingroup$
I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291.
$endgroup$
– Robert Soupe
May 12 '16 at 5:08
|
show 4 more comments
3
$begingroup$
See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
$endgroup$
– Starfall
May 11 '16 at 14:26
1
$begingroup$
@HamidRezaEbrahimi modulo $30$ is used because $2cdot 3cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$.
$endgroup$
– Hagen von Eitzen
May 11 '16 at 14:59
2
$begingroup$
The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7.
$endgroup$
– almagest
May 11 '16 at 15:40
1
$begingroup$
A deceptively simple question.
$endgroup$
– Mr. Brooks
May 11 '16 at 21:16
1
$begingroup$
I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291.
$endgroup$
– Robert Soupe
May 12 '16 at 5:08
3
3
$begingroup$
See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
$endgroup$
– Starfall
May 11 '16 at 14:26
$begingroup$
See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
$endgroup$
– Starfall
May 11 '16 at 14:26
1
1
$begingroup$
@HamidRezaEbrahimi modulo $30$ is used because $2cdot 3cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$.
$endgroup$
– Hagen von Eitzen
May 11 '16 at 14:59
$begingroup$
@HamidRezaEbrahimi modulo $30$ is used because $2cdot 3cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$.
$endgroup$
– Hagen von Eitzen
May 11 '16 at 14:59
2
2
$begingroup$
The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7.
$endgroup$
– almagest
May 11 '16 at 15:40
$begingroup$
The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7.
$endgroup$
– almagest
May 11 '16 at 15:40
1
1
$begingroup$
A deceptively simple question.
$endgroup$
– Mr. Brooks
May 11 '16 at 21:16
$begingroup$
A deceptively simple question.
$endgroup$
– Mr. Brooks
May 11 '16 at 21:16
1
1
$begingroup$
I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291.
$endgroup$
– Robert Soupe
May 12 '16 at 5:08
$begingroup$
I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291.
$endgroup$
– Robert Soupe
May 12 '16 at 5:08
|
show 4 more comments
2 Answers
2
active
oldest
votes
$begingroup$
First off, you should observe that since any two numbers in the sequence differ by at most 15, any common factor is at most 15. Therefore, any number not coprime to the others is divisible by one of the primes 2,3,5,7,11,13.
Now if a number $x$ in the sequence is divisible by $p = 2, 3, $ or $7$, then it cannot be coprime to the others, since in that case either $x-p$ or $x+p$ must also lie in the sequence. (If $x-p$ is not in the sequence, then the first element is at least $x-p+1$, so the last element is at least $x-p+16 > x+p$.)
Therefore, $x$ is a desired coprime element if and only if the following conditions are all satisfied:
- $x$ is not divisible by 2, 3, 5, or 7.
- If $x$ is divisible by 11, then $x-11$ and $x+11$ are not in the sequence.
- If $x$ is by 13, then $x-13$ and $x+13$ are not in the sequence.
We consider the congruence classes modulo 30. Of these, the set $S = {1, 7, 11, 13, 17, 19, 23, 29}$ represent elements divisible by neither 2 nor 3 nor 5. Now we must consider each possible set of sixteen consecutive residues and argue that there are enough elements of $S$ that at least one of them satisfies our conditions for being coprime.
In particular we will note that it is sufficient (although not quite necessary) to find an element in the sequence from $S$ that is coprime to 7, 11, 13.
Note that in such a sequence there can be only one element from a residue class in $S$ divisible by 11, and likewise only one element from a residue class in $S$ divisible by 13. There might be two divisible by 7, since that only requires a difference of 14, which happens in three cases:
- When the sequence has elements of form $30k+17$ and $30(k+1) +1$
- When the sequence has elements of form $30k+23$ and $30(k+1) +7$
- When the sequence has elements of form $30k+29$ and $30(k+1) +13$
We consider which residue appears first in the sequence. (I would be happy to avoid covering cases explicitly like this but it seems necessary to the argument, and the last two cases are finicky.)
- If the first element from $S$ is of form $30k+1$, then the first element overall is $30k$ or greater. This means that $30k+1, 30k+7, 30k+11, 30k+13$ are all in the sequence. At most one of these four elements is divisible by 11, at most one is divisible by 13, and by above at most one is divisible by 7. Thus, one of them is coprime to all elements in the sequence, as desired.
- If the first element from $S$ is of form $30k+7$, then the first element is at least $30k+2$ and thus the sequence contains $30k+7, 30k+11, 30k+13, 30k+17$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+11$ or $30k+13$, then the first element is at least $30k+8$ and thus the sequence contains $30k+13, 30k+17, 30k+19,30k+23$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+17$, then by the same reasoning the sequence contains the elements $30k+17, 30k+19,30k+23, 30k+29$, of which at least one is coprime as desired.
- If the first element from $S$ is of form $30k+19$, then the sequence contains the elements $30k+19,30k+23, 30k+29, 30(k+1) + 1$ and the argument is the same.
- If the first element from $S$ is of form $30k+23$, then the sequence contains the elements $30k+23, 30k+29, 30(k+1) + 1$. At this point we need to be more careful, since one each of these three could very well be divisible by 7,11,13. However in this case note that $30k+29 pm 11$ and $30k+29 pm 13$ all lie outside the bounds of the sequence (the first element lies in the range $[30k+20, 30k+23]$ and the last element lies in the range $[30(k+1)+5,30(k+1)+8]$). Thus for this element to be not coprime it must be the one divisible by 7. If we try to force $x = 30(k+1) + 1$, to not be coprime, we examine the elements $x pm 11, x pm 13$. Of these, only $x-11 = 30k+20$ is possibly in the sequence, which would therefore be the range $[30k+20,30(k+1)+5]$. In that case, we see that $(30k+23)$ might be divisible by 13, but then $(30k+23)pm 13$ lie outside the sequence, so that $30k+23$ must be coprime after all.
- If the first element from $S$ is of form $30k+29$, then the sequence contains the elements $30k+29, 30(k+1) + 1, 30(k+1)+7$. If $30(k+1)+11$ lies in the sequence we have four elements from $S$ with at least one of them coprime to 7,11,13, as desired. Thus, we restrict ourselves to when the first element is either $30k+24$ or $30k+25$ and the last element is either $30(k+1)+9$ or $30(k+1)+10$.
Again, we see that the three elements $30k+29, 30(k+1) + 1, 30(k+1)+7$ might each be divisible by one of 7,11,13. Since $30(k+1) + 1 pm 11$ and $30(k+1) + 1 pm 13$ lie outside the sequence's range, $30(k+1) + 1$ is coprime unless it is the one divisible by 7. Then if we examine $x = 30k+29$, of the values $xpm 11, x pm 13$ only $x+11$ is possibly in the sequence, which must be $[30k+25, 30(k+1)+10]$. But then $30(k+1)+7pm 13$ both lie outside the sequence. We are done by the same reasoning as the previous case.
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
$endgroup$
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
add a comment |
$begingroup$
Theorem. (S. S. Pillai) For $minmathbb N$ the following statements are equivalent:
(1) there is a set of $m$ consecutive integers, none of which is relatively prime to all the others;
(2) $mge17$.
The smallest example of a set as in (1) is ${2184,2185,dots,2200}$.
S. S. Pillai, On $m$ consecutive integers—III, Proc. Indian Acad. Sci. 13 (1941), 530–533.
Irene Gassko, Stapled sequences and stapling coverings of natural numbers, Electronic Journal of Combinatorics, Volume 3, Issue 1, 1996.
answered Jan 20 at 17:28
bofbof
52.3k558121
$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%2f1780933%2fshow-that-among-any-consecutive-16-natural-numbers-one-is-coprime-to-all-other%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First off, you should observe that since any two numbers in the sequence differ by at most 15, any common factor is at most 15. Therefore, any number not coprime to the others is divisible by one of the primes 2,3,5,7,11,13.
Now if a number $x$ in the sequence is divisible by $p = 2, 3, $ or $7$, then it cannot be coprime to the others, since in that case either $x-p$ or $x+p$ must also lie in the sequence. (If $x-p$ is not in the sequence, then the first element is at least $x-p+1$, so the last element is at least $x-p+16 > x+p$.)
Therefore, $x$ is a desired coprime element if and only if the following conditions are all satisfied:
- $x$ is not divisible by 2, 3, 5, or 7.
- If $x$ is divisible by 11, then $x-11$ and $x+11$ are not in the sequence.
- If $x$ is by 13, then $x-13$ and $x+13$ are not in the sequence.
We consider the congruence classes modulo 30. Of these, the set $S = {1, 7, 11, 13, 17, 19, 23, 29}$ represent elements divisible by neither 2 nor 3 nor 5. Now we must consider each possible set of sixteen consecutive residues and argue that there are enough elements of $S$ that at least one of them satisfies our conditions for being coprime.
In particular we will note that it is sufficient (although not quite necessary) to find an element in the sequence from $S$ that is coprime to 7, 11, 13.
Note that in such a sequence there can be only one element from a residue class in $S$ divisible by 11, and likewise only one element from a residue class in $S$ divisible by 13. There might be two divisible by 7, since that only requires a difference of 14, which happens in three cases:
- When the sequence has elements of form $30k+17$ and $30(k+1) +1$
- When the sequence has elements of form $30k+23$ and $30(k+1) +7$
- When the sequence has elements of form $30k+29$ and $30(k+1) +13$
We consider which residue appears first in the sequence. (I would be happy to avoid covering cases explicitly like this but it seems necessary to the argument, and the last two cases are finicky.)
- If the first element from $S$ is of form $30k+1$, then the first element overall is $30k$ or greater. This means that $30k+1, 30k+7, 30k+11, 30k+13$ are all in the sequence. At most one of these four elements is divisible by 11, at most one is divisible by 13, and by above at most one is divisible by 7. Thus, one of them is coprime to all elements in the sequence, as desired.
- If the first element from $S$ is of form $30k+7$, then the first element is at least $30k+2$ and thus the sequence contains $30k+7, 30k+11, 30k+13, 30k+17$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+11$ or $30k+13$, then the first element is at least $30k+8$ and thus the sequence contains $30k+13, 30k+17, 30k+19,30k+23$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+17$, then by the same reasoning the sequence contains the elements $30k+17, 30k+19,30k+23, 30k+29$, of which at least one is coprime as desired.
- If the first element from $S$ is of form $30k+19$, then the sequence contains the elements $30k+19,30k+23, 30k+29, 30(k+1) + 1$ and the argument is the same.
- If the first element from $S$ is of form $30k+23$, then the sequence contains the elements $30k+23, 30k+29, 30(k+1) + 1$. At this point we need to be more careful, since one each of these three could very well be divisible by 7,11,13. However in this case note that $30k+29 pm 11$ and $30k+29 pm 13$ all lie outside the bounds of the sequence (the first element lies in the range $[30k+20, 30k+23]$ and the last element lies in the range $[30(k+1)+5,30(k+1)+8]$). Thus for this element to be not coprime it must be the one divisible by 7. If we try to force $x = 30(k+1) + 1$, to not be coprime, we examine the elements $x pm 11, x pm 13$. Of these, only $x-11 = 30k+20$ is possibly in the sequence, which would therefore be the range $[30k+20,30(k+1)+5]$. In that case, we see that $(30k+23)$ might be divisible by 13, but then $(30k+23)pm 13$ lie outside the sequence, so that $30k+23$ must be coprime after all.
- If the first element from $S$ is of form $30k+29$, then the sequence contains the elements $30k+29, 30(k+1) + 1, 30(k+1)+7$. If $30(k+1)+11$ lies in the sequence we have four elements from $S$ with at least one of them coprime to 7,11,13, as desired. Thus, we restrict ourselves to when the first element is either $30k+24$ or $30k+25$ and the last element is either $30(k+1)+9$ or $30(k+1)+10$.
Again, we see that the three elements $30k+29, 30(k+1) + 1, 30(k+1)+7$ might each be divisible by one of 7,11,13. Since $30(k+1) + 1 pm 11$ and $30(k+1) + 1 pm 13$ lie outside the sequence's range, $30(k+1) + 1$ is coprime unless it is the one divisible by 7. Then if we examine $x = 30k+29$, of the values $xpm 11, x pm 13$ only $x+11$ is possibly in the sequence, which must be $[30k+25, 30(k+1)+10]$. But then $30(k+1)+7pm 13$ both lie outside the sequence. We are done by the same reasoning as the previous case.
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
$endgroup$
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
add a comment |
$begingroup$
First off, you should observe that since any two numbers in the sequence differ by at most 15, any common factor is at most 15. Therefore, any number not coprime to the others is divisible by one of the primes 2,3,5,7,11,13.
Now if a number $x$ in the sequence is divisible by $p = 2, 3, $ or $7$, then it cannot be coprime to the others, since in that case either $x-p$ or $x+p$ must also lie in the sequence. (If $x-p$ is not in the sequence, then the first element is at least $x-p+1$, so the last element is at least $x-p+16 > x+p$.)
Therefore, $x$ is a desired coprime element if and only if the following conditions are all satisfied:
- $x$ is not divisible by 2, 3, 5, or 7.
- If $x$ is divisible by 11, then $x-11$ and $x+11$ are not in the sequence.
- If $x$ is by 13, then $x-13$ and $x+13$ are not in the sequence.
We consider the congruence classes modulo 30. Of these, the set $S = {1, 7, 11, 13, 17, 19, 23, 29}$ represent elements divisible by neither 2 nor 3 nor 5. Now we must consider each possible set of sixteen consecutive residues and argue that there are enough elements of $S$ that at least one of them satisfies our conditions for being coprime.
In particular we will note that it is sufficient (although not quite necessary) to find an element in the sequence from $S$ that is coprime to 7, 11, 13.
Note that in such a sequence there can be only one element from a residue class in $S$ divisible by 11, and likewise only one element from a residue class in $S$ divisible by 13. There might be two divisible by 7, since that only requires a difference of 14, which happens in three cases:
- When the sequence has elements of form $30k+17$ and $30(k+1) +1$
- When the sequence has elements of form $30k+23$ and $30(k+1) +7$
- When the sequence has elements of form $30k+29$ and $30(k+1) +13$
We consider which residue appears first in the sequence. (I would be happy to avoid covering cases explicitly like this but it seems necessary to the argument, and the last two cases are finicky.)
- If the first element from $S$ is of form $30k+1$, then the first element overall is $30k$ or greater. This means that $30k+1, 30k+7, 30k+11, 30k+13$ are all in the sequence. At most one of these four elements is divisible by 11, at most one is divisible by 13, and by above at most one is divisible by 7. Thus, one of them is coprime to all elements in the sequence, as desired.
- If the first element from $S$ is of form $30k+7$, then the first element is at least $30k+2$ and thus the sequence contains $30k+7, 30k+11, 30k+13, 30k+17$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+11$ or $30k+13$, then the first element is at least $30k+8$ and thus the sequence contains $30k+13, 30k+17, 30k+19,30k+23$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+17$, then by the same reasoning the sequence contains the elements $30k+17, 30k+19,30k+23, 30k+29$, of which at least one is coprime as desired.
- If the first element from $S$ is of form $30k+19$, then the sequence contains the elements $30k+19,30k+23, 30k+29, 30(k+1) + 1$ and the argument is the same.
- If the first element from $S$ is of form $30k+23$, then the sequence contains the elements $30k+23, 30k+29, 30(k+1) + 1$. At this point we need to be more careful, since one each of these three could very well be divisible by 7,11,13. However in this case note that $30k+29 pm 11$ and $30k+29 pm 13$ all lie outside the bounds of the sequence (the first element lies in the range $[30k+20, 30k+23]$ and the last element lies in the range $[30(k+1)+5,30(k+1)+8]$). Thus for this element to be not coprime it must be the one divisible by 7. If we try to force $x = 30(k+1) + 1$, to not be coprime, we examine the elements $x pm 11, x pm 13$. Of these, only $x-11 = 30k+20$ is possibly in the sequence, which would therefore be the range $[30k+20,30(k+1)+5]$. In that case, we see that $(30k+23)$ might be divisible by 13, but then $(30k+23)pm 13$ lie outside the sequence, so that $30k+23$ must be coprime after all.
- If the first element from $S$ is of form $30k+29$, then the sequence contains the elements $30k+29, 30(k+1) + 1, 30(k+1)+7$. If $30(k+1)+11$ lies in the sequence we have four elements from $S$ with at least one of them coprime to 7,11,13, as desired. Thus, we restrict ourselves to when the first element is either $30k+24$ or $30k+25$ and the last element is either $30(k+1)+9$ or $30(k+1)+10$.
Again, we see that the three elements $30k+29, 30(k+1) + 1, 30(k+1)+7$ might each be divisible by one of 7,11,13. Since $30(k+1) + 1 pm 11$ and $30(k+1) + 1 pm 13$ lie outside the sequence's range, $30(k+1) + 1$ is coprime unless it is the one divisible by 7. Then if we examine $x = 30k+29$, of the values $xpm 11, x pm 13$ only $x+11$ is possibly in the sequence, which must be $[30k+25, 30(k+1)+10]$. But then $30(k+1)+7pm 13$ both lie outside the sequence. We are done by the same reasoning as the previous case.
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
$endgroup$
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
add a comment |
$begingroup$
First off, you should observe that since any two numbers in the sequence differ by at most 15, any common factor is at most 15. Therefore, any number not coprime to the others is divisible by one of the primes 2,3,5,7,11,13.
Now if a number $x$ in the sequence is divisible by $p = 2, 3, $ or $7$, then it cannot be coprime to the others, since in that case either $x-p$ or $x+p$ must also lie in the sequence. (If $x-p$ is not in the sequence, then the first element is at least $x-p+1$, so the last element is at least $x-p+16 > x+p$.)
Therefore, $x$ is a desired coprime element if and only if the following conditions are all satisfied:
- $x$ is not divisible by 2, 3, 5, or 7.
- If $x$ is divisible by 11, then $x-11$ and $x+11$ are not in the sequence.
- If $x$ is by 13, then $x-13$ and $x+13$ are not in the sequence.
We consider the congruence classes modulo 30. Of these, the set $S = {1, 7, 11, 13, 17, 19, 23, 29}$ represent elements divisible by neither 2 nor 3 nor 5. Now we must consider each possible set of sixteen consecutive residues and argue that there are enough elements of $S$ that at least one of them satisfies our conditions for being coprime.
In particular we will note that it is sufficient (although not quite necessary) to find an element in the sequence from $S$ that is coprime to 7, 11, 13.
Note that in such a sequence there can be only one element from a residue class in $S$ divisible by 11, and likewise only one element from a residue class in $S$ divisible by 13. There might be two divisible by 7, since that only requires a difference of 14, which happens in three cases:
- When the sequence has elements of form $30k+17$ and $30(k+1) +1$
- When the sequence has elements of form $30k+23$ and $30(k+1) +7$
- When the sequence has elements of form $30k+29$ and $30(k+1) +13$
We consider which residue appears first in the sequence. (I would be happy to avoid covering cases explicitly like this but it seems necessary to the argument, and the last two cases are finicky.)
- If the first element from $S$ is of form $30k+1$, then the first element overall is $30k$ or greater. This means that $30k+1, 30k+7, 30k+11, 30k+13$ are all in the sequence. At most one of these four elements is divisible by 11, at most one is divisible by 13, and by above at most one is divisible by 7. Thus, one of them is coprime to all elements in the sequence, as desired.
- If the first element from $S$ is of form $30k+7$, then the first element is at least $30k+2$ and thus the sequence contains $30k+7, 30k+11, 30k+13, 30k+17$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+11$ or $30k+13$, then the first element is at least $30k+8$ and thus the sequence contains $30k+13, 30k+17, 30k+19,30k+23$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+17$, then by the same reasoning the sequence contains the elements $30k+17, 30k+19,30k+23, 30k+29$, of which at least one is coprime as desired.
- If the first element from $S$ is of form $30k+19$, then the sequence contains the elements $30k+19,30k+23, 30k+29, 30(k+1) + 1$ and the argument is the same.
- If the first element from $S$ is of form $30k+23$, then the sequence contains the elements $30k+23, 30k+29, 30(k+1) + 1$. At this point we need to be more careful, since one each of these three could very well be divisible by 7,11,13. However in this case note that $30k+29 pm 11$ and $30k+29 pm 13$ all lie outside the bounds of the sequence (the first element lies in the range $[30k+20, 30k+23]$ and the last element lies in the range $[30(k+1)+5,30(k+1)+8]$). Thus for this element to be not coprime it must be the one divisible by 7. If we try to force $x = 30(k+1) + 1$, to not be coprime, we examine the elements $x pm 11, x pm 13$. Of these, only $x-11 = 30k+20$ is possibly in the sequence, which would therefore be the range $[30k+20,30(k+1)+5]$. In that case, we see that $(30k+23)$ might be divisible by 13, but then $(30k+23)pm 13$ lie outside the sequence, so that $30k+23$ must be coprime after all.
- If the first element from $S$ is of form $30k+29$, then the sequence contains the elements $30k+29, 30(k+1) + 1, 30(k+1)+7$. If $30(k+1)+11$ lies in the sequence we have four elements from $S$ with at least one of them coprime to 7,11,13, as desired. Thus, we restrict ourselves to when the first element is either $30k+24$ or $30k+25$ and the last element is either $30(k+1)+9$ or $30(k+1)+10$.
Again, we see that the three elements $30k+29, 30(k+1) + 1, 30(k+1)+7$ might each be divisible by one of 7,11,13. Since $30(k+1) + 1 pm 11$ and $30(k+1) + 1 pm 13$ lie outside the sequence's range, $30(k+1) + 1$ is coprime unless it is the one divisible by 7. Then if we examine $x = 30k+29$, of the values $xpm 11, x pm 13$ only $x+11$ is possibly in the sequence, which must be $[30k+25, 30(k+1)+10]$. But then $30(k+1)+7pm 13$ both lie outside the sequence. We are done by the same reasoning as the previous case.
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
$endgroup$
First off, you should observe that since any two numbers in the sequence differ by at most 15, any common factor is at most 15. Therefore, any number not coprime to the others is divisible by one of the primes 2,3,5,7,11,13.
Now if a number $x$ in the sequence is divisible by $p = 2, 3, $ or $7$, then it cannot be coprime to the others, since in that case either $x-p$ or $x+p$ must also lie in the sequence. (If $x-p$ is not in the sequence, then the first element is at least $x-p+1$, so the last element is at least $x-p+16 > x+p$.)
Therefore, $x$ is a desired coprime element if and only if the following conditions are all satisfied:
- $x$ is not divisible by 2, 3, 5, or 7.
- If $x$ is divisible by 11, then $x-11$ and $x+11$ are not in the sequence.
- If $x$ is by 13, then $x-13$ and $x+13$ are not in the sequence.
We consider the congruence classes modulo 30. Of these, the set $S = {1, 7, 11, 13, 17, 19, 23, 29}$ represent elements divisible by neither 2 nor 3 nor 5. Now we must consider each possible set of sixteen consecutive residues and argue that there are enough elements of $S$ that at least one of them satisfies our conditions for being coprime.
In particular we will note that it is sufficient (although not quite necessary) to find an element in the sequence from $S$ that is coprime to 7, 11, 13.
Note that in such a sequence there can be only one element from a residue class in $S$ divisible by 11, and likewise only one element from a residue class in $S$ divisible by 13. There might be two divisible by 7, since that only requires a difference of 14, which happens in three cases:
- When the sequence has elements of form $30k+17$ and $30(k+1) +1$
- When the sequence has elements of form $30k+23$ and $30(k+1) +7$
- When the sequence has elements of form $30k+29$ and $30(k+1) +13$
We consider which residue appears first in the sequence. (I would be happy to avoid covering cases explicitly like this but it seems necessary to the argument, and the last two cases are finicky.)
- If the first element from $S$ is of form $30k+1$, then the first element overall is $30k$ or greater. This means that $30k+1, 30k+7, 30k+11, 30k+13$ are all in the sequence. At most one of these four elements is divisible by 11, at most one is divisible by 13, and by above at most one is divisible by 7. Thus, one of them is coprime to all elements in the sequence, as desired.
- If the first element from $S$ is of form $30k+7$, then the first element is at least $30k+2$ and thus the sequence contains $30k+7, 30k+11, 30k+13, 30k+17$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+11$ or $30k+13$, then the first element is at least $30k+8$ and thus the sequence contains $30k+13, 30k+17, 30k+19,30k+23$. Again one of these is again divisible by neither 7, 11, nor 13.
- If the first element from $S$ is of form $30k+17$, then by the same reasoning the sequence contains the elements $30k+17, 30k+19,30k+23, 30k+29$, of which at least one is coprime as desired.
- If the first element from $S$ is of form $30k+19$, then the sequence contains the elements $30k+19,30k+23, 30k+29, 30(k+1) + 1$ and the argument is the same.
- If the first element from $S$ is of form $30k+23$, then the sequence contains the elements $30k+23, 30k+29, 30(k+1) + 1$. At this point we need to be more careful, since one each of these three could very well be divisible by 7,11,13. However in this case note that $30k+29 pm 11$ and $30k+29 pm 13$ all lie outside the bounds of the sequence (the first element lies in the range $[30k+20, 30k+23]$ and the last element lies in the range $[30(k+1)+5,30(k+1)+8]$). Thus for this element to be not coprime it must be the one divisible by 7. If we try to force $x = 30(k+1) + 1$, to not be coprime, we examine the elements $x pm 11, x pm 13$. Of these, only $x-11 = 30k+20$ is possibly in the sequence, which would therefore be the range $[30k+20,30(k+1)+5]$. In that case, we see that $(30k+23)$ might be divisible by 13, but then $(30k+23)pm 13$ lie outside the sequence, so that $30k+23$ must be coprime after all.
- If the first element from $S$ is of form $30k+29$, then the sequence contains the elements $30k+29, 30(k+1) + 1, 30(k+1)+7$. If $30(k+1)+11$ lies in the sequence we have four elements from $S$ with at least one of them coprime to 7,11,13, as desired. Thus, we restrict ourselves to when the first element is either $30k+24$ or $30k+25$ and the last element is either $30(k+1)+9$ or $30(k+1)+10$.
Again, we see that the three elements $30k+29, 30(k+1) + 1, 30(k+1)+7$ might each be divisible by one of 7,11,13. Since $30(k+1) + 1 pm 11$ and $30(k+1) + 1 pm 13$ lie outside the sequence's range, $30(k+1) + 1$ is coprime unless it is the one divisible by 7. Then if we examine $x = 30k+29$, of the values $xpm 11, x pm 13$ only $x+11$ is possibly in the sequence, which must be $[30k+25, 30(k+1)+10]$. But then $30(k+1)+7pm 13$ both lie outside the sequence. We are done by the same reasoning as the previous case.
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
answered May 12 '16 at 5:46
Rolf HoyerRolf Hoyer
11.3k31629
11.3k31629
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
add a comment |
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
My answer is quite long-winded as it stands, but I do want to note that careful examination of the finicky cases allow one to construct a sequence of seventeen consecutive integers with each element sharing a prime factor with another in the sequence.
$endgroup$
– Rolf Hoyer
May 12 '16 at 6:04
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
$begingroup$
I feel there must be a shorter answer to this question.However I appreciate your answer.
$endgroup$
– Hamid Reza Ebrahimi
May 12 '16 at 12:53
add a comment |
$begingroup$
Theorem. (S. S. Pillai) For $minmathbb N$ the following statements are equivalent:
(1) there is a set of $m$ consecutive integers, none of which is relatively prime to all the others;
(2) $mge17$.
The smallest example of a set as in (1) is ${2184,2185,dots,2200}$.
S. S. Pillai, On $m$ consecutive integers—III, Proc. Indian Acad. Sci. 13 (1941), 530–533.
Irene Gassko, Stapled sequences and stapling coverings of natural numbers, Electronic Journal of Combinatorics, Volume 3, Issue 1, 1996.
answered Jan 20 at 17:28
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
Theorem. (S. S. Pillai) For $minmathbb N$ the following statements are equivalent:
(1) there is a set of $m$ consecutive integers, none of which is relatively prime to all the others;
(2) $mge17$.
The smallest example of a set as in (1) is ${2184,2185,dots,2200}$.
S. S. Pillai, On $m$ consecutive integers—III, Proc. Indian Acad. Sci. 13 (1941), 530–533.
Irene Gassko, Stapled sequences and stapling coverings of natural numbers, Electronic Journal of Combinatorics, Volume 3, Issue 1, 1996.
answered Jan 20 at 17:28
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
Theorem. (S. S. Pillai) For $minmathbb N$ the following statements are equivalent:
(1) there is a set of $m$ consecutive integers, none of which is relatively prime to all the others;
(2) $mge17$.
The smallest example of a set as in (1) is ${2184,2185,dots,2200}$.
S. S. Pillai, On $m$ consecutive integers—III, Proc. Indian Acad. Sci. 13 (1941), 530–533.
Irene Gassko, Stapled sequences and stapling coverings of natural numbers, Electronic Journal of Combinatorics, Volume 3, Issue 1, 1996.
answered Jan 20 at 17:28
bofbof
52.3k558121
$endgroup$
Theorem. (S. S. Pillai) For $minmathbb N$ the following statements are equivalent:
(1) there is a set of $m$ consecutive integers, none of which is relatively prime to all the others;
(2) $mge17$.
The smallest example of a set as in (1) is ${2184,2185,dots,2200}$.
S. S. Pillai, On $m$ consecutive integers—III, Proc. Indian Acad. Sci. 13 (1941), 530–533.
Irene Gassko, Stapled sequences and stapling coverings of natural numbers, Electronic Journal of Combinatorics, Volume 3, Issue 1, 1996.
answered Jan 20 at 17:28
bofbof
52.3k558121
edited Jan 21 at 0:47
answered Jan 20 at 17:28
bofbof
52.3k558121
answered Jan 20 at 17:28
bofbof
52.3k558121
answered Jan 20 at 17:28
bofbof
52.3k558121
52.3k558121
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%2f1780933%2fshow-that-among-any-consecutive-16-natural-numbers-one-is-coprime-to-all-other%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
3
$begingroup$
See Solution-O51 in projectpen.files.wordpress.com/2009/06/pen-a9-a37-o511.pdf
$endgroup$
– Starfall
May 11 '16 at 14:26
1
$begingroup$
@HamidRezaEbrahimi modulo $30$ is used because $2cdot 3cdot 5=30$, so the numbers congruent to one of $1,7,11,13,17,19,23,29$ are automatically not divisible by $2,3,5$.
$endgroup$
– Hagen von Eitzen
May 11 '16 at 14:59
2
$begingroup$
The proof referenced above is wrong. It claims that if we have 8 consecutive odd numbers, then we can always find one which is not divisible by any of 2, 3, 5, 7, 11 or 13. But we have 20573 divisible by 7, 20575 by 5, 20577 by 3, 20579 by 13, 20581 by 11, 20583 by 3, 20585 by 5 and 20587 by 7.
$endgroup$
– almagest
May 11 '16 at 15:40
1
$begingroup$
A deceptively simple question.
$endgroup$
– Mr. Brooks
May 11 '16 at 21:16
1
$begingroup$
I thought someone else would have mentioned by now that "any consecutive 16 natural numbers" is not quite the same as $16k, 16k + 1, ldots, 16k + 15". For example, compare 273, ..., 288 to 276, ..., 291.
$endgroup$
– Robert Soupe
May 12 '16 at 5:08