GCD with One Fixed Argument is Multiplicative Function

From ProofWiki
Jump to navigation Jump to search

Theorem

Let:

$a, b, c \in \Z: b \perp c$

where $b \perp c$ denotes that $b$ is coprime to $c$.


Then:

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

That is, GCD is multiplicative.


Proof

\(\ds \gcd \set {a, b c}\) \(=\) \(\ds \gcd \set {a, \lcm \set {b, c} }\) LCM equals Product iff Coprime
\(\ds \) \(=\) \(\ds \lcm \set {\gcd \set {a, b}, \gcd \set {a, c} }\) GCD and LCM Distribute Over Each Other
\(\ds \) \(=\) \(\ds \frac {\gcd \set {a, b} \gcd \set {a, c} } {\gcd \set {\gcd \set {a, b}, \gcd \set {a, c} } }\) Product of GCD and LCM
\(\ds \) \(=\) \(\ds \frac {\gcd \set {a, b} \gcd \set {a, c} } {\gcd \set {a, \gcd \set {b, \gcd \set {a, c} } } }\) Greatest Common Divisor is Associative
\(\ds \) \(=\) \(\ds \frac {\gcd \set {a, b} \gcd \set {a, c} } {\gcd \set {a, \gcd \set {\gcd \set {b, c}, a} } }\) Greatest Common Divisor is Associative
\(\ds \) \(=\) \(\ds \frac {\gcd \set {a, b} \gcd \set {a, c} } {\gcd \set {a, \gcd \set {1, a} } }\) Definition of Coprime Integers
\(\ds \) \(=\) \(\ds \frac {\gcd \set {a, b} \gcd \set {a, c} } {\gcd \set {a, 1} }\)
\(\ds \) \(=\) \(\ds \frac {\gcd \set {a, b} \gcd \set {a, c} } 1\)
\(\ds \) \(=\) \(\ds \gcd \set {a, b} \gcd \set {a, c}\)

$\blacksquare$