A Difficult Number Theory Olympiad level Question So, the question is like this:
$a_1$ = 1 and $a_2$ = 24, $a_n$ is smallest in the set A.
A = {a has not appeared in the set before and ($a_n,a_{n-1}$) = 1 for all a $\in$ N
Prove that every positive integer appears in this set.(For ex: $a_3 = 5, a_4 = 2, a_5 = 3,a_6 = 4, a_7 = 7$).
This question was given as a challenge in my INMOTC. I am unable to solve it. Can anybody help me in solving it?
 A: We will split this proof into three parts:
For any prime $q$, we prove that $q|a_j$ implies $q=a_i$ for $i\leq j$. Clearly, $q$ does not divide $a_{j-1}$ else $\gcd(a_j,a_{j-1})>1$. However, since $q\leq a_j$ we know $q=a_j$ or $q$ is already in the sequence. This proves the first part.

EDIT: Edited to to fix mistake.
Next, we prove that all primes $q$ will eventually be in $\{a_n\}_{n=1}^\infty$. There are two possibilities: either $q$ does not divide $a_n$ for all $n$ (this follows from part $1$), or $q$ is in $\{a_n\}_{n=1}^\infty$. Consider the sets
$$S=\{a_1,a_2,\dots a_q\}$$
and
$$T=\{1\leq m<a_q:\gcd(a_q,m)=1\text{ and }m\not\in S\}$$
(note that $T$ is finite). If $q\in S$, then we are done. If not, then $a_q>q$ and therefore $q\in T$. Now, $a_{q+1}\in T$ as $\gcd(q,a_q)=1$. This implies that if all other members of $T$ are not relatively prime to $a_q$, then $a_{q+1}=q$. If not, then choose the smallest member of $T$ that fits this condition (it might be $q$) to be $a_{q+1}$ and remove $a_{q+1}$ from $T$. Repeating this process at most $|T|$ times, we are assured that $q$ is somewhere in the set
$$\{a_{q+1},a_{q+2},\dots a_{q+|T|}\}$$
Since $q$ was arbitrary, all primes are eventually in $\{a_n\}_{n=1}^\infty$. This concludes the second part.

Finally, assume that there is some smallest natural $k$ such that $k\not\in \{a_n\}_{n=1}^\infty$ and let $N$ be defined such that $a_N$ is the last integer smaller than $k$ to be added to $\{a_n\}_{n=1}^\infty$.
Let $p$ be the smallest prime larger than $k$ such that
$$p\not\in\{a_1,a_2,\dots,a_N\}$$
Now, we know that there exists $M>N$ such that $p=a_M$. Since $p>k$ we know $\gcd(k,p)=1$. Thus, $a_{M+1}=k$ which is a contradiction. We conclude all natural numbers are eventually in $\{a_n\}_{n=1}^\infty$.
