_Posted on April 21, 2024_ ##### Introduction By the [[Fundamental Theorem of Arithmetic|FTA]], note that an integer $a$ can be expressed uniquely as $\Pi_{k=1}^{\infty}p_k^{m_k}$, where $p_k$ is prime and $m_k$ are non-negative integers. The sequence $(p_k)$ consists of all prime numbers in increasing order. For only finitely many $k$, $m_k \neq 0$, reflecting that $a$ has finitely many prime factors. ##### Prerequisites > [!theorem] **Theorem:** For two integers $a = \Pi_{k=1}^{\infty}p_k^{\alpha_k}$ and $b = \Pi_{k=1}^{\infty}p_k^{\beta_k}$, $a \mid b$ if and only if $\alpha_k \leq \beta_k$ for all $k$. Proof: Suppose, for the sake of contradiction, that this were not the case. Thus, $a \mid b$, but there exists a $k$ such that $\alpha_k > \beta_k$. Since $a \mid b$, $b = n(\Pi_{k=1}^{\infty}p_k^{\alpha_k})$ for some $n = \Pi_{k=1}^{\infty}p_k^{\nu_k}$. Thus, $b = \Pi_{k=1}^{\infty}p_k^{\alpha_k + \nu_k}$. By the FTA, $\alpha_k + \nu_k = \beta_k$ for all $k$. This directly contradicts our assumption that $\alpha_k > \beta_k$ for some $k$. Conversely, suppose that $\alpha_k \leq \beta_k$ for all $k$. For each $k$, let $\nu_k = \beta_k - \alpha_k$. Since $\nu_k \geq 0$ for all $k$, we can express some $n$ as $n = \Pi_{k=1}^{\infty}p_k^{\nu_k}$. It follows that $b = \Pi_{k=1}^{\infty}p_k^{\alpha_k + \beta_k - \alpha_k)} = \Pi_{k=1}^{\infty}p_k^{\alpha_k + \nu_k} = n(\Pi_{k=1}^{\infty}p_k^{\alpha_k}) = na.$Thus $a \mid b$ $\blacksquare$ Now, we define the least common multiple as $\text{LCM}(a,b) = m$ if and only if: 1. $a \mid m$ and $b \mid m$ 2. $a \mid \mu$ and $b \mid \mu$ implies that $m \mid \mu$. ##### Statement and proof > [!theorem] **Theorem:** For $a = \Pi_{k=1}^np_k^{\alpha_k}$, and $b = \Pi_{k=1}^np_k^{\beta_k}$. $\text{LCM}(a,b) = \Pi_{k=1}^np_k^{\text{max}(\alpha_k,\beta_k)}$, and $\text{GCD}(a,b) = \Pi_{k=1}^np_k^{\text{min}(\alpha_k,\beta_k)}$. Additionally, $\text{GCD}(a,b)\cdot \text{LCM}(a,b) = ab$. Proof: Let $m = \Pi_{k=1}^np_k^{\text{max}(\alpha_k,\beta_k)}$. We now check that it satisfies the above conditions. For (1), observe that for each $k$, $\alpha_k \leq \text{max}(\alpha_k,\beta_k)$ and $\beta_k \leq \text{max}(\alpha_k,\beta_k)$ by definition of $\text{max}$. Now, for (2) let $\mu = \Pi_{k=1}^np_k^{\gamma_k}$. Suppose that $a \mid \mu$ and $b \mid \mu$. For all $k$, we thus have $\alpha_k \leq \gamma_k$ and $\beta_k \leq \gamma_k$ which obviously implies that $\text{max}(\alpha_k, \beta_k) \leq \gamma_k$. By the definition of $\text{LCM}$, we have the first part of our result. A very similar argument establishes the result for $\text{GCD}(a, b)$ $\blacksquare$