Set of Integers with GCD of 1 are not necessarily Pairwise Coprime
Jump to navigation
Jump to search
Theorem
Let $S$ be a set of integers such that $S$ has more than $2$ elements:
- $S = \set {s_1, s_2, \ldots, s_n}$
Let:
- $\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
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.
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm