Show that the sequence contains at least one prime term

Question

Problem: Given a sequence of $n$ natural numbers $a_1,a_2,...,a_n$ with $1<a_i<(2n-1)^2$, $(i=\overline{1,n})$ and $i < j \iff a_i < a_j$. If all of the terms are pairwise coprime, show that at least one of them must be prime.

---

My try: (based on weak arguments)

• Claim: $p_n \ge 2n-1$ (i.e. $n^\text{th}$ prime number is not less than $n^\text{th}$ odd number).

• Proof: $\square$ Trivial to check for some initial $n$'s:$$p_1=2 \ge 1$$ $$p_2=3 \ge 3$$ $$p_3=5 \ge 5$$ $$...$$ Now, since $p_{i+1} - p_i \ge 2 \ \ (\forall ~ i \ge 2)$ but the difference between any two consecutive odd numbers is $2$, the claim is obvious. $\blacksquare$

For the sake of contradiction, assume that there is no prime in them. Since $\gcd(a_i,a_j)=1, \ \ (i\neq j)$, all terms of the sequence must have distinct prime factors. As we do not want to be run out of prime factors that are less than $2n-1$, we better assume $a_i=p_i^2$ (if we can prove that the original statement is true for this case, then it is true in general since for any other construction of $a_i'$ we will have $a_i<a_i'$).

Then, $a_n = p_n^2$, but the claim implies $a_n=p_n^2 \ge (2n-1)^2$. A contradiction.

Therefore, at least one of the terms must be prime.

---

However, this "solution" seems to have many errors yet I cannot fix. I think I started approaching in the wrong way.

Any help is appreciated.

Answer 1

I would not say that your proof has many errors. It has some gaps but it is basically correct.

Let us order all these sequences in Short-Lex order (first look at the first terms, if they are equal, look at the second terms, etc., shorter sequences are smaller).

Take the smallest in the Short-Lex order sequence $a_1,...a_n$ without prime numbers where numbers are pairwise coprime.

Then as you notice primes dividing different $a_i$ are different. Let $p_1,...,p_m$ be all primes dividing $a_1,...,a_n$, $p_1<...<p_m$.

The number $a_1$ is a product of some $p_j$ ($p_{i_1}<...<p_{i_{k_1}}$), $k_1>1$. None of the other $a_s, s>1$ is divisible by any of these $p_{i_s}$. Then $a_1\ge p_{i_1}^2$. And if we replace in our sequence $a_1$ by $p_{i_1}^2$, the new sequence will not be bigger in the lexicographic order and still satisfy the conditions. Hence $a_1=p_{i_1}^2$. Now look at the next number, $a_2$. By the same argument, we can assume that it is the square of a prime. Note that when we replace $a_2$ by $p^2$ where $p$ is the first prime dividing $a_2$, $p^2$ may be smaller than $a_1$; in that case we switch $a_1, a_2$.

Therefore we can assume that all numbers in the sequence $a_1,...,a_n$ are squares of primes $p_1^2,...,p_n^2$, $p_1<...<p_n$. But that contradicts, as you notice, the inequality $a_i<(2n-1)^2$. Q.E.D.