I want to show that for $m,n,x \in \mathbb{Z}$, \begin{align*} \textrm{LCM}\left(\textrm{GCD}\left(m,x\right),\textrm{GCD}\left(n,x\right)\right) = \textrm{GCD}\left(\textrm{LCM}\left(m,n\right),x\right) \end{align*} I have proven that $\textrm{LCM}\left(\textrm{GCD}\left(m,x\right),\textrm{GCD}\left(n,x\right)\right)$ divides $\textrm{GCD}\left(\textrm{LCM}\left(m,n\right),x\right)$. But I had difficulty in proving the other way around. The only solution that I've come up with is this: \begin{align*} \textrm{Let} \quad \textrm{ } m &= p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}\\ n &= p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k} \quad \textrm{ and }\\ x &= p_1^{\gamma_1}p_2^{\gamma_2}\ldots p_k^{\gamma_k} \end{align*} where $p_i$'s are all the primes of $m,n$ & $x$ and $\alpha_i$'s, $\beta_i$'s & $\gamma_i$'s are non negative integers. Then we know that \begin{align*} \textrm{LCM}(m,n) &= p_1^{\max(\alpha_1,\beta_1)}p_2^{\max(\alpha_2,\beta_2)}\ldots p_k^{\max(\alpha_k,\beta_k)}\\ \textrm{GCD}(m,x) &= p_1^{\min(\alpha_1,\gamma_1)}p_2^{\min(\alpha_2,\gamma_2)}\ldots p_k^{\min(\alpha_k,\gamma_k)}\\ \textrm{GCD}(n,x) &= p_1^{\min(\beta_1,\gamma_1)}p_2^{\min(\beta_2,\gamma_2)}\ldots p_k^{\min(\beta_k,\gamma_k)} \end{align*} Thus \begin{align*} &\textrm{LCM}\left(\textrm{GCD}\left(m,x\right),\textrm{GCD}\left(n,x\right)\right) = p_1^{\delta_1}p_2^{\delta_2}\ldots p_k^{\delta_k}\\ &\textrm{ where } \delta_i = \max(\min(\alpha_i,\gamma_i),\min(\beta_i,\gamma_i)) \quad \forall i = 1,2,\ldots,k \end{align*} and \begin{align*} &\textrm{GCD}\left(\textrm{LCM}\left(m,n\right),x\right) = p_1^{\eta_1}p_2^{\eta_2}\ldots p_k^{\eta_k}\\ &\textrm{ where } \eta_i = \min(\max(\alpha_i,\beta_i),\gamma_i) \quad \forall i = 1,2,\ldots,k \end{align*} Then $\forall$ $i = 1,2,\ldots,k$ \begin{align*} \eta_i &= \min(\max(\alpha_i,\beta_i),\gamma_i)\\ \Rightarrow \eta_i &\leq \max(\alpha_i,\beta_i) \quad \textrm{and} \quad \eta_i \leq \gamma_i\\ \Rightarrow \eta_i &\leq \alpha_i \textrm{ or } \eta_i \leq \beta_i \quad \textrm{and} \quad \eta_i \leq \gamma_i \quad \textrm{ Since } \max(\alpha_i,\beta_i) = \alpha_i \textrm{ or }\beta_i\\ \Rightarrow \eta_i &\leq \alpha_i \textrm{ and } \gamma_i \quad \textrm{or} \quad \eta_i \leq \beta_i \textrm{ and } \gamma_i\\ \Rightarrow \eta_i &\leq \min(\alpha_i,\gamma_i) \quad \textrm{or} \quad \eta_i \leq \min(\beta_i,\gamma_i)\\ \Rightarrow \eta_i &\leq \max(\min(\alpha_i,\gamma_i),\min(\beta_i,\gamma_i)) = \delta_i\\ \Rightarrow p_i^{\eta_i} &\textrm{ divides } p_i^{\delta_i} \end{align*} which tells us that $\textrm{GCD}\left(\textrm{LCM}\left(m,n\right),x\right)$ divides $\textrm{LCM}\left(\textrm{GCD}\left(m,x\right),\textrm{GCD}\left(n,x\right)\right)$.

Can someone cross verify this proof; whether or not is it correct ?

  • 2
    $\begingroup$ Why don't prove $\min(\max(\alpha,\beta),\gamma)=\max(\min(\alpha,\gamma),\min(\beta,\gamma)$? $\endgroup$ – user26857 Nov 10 '18 at 17:01
  • $\begingroup$ Here is a more general proof without using primes. $\endgroup$ – Bill Dubuque Nov 10 '18 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.