Online Course Discussion Forum

Math challenge I-A homework

 
 
ProfessorAreteem的头像
Re: Math challenge I-A homework
ProfessorAreteem - 2020年04月1日 Wednesday 11:51
 

There's two approaches you can follow for this problem:

1) Let $m = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ and $n = p_1^{f_1} \cdot p_2^{f_2} \cdots p_k^{f_k}$ be two positive integers (and their prime factorizations). Then $$\text{lcm} (m,n) = p_1^{\max(e_1,f_1)}\cdot p_2^{\max(e_2,f_2)}\cdots p_k^{\max(e_k,f_k)}$$ and $$\gcd (m,n) = p_1^{\min(e_1,f_1)}\cdot p_2^{\min(e_2,f_2)}\cdots p_k^{\min(e_k,f_k)}.$$ For example, $48 = 2^4 \cdot 3 \cdot 5^0$ and $180 = 2^2 \cdot 3^2 \cdot 5$, so $$\text{lcm}(48,180) = 2^4 \cdot 3^2\cdot 5 = 720$$ and $$\gcd(48,180) = 2^2\cdot 3 \cdot 5^0 = 12.$$ So you can look at the prime factorizations of the given numbers to figure out the prime factorization of the missing number.

2) From what we have above, it is easy to check that for any two integers $m$ and $n$ it is always true that $$m\cdot n = \text{lcm}(m,n) \cdot \gcd(m,n).$$