Mixing
find a subsequence relatively prime
$begingroup$
Let $forall n in mathbb{N}: a_n := n^2 + 2$.
Find a subsequence $(a_{n_k})_{kin mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}$ and $a_{n_j}$ are relatively prime whenever $i neq j$.
And another subsequence $(a_{n_k})_{k in mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}mid a_{n_j}$ whenever $i lt j$.
My attempt so far. I cannot continue with the remainder theorem because $(a_{n_i})$ & $(a_{n_j})$ are not integers. I don't even know if I have the mathematical technicality to complete such a problem.
sequences-and-series elementary-number-theory
edited Oct 27 '17 at 14:24
user26857
39.3k124183
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
$endgroup$
add a comment |
$begingroup$
Let $forall n in mathbb{N}: a_n := n^2 + 2$.
Find a subsequence $(a_{n_k})_{kin mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}$ and $a_{n_j}$ are relatively prime whenever $i neq j$.
And another subsequence $(a_{n_k})_{k in mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}mid a_{n_j}$ whenever $i lt j$.
My attempt so far. I cannot continue with the remainder theorem because $(a_{n_i})$ & $(a_{n_j})$ are not integers. I don't even know if I have the mathematical technicality to complete such a problem.
sequences-and-series elementary-number-theory
edited Oct 27 '17 at 14:24
user26857
39.3k124183
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
$endgroup$
$begingroup$
What do you/they/"it" mean by find? Simply prove that such subsequences exist? Give a constructive way to build them? Or "find" them in closed form?
$endgroup$
– mathguy
Oct 26 '17 at 22:38
1
$begingroup$
I'd try to do the first one recursively. Start with $a_1=3$. Let $a_2=a_1^2+2=11$, then let $a_n=(prod a_i)^2+2$, something like that.
$endgroup$
– lulu
Oct 26 '17 at 22:46
add a comment |
$begingroup$
Let $forall n in mathbb{N}: a_n := n^2 + 2$.
Find a subsequence $(a_{n_k})_{kin mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}$ and $a_{n_j}$ are relatively prime whenever $i neq j$.
And another subsequence $(a_{n_k})_{k in mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}mid a_{n_j}$ whenever $i lt j$.
My attempt so far. I cannot continue with the remainder theorem because $(a_{n_i})$ & $(a_{n_j})$ are not integers. I don't even know if I have the mathematical technicality to complete such a problem.
sequences-and-series elementary-number-theory
edited Oct 27 '17 at 14:24
user26857
39.3k124183
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
$endgroup$
Let $forall n in mathbb{N}: a_n := n^2 + 2$.
Find a subsequence $(a_{n_k})_{kin mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}$ and $a_{n_j}$ are relatively prime whenever $i neq j$.
And another subsequence $(a_{n_k})_{k in mathbb{N}}$ of $(a_n)_{n in mathbb{N}}$ such that $a_{n_i}mid a_{n_j}$ whenever $i lt j$.
My attempt so far. I cannot continue with the remainder theorem because $(a_{n_i})$ & $(a_{n_j})$ are not integers. I don't even know if I have the mathematical technicality to complete such a problem.
sequences-and-series elementary-number-theory
sequences-and-series elementary-number-theory
edited Oct 27 '17 at 14:24
user26857
39.3k124183
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
edited Oct 27 '17 at 14:24
user26857
39.3k124183
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
edited Oct 27 '17 at 14:24
user26857
39.3k124183
edited Oct 27 '17 at 14:24
user26857
39.3k124183
edited Oct 27 '17 at 14:24
user26857
39.3k124183
39.3k124183
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
asked Oct 26 '17 at 22:31
GI-CasGI-Cas
164
164
$begingroup$
What do you/they/"it" mean by find? Simply prove that such subsequences exist? Give a constructive way to build them? Or "find" them in closed form?
$endgroup$
– mathguy
Oct 26 '17 at 22:38
1
$begingroup$
I'd try to do the first one recursively. Start with $a_1=3$. Let $a_2=a_1^2+2=11$, then let $a_n=(prod a_i)^2+2$, something like that.
$endgroup$
– lulu
Oct 26 '17 at 22:46
add a comment |
$begingroup$
What do you/they/"it" mean by find? Simply prove that such subsequences exist? Give a constructive way to build them? Or "find" them in closed form?
$endgroup$
– mathguy
Oct 26 '17 at 22:38
1
$begingroup$
I'd try to do the first one recursively. Start with $a_1=3$. Let $a_2=a_1^2+2=11$, then let $a_n=(prod a_i)^2+2$, something like that.
$endgroup$
– lulu
Oct 26 '17 at 22:46
$begingroup$
What do you/they/"it" mean by find? Simply prove that such subsequences exist? Give a constructive way to build them? Or "find" them in closed form?
$endgroup$
– mathguy
Oct 26 '17 at 22:38
$begingroup$
What do you/they/"it" mean by find? Simply prove that such subsequences exist? Give a constructive way to build them? Or "find" them in closed form?
$endgroup$
– mathguy
Oct 26 '17 at 22:38
1
1
$begingroup$
I'd try to do the first one recursively. Start with $a_1=3$. Let $a_2=a_1^2+2=11$, then let $a_n=(prod a_i)^2+2$, something like that.
$endgroup$
– lulu
Oct 26 '17 at 22:46
$begingroup$
I'd try to do the first one recursively. Start with $a_1=3$. Let $a_2=a_1^2+2=11$, then let $a_n=(prod a_i)^2+2$, something like that.
$endgroup$
– lulu
Oct 26 '17 at 22:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Well, for the second one, let $x_1 = 1$, and $x_{m+1} = x_m^2 + x_m+2$. Now, we note that:
$$a_{x_{m+1}} = x_{m+1}^2 + 2 = (x_m^2+2x_m+3)(x_m^2 + 2) $$
is a multiple of $a_{x_m}$. By induction, this gives a sequence of numbers, each of whom is a multiple of the previous number and therefore of all numbers before it.
this gives the sequence $x_i : 1,4,22,508...$ with $a_i : 3,18,486,258066 $, each of which is a multiple of the number before it.
For the first question, note that if $m=k(n^2+2)$ for any positive odd integer $k$, then $p$ divides $m^2+2$ and $p$ divides $n^2+2$ implies that $p$ divides $2$, and if $n$ is odd, then $m$ is odd, so this forces $p=1$, and hence $m^2+2$ and $n^2+2$ are coprime.
To create the desired sequence, then we let $x_1 = 1$ and ensure that $x_{m}$ is a odd multiple of $x_1^2 +2,x_2^2+2,...,x_{m-1}^2+2$, so that $a_{x_m}, a_{x_n}$ would be co prime since (WLOG $m > n$) we would have $x_m$ as an odd multiple of $x_n$, so by our argument $a_{x_m},a_{x_n}$ would be co prime.
For example, we may take $x_1 = 1$, and $x_{m} = prod_{j=1}^{m-1} (x_{j}^2+2)$. Then the resulting sequence $a_{x_n}$ has pairwise co prime numbers.
For example, this sequence results in $x_1=1,x_2 = 3,x_3 = 11 times 3 = 33, x_4 = 11 times 3 times 35 = 1155$, and so on. Check that $a_{x_n}$ looks like $3,11,1091,1334027,...$
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
$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%2f2491575%2ffind-a-subsequence-relatively-prime%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$
Well, for the second one, let $x_1 = 1$, and $x_{m+1} = x_m^2 + x_m+2$. Now, we note that:
$$a_{x_{m+1}} = x_{m+1}^2 + 2 = (x_m^2+2x_m+3)(x_m^2 + 2) $$
is a multiple of $a_{x_m}$. By induction, this gives a sequence of numbers, each of whom is a multiple of the previous number and therefore of all numbers before it.
this gives the sequence $x_i : 1,4,22,508...$ with $a_i : 3,18,486,258066 $, each of which is a multiple of the number before it.
For the first question, note that if $m=k(n^2+2)$ for any positive odd integer $k$, then $p$ divides $m^2+2$ and $p$ divides $n^2+2$ implies that $p$ divides $2$, and if $n$ is odd, then $m$ is odd, so this forces $p=1$, and hence $m^2+2$ and $n^2+2$ are coprime.
To create the desired sequence, then we let $x_1 = 1$ and ensure that $x_{m}$ is a odd multiple of $x_1^2 +2,x_2^2+2,...,x_{m-1}^2+2$, so that $a_{x_m}, a_{x_n}$ would be co prime since (WLOG $m > n$) we would have $x_m$ as an odd multiple of $x_n$, so by our argument $a_{x_m},a_{x_n}$ would be co prime.
For example, we may take $x_1 = 1$, and $x_{m} = prod_{j=1}^{m-1} (x_{j}^2+2)$. Then the resulting sequence $a_{x_n}$ has pairwise co prime numbers.
For example, this sequence results in $x_1=1,x_2 = 3,x_3 = 11 times 3 = 33, x_4 = 11 times 3 times 35 = 1155$, and so on. Check that $a_{x_n}$ looks like $3,11,1091,1334027,...$
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
$endgroup$
add a comment |
$begingroup$
Well, for the second one, let $x_1 = 1$, and $x_{m+1} = x_m^2 + x_m+2$. Now, we note that:
$$a_{x_{m+1}} = x_{m+1}^2 + 2 = (x_m^2+2x_m+3)(x_m^2 + 2) $$
is a multiple of $a_{x_m}$. By induction, this gives a sequence of numbers, each of whom is a multiple of the previous number and therefore of all numbers before it.
this gives the sequence $x_i : 1,4,22,508...$ with $a_i : 3,18,486,258066 $, each of which is a multiple of the number before it.
For the first question, note that if $m=k(n^2+2)$ for any positive odd integer $k$, then $p$ divides $m^2+2$ and $p$ divides $n^2+2$ implies that $p$ divides $2$, and if $n$ is odd, then $m$ is odd, so this forces $p=1$, and hence $m^2+2$ and $n^2+2$ are coprime.
To create the desired sequence, then we let $x_1 = 1$ and ensure that $x_{m}$ is a odd multiple of $x_1^2 +2,x_2^2+2,...,x_{m-1}^2+2$, so that $a_{x_m}, a_{x_n}$ would be co prime since (WLOG $m > n$) we would have $x_m$ as an odd multiple of $x_n$, so by our argument $a_{x_m},a_{x_n}$ would be co prime.
For example, we may take $x_1 = 1$, and $x_{m} = prod_{j=1}^{m-1} (x_{j}^2+2)$. Then the resulting sequence $a_{x_n}$ has pairwise co prime numbers.
For example, this sequence results in $x_1=1,x_2 = 3,x_3 = 11 times 3 = 33, x_4 = 11 times 3 times 35 = 1155$, and so on. Check that $a_{x_n}$ looks like $3,11,1091,1334027,...$
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
$endgroup$
add a comment |
$begingroup$
Well, for the second one, let $x_1 = 1$, and $x_{m+1} = x_m^2 + x_m+2$. Now, we note that:
$$a_{x_{m+1}} = x_{m+1}^2 + 2 = (x_m^2+2x_m+3)(x_m^2 + 2) $$
is a multiple of $a_{x_m}$. By induction, this gives a sequence of numbers, each of whom is a multiple of the previous number and therefore of all numbers before it.
this gives the sequence $x_i : 1,4,22,508...$ with $a_i : 3,18,486,258066 $, each of which is a multiple of the number before it.
For the first question, note that if $m=k(n^2+2)$ for any positive odd integer $k$, then $p$ divides $m^2+2$ and $p$ divides $n^2+2$ implies that $p$ divides $2$, and if $n$ is odd, then $m$ is odd, so this forces $p=1$, and hence $m^2+2$ and $n^2+2$ are coprime.
To create the desired sequence, then we let $x_1 = 1$ and ensure that $x_{m}$ is a odd multiple of $x_1^2 +2,x_2^2+2,...,x_{m-1}^2+2$, so that $a_{x_m}, a_{x_n}$ would be co prime since (WLOG $m > n$) we would have $x_m$ as an odd multiple of $x_n$, so by our argument $a_{x_m},a_{x_n}$ would be co prime.
For example, we may take $x_1 = 1$, and $x_{m} = prod_{j=1}^{m-1} (x_{j}^2+2)$. Then the resulting sequence $a_{x_n}$ has pairwise co prime numbers.
For example, this sequence results in $x_1=1,x_2 = 3,x_3 = 11 times 3 = 33, x_4 = 11 times 3 times 35 = 1155$, and so on. Check that $a_{x_n}$ looks like $3,11,1091,1334027,...$
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
$endgroup$
Well, for the second one, let $x_1 = 1$, and $x_{m+1} = x_m^2 + x_m+2$. Now, we note that:
$$a_{x_{m+1}} = x_{m+1}^2 + 2 = (x_m^2+2x_m+3)(x_m^2 + 2) $$
is a multiple of $a_{x_m}$. By induction, this gives a sequence of numbers, each of whom is a multiple of the previous number and therefore of all numbers before it.
this gives the sequence $x_i : 1,4,22,508...$ with $a_i : 3,18,486,258066 $, each of which is a multiple of the number before it.
For the first question, note that if $m=k(n^2+2)$ for any positive odd integer $k$, then $p$ divides $m^2+2$ and $p$ divides $n^2+2$ implies that $p$ divides $2$, and if $n$ is odd, then $m$ is odd, so this forces $p=1$, and hence $m^2+2$ and $n^2+2$ are coprime.
To create the desired sequence, then we let $x_1 = 1$ and ensure that $x_{m}$ is a odd multiple of $x_1^2 +2,x_2^2+2,...,x_{m-1}^2+2$, so that $a_{x_m}, a_{x_n}$ would be co prime since (WLOG $m > n$) we would have $x_m$ as an odd multiple of $x_n$, so by our argument $a_{x_m},a_{x_n}$ would be co prime.
For example, we may take $x_1 = 1$, and $x_{m} = prod_{j=1}^{m-1} (x_{j}^2+2)$. Then the resulting sequence $a_{x_n}$ has pairwise co prime numbers.
For example, this sequence results in $x_1=1,x_2 = 3,x_3 = 11 times 3 = 33, x_4 = 11 times 3 times 35 = 1155$, and so on. Check that $a_{x_n}$ looks like $3,11,1091,1334027,...$
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
edited Jan 18 at 6:01
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
answered Oct 27 '17 at 1:43
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.8k33477
38.8k33477
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%2f2491575%2ffind-a-subsequence-relatively-prime%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
$begingroup$
What do you/they/"it" mean by find? Simply prove that such subsequences exist? Give a constructive way to build them? Or "find" them in closed form?
$endgroup$
– mathguy
Oct 26 '17 at 22:38
1
$begingroup$
I'd try to do the first one recursively. Start with $a_1=3$. Let $a_2=a_1^2+2=11$, then let $a_n=(prod a_i)^2+2$, something like that.
$endgroup$
– lulu
Oct 26 '17 at 22:46