# $a_k$ is a countable sequence of positive numbers st. $gcd(a_1,a_2,…)=1$, show exists a finite subsequence $a_{i_1},a_{i_2},…,a_{i_n}$ with gcd 1

The question is,

Let $a_k$ be a countably infinite sequence of positive numbers st. $\gcd(a_1,a_2,...)=1$, does it exist a finite subsequence $a_{i_1},a_{i_2},...,a_{i_n}$ with $\gcd(a_{i_1},a_{i_2},...,a_{i_n})=1$?

or more generally,

Let $a_k$ be a countably infinite sequence of positive numbers st. $\gcd(a_1,a_2,...)=d$, does it exist a finite subsequence $a_{i_1},a_{i_2},...,a_{i_n}$ with $\gcd(a_{i_1},a_{i_2},...,a_{i_n})=d$?

Can anyone help with an elementary proof (pls. do not use advanced number theory stuff) or a counter example? Thank you.

This is a bit of a pedestrian argument, but you asked for one:

Recall that the GCD is $1$ if and only if no prime number divides all $a_i$. The number $a_1$ is divisible by a finite number of primes $p_1, \dots , p_k$. For each $p_j$ there exists some $a_{i_j}$ such that $p_j \nmid a_{i_j}$.

Now note that there is no prime number that divides each of $a_1, a_{i_1}, \dots , a_{i_k}$, and conclude.

(Note that the $a_{i_j}$ are not necessarily distinct.)

Hint: Let $d_n=\gcd(a_1,\dots,a_n)$. Then since $\{d_n\}$ is a non-empty set of positive integers, it must have a least element.

• How do you know this least element will be the gcd of all $a_i$? – quid Jan 17 '16 at 17:23
• That's why it is a hint. @quid – Thomas Andrews Jan 17 '16 at 17:25
• Well, yes and no. I think the "least value" is a big part of the "trick." Also, restricting it to just the case $a_1,\dots,a_n$ rather than arbitrary subsets, makes it easier to write :) @quid – Thomas Andrews Jan 17 '16 at 17:26
• Of course I thought about it. I wondered what I could give that would not give away the whole answer. I wrote the word "hint." What makes you think I wasn't aware this was not a complete proof? I actually wondered if it was too big a hint. @quid – Thomas Andrews Jan 17 '16 at 17:36
• Perhaps you just don't realize how trivial the rest of the proof is from this start? @quid – Thomas Andrews Jan 17 '16 at 17:54