Integer Coprime to Factors is Coprime to Whole/Proof 2
Jump to navigation
Jump to search
Theorem
Let $a, b, c \in \Z$ be integers.
Let:
- $a \perp b$
- $a \perp c$
where $\perp$ denotes coprimality.
Then:
- $a \perp b c$
In the words of Euclid:
(The Elements: Book $\text{VII}$: Proposition $24$)
Proof
Let $a, b, c \in \Z$ such that $a$ is coprime to each of $b$ and $c$.
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 a\) | \(\perp\) | \(\ds c\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists u, v \in \Z: \, \) | \(\ds 1\) | \(=\) | \(\ds a u + c v\) | Integer Combination of Coprime Integers | |||||||||
\(\ds \) | \(=\) | \(\ds \paren {a x + b y} \paren {a u + c v}\) | from $(1)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds a^2 u x + a c v x + a b y u + b c y v\) | multiplying out | |||||||||||
\(\ds \) | \(=\) | \(\ds a \paren {a u x + c v x + b y u} + b c \paren {y v}\) | rearranging | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds a\) | \(\perp\) | \(\ds b c\) | Integer Combination of Coprime Integers |
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $16 \ \text {(a)}$