GCD equals GCD with Product of Coprime Factor

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b, c \in \Z$ be integers.

Let:

$a \perp b$

where $\perp$ denotes coprimality.


Then:

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

where $\gcd$ denotes greatest common divisor.


Proof

Let $a, b, c \in \Z$ such that $a$ is coprime to $b$.

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

We have:

\(\ds a\) \(\perp\) \(\ds b\)
\(\text {(1)}: \quad\) \(\ds \leadsto \ \ \) \(\ds \exists x, y \in \Z: \, \) \(\ds 1\) \(=\) \(\ds a x + b y\) Integer Combination of Coprime Integers
\(\ds \exists u, v \in \Z: \, \) \(\ds d\) \(=\) \(\ds c u + b v\) Bézout's Identity
\(\ds \leadsto \ \ \) \(\ds d\) \(=\) \(\ds \paren {a x + b y} \paren {c u + b v}\) from $(1)$
\(\ds \) \(=\) \(\ds a c u x + a b v x + b c u y + b^2 v x\) multiplying out
\(\ds \) \(=\) \(\ds a c \paren {u x} + b \paren {a v x + c u y + b v x}\) rearranging
\(\ds \) \(=\) \(\ds \gcd \set {a c, b}\) Bézout's Identity

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=GCD_equals_GCD_with_Product_of_Coprime_Factor&oldid=591618"