1
$\begingroup$

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!

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ThisIsNotAnId Jan 17 '16 at 5:32
  • $\begingroup$ It is a counterexample for the "conjecture" $\endgroup$ – Jorge Fernández Hidalgo Jan 17 '16 at 5:42
  • $\begingroup$ Oh right. My apologies, didn't think that through. $\endgroup$ – ThisIsNotAnId Jan 17 '16 at 5:43
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jorge Fernández Hidalgo Jan 17 '16 at 4:53
  • $\begingroup$ 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$). $\endgroup$ – Jorge Fernández Hidalgo Jan 17 '16 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.