Infinite sequence of integers has infinitely many prime divisors The 2019 Stack Overflow Developer Survey Results Are InInfinitely many primes $equiv 2 pmod 3$ proof correctnessExistence of a sequence that has every element of $mathbb N$ infinite number of timesLinear independence of vectors and solutions to systems of equationsClosed-form solution to 3D vector rotation problemCan decreasing sequence of sets with $A_i$ containing infinitely less elements than $A_i-1$ have finite limit?Proof of existence of infinitely many primes that divide the sequence $S(k)=sum_i=1^n a_i^k$ where $a_i_i=1^n$ forms an APOn puzzles about $pi$erfect numbers: has $sigma(pi(n))=pi(2n)$ infinitely many solutions?Vector combination to minimize distance to points?What is the convex hull of $textconv(u_1,u_2,cdots,u_p)+textconv(v_1,v_2,cdots,v_s)$?Any sequence of real numbers has a monotone subsequence.
Why didn't the Event Horizon Telescope team mention Sagittarius A*?
Can you cast a spell on someone in the Ethereal Plane, if you are on the Material Plane and have the True Seeing spell active?
Are there any other methods to apply to solving simultaneous equations?
Is Cinnamon a desktop environment or a window manager? (Or both?)
What is the most efficient way to store a numeric range?
Short story: man watches girlfriend's spaceship entering a 'black hole' (?) forever
Cooking pasta in a water boiler
Likelihood that a superbug or lethal virus could come from a landfill
Why not take a picture of a closer black hole?
Why doesn't UInt have a toDouble()?
Can an undergraduate be advised by a professor who is very far away?
Button changing its text & action. Good or terrible?
I am an eight letter word. What am I?
Is it okay to consider publishing in my first year of PhD?
How to notate time signature switching consistently every measure
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Is an up-to-date browser secure on an out-of-date OS?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
Can I have a signal generator on while it's not connected?
Kerning for subscripts of sigma?
How do I free up internal storage if I don't have any apps downloaded?
How to quickly solve partial fractions equation?
Is it safe to harvest rainwater that fell on solar panels?
Output the Arecibo Message
Infinite sequence of integers has infinitely many prime divisors
The 2019 Stack Overflow Developer Survey Results Are InInfinitely many primes $equiv 2 pmod 3$ proof correctnessExistence of a sequence that has every element of $mathbb N$ infinite number of timesLinear independence of vectors and solutions to systems of equationsClosed-form solution to 3D vector rotation problemCan decreasing sequence of sets with $A_i$ containing infinitely less elements than $A_i-1$ have finite limit?Proof of existence of infinitely many primes that divide the sequence $S(k)=sum_i=1^n a_i^k$ where $a_i_i=1^n$ forms an APOn puzzles about $pi$erfect numbers: has $sigma(pi(n))=pi(2n)$ infinitely many solutions?Vector combination to minimize distance to points?What is the convex hull of $textconv(u_1,u_2,cdots,u_p)+textconv(v_1,v_2,cdots,v_s)$?Any sequence of real numbers has a monotone subsequence.
$begingroup$
Problem: For a sequence $a_i_ige 1$ consisting of only positive integers, prove that if for all different positive integers $i$ and $j$, we have $a_i nmid a_j$ , then
$$pcolon p text is a prime and pmid a_i text for some i$$
is an infinite set.
I have a solution to this problem, but if you read my solution (which I have posted below) then you can see that it is kind of vague, not the type you can write in some contest. It is because I am not particularly trained in linear algebra. So I was hoping for someone to make my solution more rigorous. Also rather than posting a new solution, please tell me how I can improve my solution.
Thanks in advance.
My approach:
(1)Some motivation (Must read, because I have introduced some definitions here which I have used in the solution): Hmmm... the method of contradiction is the best way with this kind of problems. So let's assume that there are only finitely many primes in the set. OK let us consider the simplest case: there are only $2$ primes in the set. Then we can associate a two dimensional vector (with non-negative integer components) to all the elements of the sequence. Now observe that if $(a,b)$ is an element of the sequence then $(x,y)$ can't be an element of the sequence iff both $xge a$ and $yge b$ or $xle a$ and $yle b$. Now let us look at its geometrical interpretation by tossing the vectors onto the Cartesian plane. Planes where we can place points will be called safe region and the rest is danger region. Notice that there are two kinds of safe region: i)solid safe region, safe regions which has one of the axis as its border line and stretches infinitely, ii) lofty region, which is not in touch with any of the axis. Observe that if you keep placing more and more points in the solid region, it gradually gets thinner and thinner and ultimately it collapses to the axis. And since the lofty regions are finite, we can cover them with finitely many points (It is not hard to see that there are only finitely many lofty regions). Hmm..so the 2-D case seems doable. But we are still far from a complete solution. Indeed, what about 3-D and higher dimensional cases? The 3-D case initially looks like the corner of a box with some kind of layer glued to the 3 planes and as you keep placing points within those layers=safe regions, the layers keep getting thinner and thinner. But this time the lofty regions aren't well-behaved bounded anymore, but they can still be covered with finitely many points; after all they are partially bounded 3-D space. Time to take on the 4-D case? Yes, but not with imagination anymore. Time to generalize it to higher dimension with $vectors$!
SOLUTION: Throughout the solution by vector I mean vectors with non-negative integer components.
For the sake of contrary assume that the set of primes, $P$ is finite, i.e. $P=p_1,p_2.ldots,p_n$. Then each element of the sequence $a_i_ige 1$ is of the form $p_1^a_1p_2^a_2ldots p_n^a_n$, where $a_iin mathbbZ^+cup0$. Notice that all the $a_i$'s can't be equal to $0$, otherwise $1$ is an element of the sequence and $1$ divides every other number. We can assign a unique vector $v_i=(a_1,a_2,ldots,a_n)$ to each element $a_i=p_1^a_1p_2^a_2ldots p_n^a_n$ of the sequence . Suppose $v_1=(alpha_1,alpha_2,ldots, alpha _n)$. We will now define some sets,
$$D(v_1)=(x_1,x_2,ldots,x_n)mid x_ilealpha _i~for~all~i$$
$$S_1(v_1)=(x_1,y_2,ldots,y_n)mid x_1<alpha_1$$
$$S_2(v_1)=(y_1,x_2,ldots,y_n)mid x_2<alpha_2$$
$$vdots$$
$$S_n(v_1)=(y_1,y_2,ldots,x_n)mid x_nlealpha_n$$
Then $v_2in S_1(v_1)cup S_2(v_2)cupldotscup S_n(v_n) -D(v_1)=S(v_1)-D(v_1)$. Notice that $v_2$ has at-least one component which is smaller than that component of $v_1$. So $S(v_1)cap S(v_2)-D(v_1)cup D(v_2)$ has at least one vector component which is less than that of $S(v_1)-D(v_1)$ and thus the solid danger region will get thinner and thinner if we keep placing more points in it and gradually just collapse to the axis. But still there are finitely many lofty danger region. But we can always cover them with finitely many vectors.
sequences-and-series combinatorics number-theory prime-numbers vectors
$endgroup$
add a comment |
$begingroup$
Problem: For a sequence $a_i_ige 1$ consisting of only positive integers, prove that if for all different positive integers $i$ and $j$, we have $a_i nmid a_j$ , then
$$pcolon p text is a prime and pmid a_i text for some i$$
is an infinite set.
I have a solution to this problem, but if you read my solution (which I have posted below) then you can see that it is kind of vague, not the type you can write in some contest. It is because I am not particularly trained in linear algebra. So I was hoping for someone to make my solution more rigorous. Also rather than posting a new solution, please tell me how I can improve my solution.
Thanks in advance.
My approach:
(1)Some motivation (Must read, because I have introduced some definitions here which I have used in the solution): Hmmm... the method of contradiction is the best way with this kind of problems. So let's assume that there are only finitely many primes in the set. OK let us consider the simplest case: there are only $2$ primes in the set. Then we can associate a two dimensional vector (with non-negative integer components) to all the elements of the sequence. Now observe that if $(a,b)$ is an element of the sequence then $(x,y)$ can't be an element of the sequence iff both $xge a$ and $yge b$ or $xle a$ and $yle b$. Now let us look at its geometrical interpretation by tossing the vectors onto the Cartesian plane. Planes where we can place points will be called safe region and the rest is danger region. Notice that there are two kinds of safe region: i)solid safe region, safe regions which has one of the axis as its border line and stretches infinitely, ii) lofty region, which is not in touch with any of the axis. Observe that if you keep placing more and more points in the solid region, it gradually gets thinner and thinner and ultimately it collapses to the axis. And since the lofty regions are finite, we can cover them with finitely many points (It is not hard to see that there are only finitely many lofty regions). Hmm..so the 2-D case seems doable. But we are still far from a complete solution. Indeed, what about 3-D and higher dimensional cases? The 3-D case initially looks like the corner of a box with some kind of layer glued to the 3 planes and as you keep placing points within those layers=safe regions, the layers keep getting thinner and thinner. But this time the lofty regions aren't well-behaved bounded anymore, but they can still be covered with finitely many points; after all they are partially bounded 3-D space. Time to take on the 4-D case? Yes, but not with imagination anymore. Time to generalize it to higher dimension with $vectors$!
SOLUTION: Throughout the solution by vector I mean vectors with non-negative integer components.
For the sake of contrary assume that the set of primes, $P$ is finite, i.e. $P=p_1,p_2.ldots,p_n$. Then each element of the sequence $a_i_ige 1$ is of the form $p_1^a_1p_2^a_2ldots p_n^a_n$, where $a_iin mathbbZ^+cup0$. Notice that all the $a_i$'s can't be equal to $0$, otherwise $1$ is an element of the sequence and $1$ divides every other number. We can assign a unique vector $v_i=(a_1,a_2,ldots,a_n)$ to each element $a_i=p_1^a_1p_2^a_2ldots p_n^a_n$ of the sequence . Suppose $v_1=(alpha_1,alpha_2,ldots, alpha _n)$. We will now define some sets,
$$D(v_1)=(x_1,x_2,ldots,x_n)mid x_ilealpha _i~for~all~i$$
$$S_1(v_1)=(x_1,y_2,ldots,y_n)mid x_1<alpha_1$$
$$S_2(v_1)=(y_1,x_2,ldots,y_n)mid x_2<alpha_2$$
$$vdots$$
$$S_n(v_1)=(y_1,y_2,ldots,x_n)mid x_nlealpha_n$$
Then $v_2in S_1(v_1)cup S_2(v_2)cupldotscup S_n(v_n) -D(v_1)=S(v_1)-D(v_1)$. Notice that $v_2$ has at-least one component which is smaller than that component of $v_1$. So $S(v_1)cap S(v_2)-D(v_1)cup D(v_2)$ has at least one vector component which is less than that of $S(v_1)-D(v_1)$ and thus the solid danger region will get thinner and thinner if we keep placing more points in it and gradually just collapse to the axis. But still there are finitely many lofty danger region. But we can always cover them with finitely many vectors.
sequences-and-series combinatorics number-theory prime-numbers vectors
$endgroup$
add a comment |
$begingroup$
Problem: For a sequence $a_i_ige 1$ consisting of only positive integers, prove that if for all different positive integers $i$ and $j$, we have $a_i nmid a_j$ , then
$$pcolon p text is a prime and pmid a_i text for some i$$
is an infinite set.
I have a solution to this problem, but if you read my solution (which I have posted below) then you can see that it is kind of vague, not the type you can write in some contest. It is because I am not particularly trained in linear algebra. So I was hoping for someone to make my solution more rigorous. Also rather than posting a new solution, please tell me how I can improve my solution.
Thanks in advance.
My approach:
(1)Some motivation (Must read, because I have introduced some definitions here which I have used in the solution): Hmmm... the method of contradiction is the best way with this kind of problems. So let's assume that there are only finitely many primes in the set. OK let us consider the simplest case: there are only $2$ primes in the set. Then we can associate a two dimensional vector (with non-negative integer components) to all the elements of the sequence. Now observe that if $(a,b)$ is an element of the sequence then $(x,y)$ can't be an element of the sequence iff both $xge a$ and $yge b$ or $xle a$ and $yle b$. Now let us look at its geometrical interpretation by tossing the vectors onto the Cartesian plane. Planes where we can place points will be called safe region and the rest is danger region. Notice that there are two kinds of safe region: i)solid safe region, safe regions which has one of the axis as its border line and stretches infinitely, ii) lofty region, which is not in touch with any of the axis. Observe that if you keep placing more and more points in the solid region, it gradually gets thinner and thinner and ultimately it collapses to the axis. And since the lofty regions are finite, we can cover them with finitely many points (It is not hard to see that there are only finitely many lofty regions). Hmm..so the 2-D case seems doable. But we are still far from a complete solution. Indeed, what about 3-D and higher dimensional cases? The 3-D case initially looks like the corner of a box with some kind of layer glued to the 3 planes and as you keep placing points within those layers=safe regions, the layers keep getting thinner and thinner. But this time the lofty regions aren't well-behaved bounded anymore, but they can still be covered with finitely many points; after all they are partially bounded 3-D space. Time to take on the 4-D case? Yes, but not with imagination anymore. Time to generalize it to higher dimension with $vectors$!
SOLUTION: Throughout the solution by vector I mean vectors with non-negative integer components.
For the sake of contrary assume that the set of primes, $P$ is finite, i.e. $P=p_1,p_2.ldots,p_n$. Then each element of the sequence $a_i_ige 1$ is of the form $p_1^a_1p_2^a_2ldots p_n^a_n$, where $a_iin mathbbZ^+cup0$. Notice that all the $a_i$'s can't be equal to $0$, otherwise $1$ is an element of the sequence and $1$ divides every other number. We can assign a unique vector $v_i=(a_1,a_2,ldots,a_n)$ to each element $a_i=p_1^a_1p_2^a_2ldots p_n^a_n$ of the sequence . Suppose $v_1=(alpha_1,alpha_2,ldots, alpha _n)$. We will now define some sets,
$$D(v_1)=(x_1,x_2,ldots,x_n)mid x_ilealpha _i~for~all~i$$
$$S_1(v_1)=(x_1,y_2,ldots,y_n)mid x_1<alpha_1$$
$$S_2(v_1)=(y_1,x_2,ldots,y_n)mid x_2<alpha_2$$
$$vdots$$
$$S_n(v_1)=(y_1,y_2,ldots,x_n)mid x_nlealpha_n$$
Then $v_2in S_1(v_1)cup S_2(v_2)cupldotscup S_n(v_n) -D(v_1)=S(v_1)-D(v_1)$. Notice that $v_2$ has at-least one component which is smaller than that component of $v_1$. So $S(v_1)cap S(v_2)-D(v_1)cup D(v_2)$ has at least one vector component which is less than that of $S(v_1)-D(v_1)$ and thus the solid danger region will get thinner and thinner if we keep placing more points in it and gradually just collapse to the axis. But still there are finitely many lofty danger region. But we can always cover them with finitely many vectors.
sequences-and-series combinatorics number-theory prime-numbers vectors
$endgroup$
Problem: For a sequence $a_i_ige 1$ consisting of only positive integers, prove that if for all different positive integers $i$ and $j$, we have $a_i nmid a_j$ , then
$$pcolon p text is a prime and pmid a_i text for some i$$
is an infinite set.
I have a solution to this problem, but if you read my solution (which I have posted below) then you can see that it is kind of vague, not the type you can write in some contest. It is because I am not particularly trained in linear algebra. So I was hoping for someone to make my solution more rigorous. Also rather than posting a new solution, please tell me how I can improve my solution.
Thanks in advance.
My approach:
(1)Some motivation (Must read, because I have introduced some definitions here which I have used in the solution): Hmmm... the method of contradiction is the best way with this kind of problems. So let's assume that there are only finitely many primes in the set. OK let us consider the simplest case: there are only $2$ primes in the set. Then we can associate a two dimensional vector (with non-negative integer components) to all the elements of the sequence. Now observe that if $(a,b)$ is an element of the sequence then $(x,y)$ can't be an element of the sequence iff both $xge a$ and $yge b$ or $xle a$ and $yle b$. Now let us look at its geometrical interpretation by tossing the vectors onto the Cartesian plane. Planes where we can place points will be called safe region and the rest is danger region. Notice that there are two kinds of safe region: i)solid safe region, safe regions which has one of the axis as its border line and stretches infinitely, ii) lofty region, which is not in touch with any of the axis. Observe that if you keep placing more and more points in the solid region, it gradually gets thinner and thinner and ultimately it collapses to the axis. And since the lofty regions are finite, we can cover them with finitely many points (It is not hard to see that there are only finitely many lofty regions). Hmm..so the 2-D case seems doable. But we are still far from a complete solution. Indeed, what about 3-D and higher dimensional cases? The 3-D case initially looks like the corner of a box with some kind of layer glued to the 3 planes and as you keep placing points within those layers=safe regions, the layers keep getting thinner and thinner. But this time the lofty regions aren't well-behaved bounded anymore, but they can still be covered with finitely many points; after all they are partially bounded 3-D space. Time to take on the 4-D case? Yes, but not with imagination anymore. Time to generalize it to higher dimension with $vectors$!
SOLUTION: Throughout the solution by vector I mean vectors with non-negative integer components.
For the sake of contrary assume that the set of primes, $P$ is finite, i.e. $P=p_1,p_2.ldots,p_n$. Then each element of the sequence $a_i_ige 1$ is of the form $p_1^a_1p_2^a_2ldots p_n^a_n$, where $a_iin mathbbZ^+cup0$. Notice that all the $a_i$'s can't be equal to $0$, otherwise $1$ is an element of the sequence and $1$ divides every other number. We can assign a unique vector $v_i=(a_1,a_2,ldots,a_n)$ to each element $a_i=p_1^a_1p_2^a_2ldots p_n^a_n$ of the sequence . Suppose $v_1=(alpha_1,alpha_2,ldots, alpha _n)$. We will now define some sets,
$$D(v_1)=(x_1,x_2,ldots,x_n)mid x_ilealpha _i~for~all~i$$
$$S_1(v_1)=(x_1,y_2,ldots,y_n)mid x_1<alpha_1$$
$$S_2(v_1)=(y_1,x_2,ldots,y_n)mid x_2<alpha_2$$
$$vdots$$
$$S_n(v_1)=(y_1,y_2,ldots,x_n)mid x_nlealpha_n$$
Then $v_2in S_1(v_1)cup S_2(v_2)cupldotscup S_n(v_n) -D(v_1)=S(v_1)-D(v_1)$. Notice that $v_2$ has at-least one component which is smaller than that component of $v_1$. So $S(v_1)cap S(v_2)-D(v_1)cup D(v_2)$ has at least one vector component which is less than that of $S(v_1)-D(v_1)$ and thus the solid danger region will get thinner and thinner if we keep placing more points in it and gradually just collapse to the axis. But still there are finitely many lofty danger region. But we can always cover them with finitely many vectors.
sequences-and-series combinatorics number-theory prime-numbers vectors
sequences-and-series combinatorics number-theory prime-numbers vectors
edited Nov 25 '18 at 17:34
the_fox
2,90231538
2,90231538
asked Nov 25 '18 at 16:24
Basudeb BhowmickBasudeb Bhowmick
356
356
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Claim. Let $P$ be a finite set of primes and let $A$ be a subset of $Bbb N$ such that each $ain A$ has all its prime divisors in $P$ and for $a,bin A$ with $ane b$, we always have $anmid b$. Then $A$ is finite.
Proof. By induction on $|P|$, the case $|P|=1$ being trivial.
Assume $|P|=m$ and the claim is true whenever $|P|<m$.
Assume that $A$ has the properties of the claim, but is infinite.
Pick $a_0in A$ and write $a_0=prod_pin Pp^c_p$ with $c_pinBbb N_0$.
For $pin P$ and $0le c<c_p$ let
$$N_p,c=,ain A:p^c.$$
Then each $ain Asetminusa_0$ is in some $N_p,c$ as otherwise we have $amid a_0$. As there are only finitely many $(p,c)$, we conclude that some $N_p_0,c_0$ is infinite. For this, let $$A'=left,frac ap_0^c_0: ain N_p_0,c_0,right.$$
Then $A'$ fulfils the condition of the claim with $P$ replaced by $P'=Psetminusp_0$. As $|P'|=m-1$, the induction hypothesis says that $A'$ is finite, contradiction. $square$
$endgroup$
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
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%2f3013047%2finfinite-sequence-of-integers-has-infinitely-many-prime-divisors%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$
Claim. Let $P$ be a finite set of primes and let $A$ be a subset of $Bbb N$ such that each $ain A$ has all its prime divisors in $P$ and for $a,bin A$ with $ane b$, we always have $anmid b$. Then $A$ is finite.
Proof. By induction on $|P|$, the case $|P|=1$ being trivial.
Assume $|P|=m$ and the claim is true whenever $|P|<m$.
Assume that $A$ has the properties of the claim, but is infinite.
Pick $a_0in A$ and write $a_0=prod_pin Pp^c_p$ with $c_pinBbb N_0$.
For $pin P$ and $0le c<c_p$ let
$$N_p,c=,ain A:p^c.$$
Then each $ain Asetminusa_0$ is in some $N_p,c$ as otherwise we have $amid a_0$. As there are only finitely many $(p,c)$, we conclude that some $N_p_0,c_0$ is infinite. For this, let $$A'=left,frac ap_0^c_0: ain N_p_0,c_0,right.$$
Then $A'$ fulfils the condition of the claim with $P$ replaced by $P'=Psetminusp_0$. As $|P'|=m-1$, the induction hypothesis says that $A'$ is finite, contradiction. $square$
$endgroup$
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
add a comment |
$begingroup$
Claim. Let $P$ be a finite set of primes and let $A$ be a subset of $Bbb N$ such that each $ain A$ has all its prime divisors in $P$ and for $a,bin A$ with $ane b$, we always have $anmid b$. Then $A$ is finite.
Proof. By induction on $|P|$, the case $|P|=1$ being trivial.
Assume $|P|=m$ and the claim is true whenever $|P|<m$.
Assume that $A$ has the properties of the claim, but is infinite.
Pick $a_0in A$ and write $a_0=prod_pin Pp^c_p$ with $c_pinBbb N_0$.
For $pin P$ and $0le c<c_p$ let
$$N_p,c=,ain A:p^c.$$
Then each $ain Asetminusa_0$ is in some $N_p,c$ as otherwise we have $amid a_0$. As there are only finitely many $(p,c)$, we conclude that some $N_p_0,c_0$ is infinite. For this, let $$A'=left,frac ap_0^c_0: ain N_p_0,c_0,right.$$
Then $A'$ fulfils the condition of the claim with $P$ replaced by $P'=Psetminusp_0$. As $|P'|=m-1$, the induction hypothesis says that $A'$ is finite, contradiction. $square$
$endgroup$
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
add a comment |
$begingroup$
Claim. Let $P$ be a finite set of primes and let $A$ be a subset of $Bbb N$ such that each $ain A$ has all its prime divisors in $P$ and for $a,bin A$ with $ane b$, we always have $anmid b$. Then $A$ is finite.
Proof. By induction on $|P|$, the case $|P|=1$ being trivial.
Assume $|P|=m$ and the claim is true whenever $|P|<m$.
Assume that $A$ has the properties of the claim, but is infinite.
Pick $a_0in A$ and write $a_0=prod_pin Pp^c_p$ with $c_pinBbb N_0$.
For $pin P$ and $0le c<c_p$ let
$$N_p,c=,ain A:p^c.$$
Then each $ain Asetminusa_0$ is in some $N_p,c$ as otherwise we have $amid a_0$. As there are only finitely many $(p,c)$, we conclude that some $N_p_0,c_0$ is infinite. For this, let $$A'=left,frac ap_0^c_0: ain N_p_0,c_0,right.$$
Then $A'$ fulfils the condition of the claim with $P$ replaced by $P'=Psetminusp_0$. As $|P'|=m-1$, the induction hypothesis says that $A'$ is finite, contradiction. $square$
$endgroup$
Claim. Let $P$ be a finite set of primes and let $A$ be a subset of $Bbb N$ such that each $ain A$ has all its prime divisors in $P$ and for $a,bin A$ with $ane b$, we always have $anmid b$. Then $A$ is finite.
Proof. By induction on $|P|$, the case $|P|=1$ being trivial.
Assume $|P|=m$ and the claim is true whenever $|P|<m$.
Assume that $A$ has the properties of the claim, but is infinite.
Pick $a_0in A$ and write $a_0=prod_pin Pp^c_p$ with $c_pinBbb N_0$.
For $pin P$ and $0le c<c_p$ let
$$N_p,c=,ain A:p^c.$$
Then each $ain Asetminusa_0$ is in some $N_p,c$ as otherwise we have $amid a_0$. As there are only finitely many $(p,c)$, we conclude that some $N_p_0,c_0$ is infinite. For this, let $$A'=left,frac ap_0^c_0: ain N_p_0,c_0,right.$$
Then $A'$ fulfils the condition of the claim with $P$ replaced by $P'=Psetminusp_0$. As $|P'|=m-1$, the induction hypothesis says that $A'$ is finite, contradiction. $square$
edited Mar 24 at 6:50
Basudeb Bhowmick
356
356
answered Nov 25 '18 at 16:58
Hagen von EitzenHagen von Eitzen
283k23273508
283k23273508
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
add a comment |
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
$begingroup$
An interesting thing is that our solutions are actually equivalent. Like $N_p,c$ in your solution is just the mathematical form of my safe region and thinning out in my solution $equiv$ $A'$ in your solution. But my solution missed induction. Your solution is still much better. Thanks.
$endgroup$
– Basudeb Bhowmick
Nov 26 '18 at 13:56
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%2f3013047%2finfinite-sequence-of-integers-has-infinitely-many-prime-divisors%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