LCM equals Product iff Coprime
Jump to navigation
Jump to search
Theorem
Let $a, b \in \Z_{>0}$ be strictly positive integers.
Then:
- $\lcm \set {a, b} = a b$
- $a$ and $b$ are coprime
where $\lcm$ denotes the lowest common multiple.
Proof
Necessary Condition
Let $a$ and $b$ be coprime.
Then:
\(\ds \lcm \set {a, b}\) | \(=\) | \(\ds \frac {a b} {\gcd \set {a, b} }\) | Product of GCD and LCM | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {a b} 1\) | Definition of Coprime Integers | |||||||||||
\(\ds \) | \(=\) | \(\ds a b\) |
$\Box$
Sufficient Condition
Let $\lcm \set {a, b} = a b$.
Then:
\(\ds \lcm \set {a, b} \gcd \set {a, b}\) | \(=\) | \(\ds a b\) | Product of GCD and LCM | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \gcd \set {a, b}\) | \(=\) | \(\ds \frac {a b} {\lcm \set {a, b} }\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \gcd \set {a, b}\) | \(=\) | \(\ds \frac {a b} {a b}\) | by hypothesis | ||||||||||
\(\ds \) | \(=\) | \(\ds 1\) |
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm