Infinite set of positive integers - choose infinitely many to be relative primes or not
$begingroup$
Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes or any two numbers in this subset have a greatest common divisor greater than 1?
There is a beautiful solution for this problem, my teacher told me that it is hard but you don’t have to use anything.
So I am looking for solutions not using well known theorems... thanks!
infinity greatest-common-divisor set-partition
edited Dec 29 '18 at 8:57
bof
52.6k559121
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
$endgroup$
add a comment |
$begingroup$
Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes or any two numbers in this subset have a greatest common divisor greater than 1?
There is a beautiful solution for this problem, my teacher told me that it is hard but you don’t have to use anything.
So I am looking for solutions not using well known theorems... thanks!
infinity greatest-common-divisor set-partition
edited Dec 29 '18 at 8:57
bof
52.6k559121
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
$endgroup$
4
$begingroup$
Hint. Consider two cases. (1) Some prime divides infinitely many members of the set. (2) No prime divides infinitely many members of the set. I don't think I have to say more about case (1). In case (2), construct your subset by choosing one number at a time, so that each number you choose is relatively prime to all of the numbers already chosen.
$endgroup$
– bof
Dec 29 '18 at 9:01
add a comment |
$begingroup$
Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes or any two numbers in this subset have a greatest common divisor greater than 1?
There is a beautiful solution for this problem, my teacher told me that it is hard but you don’t have to use anything.
So I am looking for solutions not using well known theorems... thanks!
infinity greatest-common-divisor set-partition
edited Dec 29 '18 at 8:57
bof
52.6k559121
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
$endgroup$
Given a set of infinitely many positive integers. Is it always possible to find a subset of this set which contains infinitely many numbers such that any two numbers in this subset are relative primes or any two numbers in this subset have a greatest common divisor greater than 1?
There is a beautiful solution for this problem, my teacher told me that it is hard but you don’t have to use anything.
So I am looking for solutions not using well known theorems... thanks!
infinity greatest-common-divisor set-partition
infinity greatest-common-divisor set-partition
edited Dec 29 '18 at 8:57
bof
52.6k559121
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
edited Dec 29 '18 at 8:57
bof
52.6k559121
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
edited Dec 29 '18 at 8:57
bof
52.6k559121
edited Dec 29 '18 at 8:57
bof
52.6k559121
edited Dec 29 '18 at 8:57
bof
52.6k559121
52.6k559121
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
asked Dec 29 '18 at 8:52
Leo GardnerLeo Gardner
499111
499111
4
$begingroup$
Hint. Consider two cases. (1) Some prime divides infinitely many members of the set. (2) No prime divides infinitely many members of the set. I don't think I have to say more about case (1). In case (2), construct your subset by choosing one number at a time, so that each number you choose is relatively prime to all of the numbers already chosen.
$endgroup$
– bof
Dec 29 '18 at 9:01
add a comment |
4
$begingroup$
Hint. Consider two cases. (1) Some prime divides infinitely many members of the set. (2) No prime divides infinitely many members of the set. I don't think I have to say more about case (1). In case (2), construct your subset by choosing one number at a time, so that each number you choose is relatively prime to all of the numbers already chosen.
$endgroup$
– bof
Dec 29 '18 at 9:01
4
4
$begingroup$
Hint. Consider two cases. (1) Some prime divides infinitely many members of the set. (2) No prime divides infinitely many members of the set. I don't think I have to say more about case (1). In case (2), construct your subset by choosing one number at a time, so that each number you choose is relatively prime to all of the numbers already chosen.
$endgroup$
– bof
Dec 29 '18 at 9:01
$begingroup$
Hint. Consider two cases. (1) Some prime divides infinitely many members of the set. (2) No prime divides infinitely many members of the set. I don't think I have to say more about case (1). In case (2), construct your subset by choosing one number at a time, so that each number you choose is relatively prime to all of the numbers already chosen.
$endgroup$
– bof
Dec 29 '18 at 9:01
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This is an application of the infinite Ramsey theorem, see
https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Color a pair blue if they are coprime and red if they are not.
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
$endgroup$
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
add a comment |
Your Answer
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%2f3055662%2finfinite-set-of-positive-integers-choose-infinitely-many-to-be-relative-primes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is an application of the infinite Ramsey theorem, see
https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Color a pair blue if they are coprime and red if they are not.
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
$endgroup$
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
add a comment |
$begingroup$
This is an application of the infinite Ramsey theorem, see
https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Color a pair blue if they are coprime and red if they are not.
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
$endgroup$
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
add a comment |
$begingroup$
This is an application of the infinite Ramsey theorem, see
https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Color a pair blue if they are coprime and red if they are not.
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
$endgroup$
This is an application of the infinite Ramsey theorem, see
https://en.wikipedia.org/wiki/Ramsey%27s_theorem
Color a pair blue if they are coprime and red if they are not.
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
answered Dec 29 '18 at 9:19
A. PongráczA. Pongrácz
6,1171929
6,1171929
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
add a comment |
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
$begingroup$
You used a well known theorem, that’s what I wanted to avoid. But it is a simple beautiful solution anyway, so thanks
$endgroup$
– Leo Gardner
Dec 29 '18 at 10:07
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%2f3055662%2finfinite-set-of-positive-integers-choose-infinitely-many-to-be-relative-primes%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
4
$begingroup$
Hint. Consider two cases. (1) Some prime divides infinitely many members of the set. (2) No prime divides infinitely many members of the set. I don't think I have to say more about case (1). In case (2), construct your subset by choosing one number at a time, so that each number you choose is relatively prime to all of the numbers already chosen.
$endgroup$
– bof
Dec 29 '18 at 9:01