Set of Integers with GCD of 1 are not necessarily Pairwise Coprime

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a set of integers such that $S$ has more than $2$ elements:

$S = \set {s_1, s_2, \ldots, s_n}$


$\map \gcd S = 1$

where $\gcd$ denotes the GCD of $S$.

Then it is not necessarily the case that there exist a pair of elements of $S$ which are themselves pairwise coprime:

$\exists i, j \in \set {1, 2, \ldots, n}: \gcd \set {s_i, s_j} = 1$


Proof by Counterexample

Let $S = \set {6, 10, 15}$.

We have:

\(\ds \gcd \set {6, 10}\) \(=\) \(\ds 2\)
\(\ds \gcd \set {6, 15}\) \(=\) \(\ds 3\)
\(\ds \gcd \set {10, 15}\) \(=\) \(\ds 5\)

Hence the result.