I recall solving this once before, but since I like the problem.. If we can find $p\ne q$ such that $(a_p,a_q)=1$, we're done: every sufficiently large positive integer $n$ can be written in the form $xa_p+ya_q,\ x,y\in\mathbb N$. We can thus assume there are no two such $p\ne q$. We now prove the assertion by induction on the first term of the sequence, $a_1$. The base step is basically proven, since if $a_1=1$ we can take $p=1$ and any $q>1$ we want. There must be a prime divisor $u|a_1$ which divides infinitely many terms of the sequence, which form some subsequence $(a_{k_n})_{n\ge 1},\ k_1=1$. Now apply the induction hypothesis to the sequence $\left(\frac{a_{k_n}}u\right)_{n\ge 1}$.

grobber wrote: If we can find $ p\ne q$ such that $ (a_p,a_q) = 1$, we're done: every sufficiently large positive integer $ n$ can be written in the form $ xa_p + ya_q,\ x,y\in\mathbb N$ Please can you explain why? I don't know this fact.

See http://www.mathlinks.ro/Wiki/index.php/Chicken_McNugget_Theorem .

I believe its called the "Chicken McNugget Theorem". Its easier to give an example to show why this is intuitively true: Chicken McNugget Theorem: \[ \text{If }(a,b)=1\text{ then all }n>(a-1)(b-1)\text{ can be written as }xa+yb\] Take $ 3,7$. Beyond $ 12$, we can write 13=2(3)+7, 14=2(7), and 15=5(3). Now all numbers can be written mod 3, so just scale these up by three to hit all positive integers beyond a point. EDIT: I just saw i got beaten to this post...

This is very helpful. Thanks

If $(a_p, a_q) \neq 1$ for all $p, q$, simply scale down. Pick $a_p, a_q$ such that $(a_p, a_q) = 1$; we simply need $a_q \mid a_m - xa_p$. But for any $a_m > a_pa_q$, there exists some $1 \leq a_p \leq a_q$ such that the conclusion is true due to the relatively prime condition. Infinitely many $a_m$ exist because the sequence is strictly increasing.