The problem statement is as follows:
The least common multiple of $2$ nonzero integers, $a,b$, denoted $\text{lcm}(a,b)$ is the smallest positive integer n so that $$a \mid n\ \text{and}\ b\mid n$$Prove that $ab = \text{gcd}(a,b)\text{lcm}(a,b)$
Hint: Express both in terms of the prime factorizations of $a$ and $b$
Summary of my attempt/thought process below
Specific questions in last section
To start, I've written the prime factorizations as: $$a = p^{n_1}_1 \cdots p^{n_k}_k$$ $$b = q^{m_1}_1 \cdots q^{m_s}_s$$ Where $q,p$ prime and $n_i, m_j \in \mathbb{Z}_{+}$. So that, $$ab = p^{n_1}_1 \cdots p^{n_k}_k \cdot q^{m_1}_1 \cdots q^{m_s}_s$$ Which we could reindex so that for any $p_i = q_j$ we take $p_i^{n_i + m_j}$ where we take (without loss of generality) $k < s$ so that we have $$ab = p_1^{n_1 + m_1} \cdots p_k^{n_k + m_k} \cdot q_l^{m_l} \cdots q_s^{m_s}$$ Where $q_p$ are the prime factors such that $q_p \neq p_i$ for any $i,p \in \mathbb{Z}_+$
Note that $\text{gcd}(a,b)$ is the smallest positive integer of the set $\mathcal{M} = \{ma + na \mid m,n \in \mathbb{Z} \}$. Hence there exist $m_0, n_0 \in \mathbb{Z}$ such that $$\text{gcd}(a,b) = d = m_0a + n_0b = m_0(p^{n_1}_1 \cdots p^{n_k}_k) + n_0(q^{m_1}_1 \cdots q^{m_s}_s)$$
Now, the only exposure in the text we've had to the $\text{lcm}(a,b)$ is exactly the content of the problem statement. Given the properties of the $\text{lcm}(a,b) = c$ we know that $$c = m_0'a = m'_0(p^{n_1}_1 \cdots p^{n_k}_k)$$ $$c = n'_0 b = n'_0(q^{m_1}_1 \cdots q^{m_s}_s)$$
Looking up an algorithm to find $\text{lcm}(a,b)$, I discern that to find $\text{lcm}(a,b)$ one must:
- Write out the prime factorization of both integers in question.
- Count the prime factors and add each unique factor to the "list"
- Whenever both integers have the same prime base then consider the base raised to the highest power and add that one to the "list"
- Multiply each element of the list together to find the least common multiple.
I know this is a bit disorganized but I'm just trying to lay out all that I know about these concepts and trying to tie them together to prove the proposition but am not seeing the full picture. I imagine I probably don't need the algorithm in order to solve as the text should be fully contained and so all I should need to know about the least common multiple is what's said in the problem statement. I'm having trouble making this into a usable expression that when multiplied with the expression for the greatest common divisor gives us $ab$. Any help is greatly appreciated!
Let $m=gcd(a,b)$ and $M=lcm(a,b)$. Then $a=k_1m$ and $b=k_2m$ where $k_1$ and $k_2$ are coprime. On the other hand, $M=n_1a=n_2b$ where $n_1$ and $n_2$ are as small as possible. Substituting $a=k_1m$ and $b=k_2m$ we have $$ M = n_1k_1m=n_2k_2m. $$ The condition that $n_1$ and $n_2$ be as small as possible combined with the fact that $k_1$ and $k_2$ are coprime implies $n_1=k_2$ and $n_2=k_1$. So $$ gcd(a,b)lcm(a,b)= mM = m(n_1a) = m(k_2a)=a(k_2m) = ab. $$