Ytukyg

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_1}p_2^{a_2}ldots p_n^{a_n}$, where $a_iin mathbb{Z^+}cup{0}$. 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_1}p_2^{a_2}ldots 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.

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|=0$ 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 P}p^{c_p}$ with $c_pinBbb N_0$.
For $pin P$ and $0le c<c_p$ let
$$N_{p,c}={,ain A:p^c| a,}.$$
Then each $ain Asetminus{a}$ 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 a{p_0^{c_0}}: ain N_{p_0,c_0},right}.$$
Then $A'$ fulfils the condition of the claim with $P$ replaced by $P'=Psetminus{p}$. As $|P'|=m-1$, the induction hypothesis says that $A'$ is finite, contradiction. $square$