Mixing
Given $k$, for every $n>1$, constructing a set of size $n$ of non-zero integers having gcd $k$ so that no...
$begingroup$
For a finite subset $S subseteq mathbb Z setminus {0}$, let us say $d=gcd S$ iff $d>0 $ , $ d|a,forall a in S$ and $m|a,forall ain S implies m|d$.
My question is:
Does there exist a positive integer $k$ such that the following holds : for every $n>1, exists $ a finite $X_n subseteq mathbb Zsetminus {0}$ such that $|X_n|=n$ , $k=gcd X_n$ but $gcd (X)ne k$ for every proper subset $X subsetneq X_n$ ?
combinatorics number-theory abelian-groups greatest-common-divisor principal-ideal-domains
asked Feb 1 at 22:55
user521337user521337
1,2201417
$endgroup$
add a comment |
$begingroup$
For a finite subset $S subseteq mathbb Z setminus {0}$, let us say $d=gcd S$ iff $d>0 $ , $ d|a,forall a in S$ and $m|a,forall ain S implies m|d$.
My question is:
Does there exist a positive integer $k$ such that the following holds : for every $n>1, exists $ a finite $X_n subseteq mathbb Zsetminus {0}$ such that $|X_n|=n$ , $k=gcd X_n$ but $gcd (X)ne k$ for every proper subset $X subsetneq X_n$ ?
combinatorics number-theory abelian-groups greatest-common-divisor principal-ideal-domains
asked Feb 1 at 22:55
user521337user521337
1,2201417
$endgroup$
add a comment |
$begingroup$
For a finite subset $S subseteq mathbb Z setminus {0}$, let us say $d=gcd S$ iff $d>0 $ , $ d|a,forall a in S$ and $m|a,forall ain S implies m|d$.
My question is:
Does there exist a positive integer $k$ such that the following holds : for every $n>1, exists $ a finite $X_n subseteq mathbb Zsetminus {0}$ such that $|X_n|=n$ , $k=gcd X_n$ but $gcd (X)ne k$ for every proper subset $X subsetneq X_n$ ?
combinatorics number-theory abelian-groups greatest-common-divisor principal-ideal-domains
asked Feb 1 at 22:55
user521337user521337
1,2201417
$endgroup$
For a finite subset $S subseteq mathbb Z setminus {0}$, let us say $d=gcd S$ iff $d>0 $ , $ d|a,forall a in S$ and $m|a,forall ain S implies m|d$.
My question is:
Does there exist a positive integer $k$ such that the following holds : for every $n>1, exists $ a finite $X_n subseteq mathbb Zsetminus {0}$ such that $|X_n|=n$ , $k=gcd X_n$ but $gcd (X)ne k$ for every proper subset $X subsetneq X_n$ ?
combinatorics number-theory abelian-groups greatest-common-divisor principal-ideal-domains
combinatorics number-theory abelian-groups greatest-common-divisor principal-ideal-domains
asked Feb 1 at 22:55
user521337user521337
1,2201417
asked Feb 1 at 22:55
user521337user521337
1,2201417
asked Feb 1 at 22:55
user521337user521337
1,2201417
asked Feb 1 at 22:55
user521337user521337
1,2201417
asked Feb 1 at 22:55
user521337user521337
1,2201417
1,2201417
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It's easy to construct such a set, for any $k,n$.
Let ${p_1,cdots, p_n}$ be distinct primes such that none of them divide $k$. Then define $$q_i=frac 1{p_i}times prod_{j=1}^np_j$$
Thus, $q_i$ is the product of all the $p_j's$ other than $p_i$.
Now define $$x_i=q_itimes kquad text {and}quad X={x_i}$$
To see that this works, note first that it is clear that $k=gcd(X)$ since $k$ is a common divisor of all the $x_i$, and none of the $p_i$ divide all the ${x_i}$ Moreover if $S$ is a proper subset of $X$ then we can find some $x_inotin S$ in which case each element of $S$ is divisible by $p_ik$.
answered Feb 1 at 23:03
lulululu
43.6k25081
$endgroup$
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
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%2f3096828%2fgiven-k-for-every-n1-constructing-a-set-of-size-n-of-non-zero-integers%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$
It's easy to construct such a set, for any $k,n$.
Let ${p_1,cdots, p_n}$ be distinct primes such that none of them divide $k$. Then define $$q_i=frac 1{p_i}times prod_{j=1}^np_j$$
Thus, $q_i$ is the product of all the $p_j's$ other than $p_i$.
Now define $$x_i=q_itimes kquad text {and}quad X={x_i}$$
To see that this works, note first that it is clear that $k=gcd(X)$ since $k$ is a common divisor of all the $x_i$, and none of the $p_i$ divide all the ${x_i}$ Moreover if $S$ is a proper subset of $X$ then we can find some $x_inotin S$ in which case each element of $S$ is divisible by $p_ik$.
answered Feb 1 at 23:03
lulululu
43.6k25081
$endgroup$
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
add a comment |
$begingroup$
It's easy to construct such a set, for any $k,n$.
Let ${p_1,cdots, p_n}$ be distinct primes such that none of them divide $k$. Then define $$q_i=frac 1{p_i}times prod_{j=1}^np_j$$
Thus, $q_i$ is the product of all the $p_j's$ other than $p_i$.
Now define $$x_i=q_itimes kquad text {and}quad X={x_i}$$
To see that this works, note first that it is clear that $k=gcd(X)$ since $k$ is a common divisor of all the $x_i$, and none of the $p_i$ divide all the ${x_i}$ Moreover if $S$ is a proper subset of $X$ then we can find some $x_inotin S$ in which case each element of $S$ is divisible by $p_ik$.
answered Feb 1 at 23:03
lulululu
43.6k25081
$endgroup$
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
add a comment |
$begingroup$
It's easy to construct such a set, for any $k,n$.
Let ${p_1,cdots, p_n}$ be distinct primes such that none of them divide $k$. Then define $$q_i=frac 1{p_i}times prod_{j=1}^np_j$$
Thus, $q_i$ is the product of all the $p_j's$ other than $p_i$.
Now define $$x_i=q_itimes kquad text {and}quad X={x_i}$$
To see that this works, note first that it is clear that $k=gcd(X)$ since $k$ is a common divisor of all the $x_i$, and none of the $p_i$ divide all the ${x_i}$ Moreover if $S$ is a proper subset of $X$ then we can find some $x_inotin S$ in which case each element of $S$ is divisible by $p_ik$.
answered Feb 1 at 23:03
lulululu
43.6k25081
$endgroup$
It's easy to construct such a set, for any $k,n$.
Let ${p_1,cdots, p_n}$ be distinct primes such that none of them divide $k$. Then define $$q_i=frac 1{p_i}times prod_{j=1}^np_j$$
Thus, $q_i$ is the product of all the $p_j's$ other than $p_i$.
Now define $$x_i=q_itimes kquad text {and}quad X={x_i}$$
To see that this works, note first that it is clear that $k=gcd(X)$ since $k$ is a common divisor of all the $x_i$, and none of the $p_i$ divide all the ${x_i}$ Moreover if $S$ is a proper subset of $X$ then we can find some $x_inotin S$ in which case each element of $S$ is divisible by $p_ik$.
answered Feb 1 at 23:03
lulululu
43.6k25081
edited Feb 1 at 23:30
answered Feb 1 at 23:03
lulululu
43.6k25081
answered Feb 1 at 23:03
lulululu
43.6k25081
answered Feb 1 at 23:03
lulululu
43.6k25081
43.6k25081
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
add a comment |
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
The condition "none of them divide $k$" is not needed (though it allows your nice simple formulation of the proof)
$endgroup$
– Hagen von Eitzen
Feb 1 at 23:19
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
$begingroup$
@HagenvonEitzen Yeah, I left it in precisely for that simplicity.
$endgroup$
– lulu
Feb 1 at 23:21
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%2f3096828%2fgiven-k-for-every-n1-constructing-a-set-of-size-n-of-non-zero-integers%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
