GCD times LCM equals product

Dependencies:

  1. PFEL of product is sum of PFEL
  2. PFEL of gcd is min of PFEL
  3. PFEL of lcm is max of PFEL

Dependencies:

  1. gcd(a1/d, a2/d, ..., an/d) = gcd(a1, a_2, ..., an)/d
  2. Product of coprime divisors is divisor
  3. LCM divides common multiple

Let $a$ and $b$ be positive numbers. Then $\gcd(a, b)\operatorname{lcm}(a, b) = ab$.

Proof

\begin{align} & \operatorname{PFEL}(\gcd(a, b)\operatorname{lcm}(a, b)) \\ &= \operatorname{PFEL}(\gcd(a, b)) + \operatorname{PFEL}(\operatorname{lcm}(a, b)) \\ &= \min(\operatorname{PFEL}(a), \operatorname{PFEL}(b)) + \max(\operatorname{PFEL}(a), \operatorname{PFEL}(b)) \\ &= \operatorname{PFEL}(a) + \operatorname{PFEL}(b) \\ &= \operatorname{PFEL}(ab) \end{align}

Therefore, $\gcd(a, b)\operatorname{lcm}(a, b) = ab$.

Alternate Proof

Let $g = \gcd(a, b)$ and $l = \operatorname{lcm}(a, b)$.

\[ (a \mid l \wedge b \mid l) \implies \left( \frac{a}{g} \mid \frac{l}{g} \wedge \frac{b}{g} \mid \frac{l}{g} \right) \] \[ \gcd\left( \frac{a}{g}, \frac{b}{g} \right) = \frac{\gcd(a, b)}{g} = 1 \] Since product of coprime divisors is also a divisor, \[ \frac{a}{g}\frac{b}{g} \mid \frac{l}{g} \implies ab \mid lg \]

\[ \frac{ab}{g} = a\left(\frac{b}{g}\right) = \left(\frac{a}{g}\right)b \] Therefore, $\frac{ab}{g}$ is a common multiple of $a$ and $b$. Therefore, \[ l \mid \frac{ab}{g} \implies lg \mid ab \]

Since $ab \mid lg$ and $lg \mid ab$, $lg = ab$. Therefore, $\gcd(a, b)\operatorname{lcm}(a, b) = ab$.

Dependency for:

  1. Zm × Zn is isomorphic to Zmn iff m and n are coprime

Info:

Transitive dependencies:

  1. Every number has a prime factorization
  2. Integer Division Theorem
  3. GCD is the smallest Linear Combination
  4. Common divisor divides GCD
  5. gcd(a1/d, a2/d, ..., an/d) = gcd(a1, a_2, ..., an)/d
  6. Euclid's lemma
  7. Fundamental Theorem of Arithmetic
  8. Prime Factorization Exponent List (PFEL)
  9. PFEL of ratio is difference of PFEL
  10. PFEL of product is sum of PFEL
  11. Divisible iff PFEL is less than or equal
  12. PFEL of lcm is max of PFEL
  13. PFEL of gcd is min of PFEL
  14. LCM divides common multiple
  15. Product of coprime divisors is divisor