◀ ▲ ▶Branches / Number-theory / Proof

Proof

(related to Proposition: Factorization of Greatest Common Divisor and Least Common Multiple)

• Assume, Let $n,m\in\mathbb N$ with $n\ge 1,$ $m\ge 1$ have the factorizations $n=\prod_{i=1}^\infty p_i^{e_i}$ and $m=\prod_{i=1}^\infty p_i^{f_i}.$
• We set $d:=\prod_{i=1}^\infty p_i^{\min(e_i,f_i)}$, $\min(e_i,f_i)$ being the minimum of the respective exponents $e_i,f_i.$
  • It is clear that $d\mid n$ is a divisor of $n,$ because $\min(e_i,f_i)\le e_i$ and $\min(e_i,f_i)\le f_i$ for all $i.$
  • For any other divisor $t\mid a$ and $t\mid b$ with the factorization $d:=\prod_{i=1}^\infty p_i^{r_i}$ we have therefore $r_i\le \min(e_i,f_i)$ for all $i.$
  • Therefore, $t\mid d$ and we have that $d$ equals the greatest common divisor $d=\gcd(n,m).$
• Analogously, we set $l:=\prod_{i=1}^\infty p_i^{\max(e_i,f_i)}$, $\max(e_i,f_i)$ being the maximum of the respective exponents $e_i,f_i.$
  • It is clear that $n\mid l$, i.e. $l$ is a multiple of $n.$ This is because $\max(e_i,f_i)\ge e_i$ and $\max(e_i,f_i)\ge f_i$ for all $i.$
  • For any other multiple $m$ of $n$ with the factorization $m:=\prod_{i=1}^\infty p_i^{s_i}$ we have therefore $s_i\ge \max(e_i,f_i)$ for all $i.$
  • Therefore, $l\mid m$ and we have that $l$ equals the least common multiple $m=\operatorname{lcm}(n,m).$
    ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Scheid Harald: "Zahlentheorie", Spektrum Akademischer Verlag, 2003, 3rd Edition
2. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927