LCM of 3 Integers in terms of GCDs of Pairs of those Integers/Lemma

From ProofWiki
Jump to navigation Jump to search


Let $a, b, c \in \Z_{>0}$ be strictly positive integers.


$\gcd \set {\gcd \set {a, b}, \gcd \set {a, c} } = \gcd \set {a, b, c}$


Let $\gcd \set {a, b, c} = d_1$.

From definition:

$d_1 \divides a$, $d_1 \divides b$ and $d_1 \divides c$.

By Common Divisor Divides GCD:

$d_1 \divides \gcd \set {a, b}$ and $d_1 \divides \gcd \set {a, c}$.

By Common Divisor Divides GCD again:

$d_1 \divides \gcd \set {\gcd \set {a, b}, \gcd \set {a, c} }$.

On the other hand, let $\gcd \set {\gcd \set {a, b}, \gcd \set {a, c} } = d_2$.

From definition:

$d_2 \divides \gcd \set {a, b}$ and $d_2 \divides \gcd \set {a, c}$.

From definition again:

$d_2 \divides a$, $d_2 \divides b$ and $d_2 \divides c$.

Hence $d_2 \divides \gcd \set {a, b, c}$.

Since $\gcd \set {\gcd \set {a, b}, \gcd \set {a, c} }$ and $\gcd \set {a, b, c}$ divide each other, by Absolute Value of Integer is not less than Divisors they must be equal.