Product of Coprime Factors

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b, c \in \Z$ such that $a$ and $b$ are coprime.

Let both $a$ and $b$ be divisors of $c$.


Then $a b$ is also a divisor of $c$.

That is:

$a \perp b \land a \divides c \land b \divides c \implies a b \divides c$


Proof

We have:

$a \divides c \implies \exists r \in \Z: c = a r$
$b \divides c \implies \exists s \in \Z: c = b s$


So:

\(\displaystyle a\) \(\perp\) \(\displaystyle b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists m, n \in \Z: m a + n b\) \(=\) \(\displaystyle 1\) Integer Combination of Coprime Integers
\(\displaystyle \leadsto \ \ \) \(\displaystyle c m a + c n b\) \(=\) \(\displaystyle c\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle b s m a + a r n b\) \(=\) \(\displaystyle c\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a b \paren {s m + r n}\) \(=\) \(\displaystyle c\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a b\) \(\divides\) \(\displaystyle c\)

$\blacksquare$


Sources