I am trying to show that $\gcd(a,\operatorname{lcm}(b,c))=\operatorname{lcm}(\gcd(a,b),\gcd(a,c))$.

If $d=\gcd(a,\operatorname{lcm}(b,c))$, then $d=ax-my$, where $m=\operatorname{lcm}(b,c)$. So $d=ax-b(ky)$ and $d=ax-c(ly)$, which means that $\gcd(a,b)|d$ and $\gcd(a,c)|d$, or $d$ is a common multiple.

But I wasn't able to show that it is the smallest common multiple.

  • 2
    $\begingroup$ You may find it easier to work with Unique Factorization, and characterization of gcd, lcm in terms of max, min of exponents. $\endgroup$ – André Nicolas May 22 '12 at 0:05
  • $\begingroup$ @AndréNicolas: This come before that. $\endgroup$ – spohreis May 22 '12 at 0:10
  • 1
    $\begingroup$ This is just the fact that the natural numbers is a distributive lattice with respect to divisibility, where gcd and lcm are meet and join. $\endgroup$ – lhf May 22 '12 at 0:15
  • 1
    $\begingroup$ This is proven en passant by me in this question and by Bill Dubuque in the same post. The equality is equivalent to proving that $\gcd(a,b,c)\gcd(ab,ac,bc) = \gcd(a,b)\gcd(a,c)\gcd(b,c)$. I use primes, but Bill proves it using the universal properties and the formula $ab={\rm lcm}(a,b)\gcd(a,b)$ alone. $\endgroup$ – Arturo Magidin May 22 '12 at 0:31
  • $\begingroup$ lcm and gcd distribute over each other, in the same way that multiplication distributes over addition (but not vice-versa). That's how this is expressed in the language of modern algebra. $\endgroup$ – Michael Hardy May 22 '12 at 2:25

Since you say you cannot use the simple min/max exponents proof via unique factorization, here is a proof that uses only universal gcd laws (so will work in any gcd domain). We simply eliminate all lcms by $\rm\:[x,y] = xy/(x,y),\:$ and apply gcd laws (distributive, commutative, associative, etc).

$$\rm\begin{eqnarray} \rm &\rm\qquad\qquad (a,[b,c])\ &=&\rm\ [(a,b),(a,c)] \\ \rm \iff&\rm\qquad\quad \left(a,\dfrac{bc}{(b,c)}\right)\ & =&\rm\ \dfrac{(a,b)(a,c)}{(a,b,c)} \\ \iff &\rm (a,b,c)(a(b,c),bc)\ &=&\rm\ (a,b)(a,c)(b,c) \end{eqnarray}$$

which is true since both sides $\rm = (aab,aac,abb,abc,acc,bbc,bcc)\:$ by distributivity etc.

If you are not proficient with gcd laws, you may find it helpful to rewrite the proof employing a more suggestive arithmetical notation, namely denoting the gcd $\rm (a,b)\:$ by $\rm\ a \dot+ b.\:$ Because the arithmetic of GCDs shares many of the same basic laws of the arithmetic of integers, the proof becomes much more intuitive using a notation highlighting this common arithmetical structure. Below is a sample calculation comparing the two notations.

$$\rm\begin{eqnarray} \rm(a,\:b)\ (a,\:c) &=&\rm (a(a,\!\:c),b(a,\!\:c)) &=&\rm ((aa,ac),\:(ba,bc)) &=&\rm (aa,ac,\:\!ba,\:bc) \\ \rm\ (a\dot+ b)(a\dot+c) &=&\rm a(a\dot+c)\dot+b(a\dot+c) &=&\rm (aa\dot+ac)\dot+(ba\dot+bc) &=&\rm aa\dot+ac\dot+ba\dot+bc \end{eqnarray}$$

  • $\begingroup$ :) I was waiting for you to answer. Could you expand on the last step where you say it is true by the distributive law? It is not clear to me. $\endgroup$ – user17762 May 22 '12 at 0:56
  • 2
    $\begingroup$ E.g. $\rm\:(a,b)(a,c) = (a(a,c),b(a,c)) = ((aa,ac),(ba,bc)) = (aa,ac,ba,bc).\:$ It's more intuitive if you write the gcd's using additive notation, i.e. plus signs vs. commas, e.g. see here. $\endgroup$ – Bill Dubuque May 22 '12 at 1:03
  • $\begingroup$ Ok. Nice. +1. Essentially, $n(a,b) = (na,nb)$. Thanks. $\endgroup$ – user17762 May 22 '12 at 1:05
  • $\begingroup$ @Marvis I added an example in the answer. $\endgroup$ – Bill Dubuque May 22 '12 at 1:39
  • $\begingroup$ Thanks. It was clear from the previous comment itself. $\endgroup$ – user17762 May 22 '12 at 1:40

See if this post from PhysicsForums helps at all, the two problems seem somewhat interchangeable.


  • 1
    $\begingroup$ Note that the linked proofs all use unique factorization (min/mx on exponents), which the OP wishes to avoid. $\endgroup$ – Bill Dubuque May 22 '12 at 1:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.