# Given a sequence $a_1,a_2,\ldots ,a_n$, if $\gcd(a_1,a_2,\ldots ,a_n) = 1$, then there exists one pair $a_i,a_j$ st. $\gcd(a_i,a_j)=1$.

Anyone can help prove the following claim using elementary proof (no advanced number theory stuff)?

Given a sequence $a_1,a_2,\ldots,a_n$, if $\gcd(a_1,a_2,\ldots,a_n) = 1$, then there exists at least one pair $a_i,a_j$ for some $i,j\in\{1,2,\ldots,n\}$ with $i\neq j$ such that $\gcd(a_i,a_j)=1$.

Thank you!

$(6,10,15){}{}{}{}{}{}{}{}{}{}{}$

• Gcd(6, 10, 15) = 1. However, any two of those numbers have gcd greater than 1. Also, this is not a proof or an answer. – ThisIsNotAnId Jan 17 '16 at 5:32
• It is a counterexample for the "conjecture" – Jorge Fernández Hidalgo Jan 17 '16 at 5:42
• Oh right. My apologies, didn't think that through. – ThisIsNotAnId Jan 17 '16 at 5:43

More generally, this is also untrue:

Let $S$ be a finite subset of $\mathbb{Z}$. If the gcd of all elements of $S$ is $1$, then there exists a proper nonempty subset $T$ of $S$ such that the gcd of all elements of $T$ is $1$.

Nevertheless, this is true:

Let $S$ be an infinite subset of $\mathbb{Z}$ such that the gcd of all elements of $S$ is $1$. Then, there exists a finite nonempty subset $T$ of $S$ such that the gcd of all elements of $T$ is $1$. However, the minimum cardinality of such a subset $T$ can be arbitrarily large.

• For the first statement there are counterexample for $|S|=n$, for every $n>1$. Let $P=p_1\times p_2\dots p_n$ and let $S=\{b_1,b_2\dots b_n\}$, we define $b_i$ as $P/p_i$. – Jorge Fernández Hidalgo Jan 17 '16 at 4:53
• For the second one, pick a number $m\in S$. We can construct a subset of at most $\omega(m)+1$ elements with $\gcd$ equal to $1$. For each prime dividing $m$ take an integer in $S$ that is not divisible by that prime ( we can do so because the $\gcd$ of $S$ is $1$). – Jorge Fernández Hidalgo Jan 17 '16 at 4:55