7
$\begingroup$

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
    You may find it easier to work with Unique Factorization, and characterization of gcd, lcm in terms of max, min of exponents.2012-05-22
  • 0
    @AndréNicolas: This come before that.2012-05-22
  • 1
    This is just the fact that the natural numbers is a [distributive lattice](http://en.wikipedia.org/wiki/Distributive_lattice) with respect to divisibility, where gcd and lcm are meet and join.2012-05-22
  • 1
    This is proven *en passant* by me [in this question](http://math.stackexchange.com/a/132264/742) and by [Bill Dubuque](http://math.stackexchange.com/a/132297/742) 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.2012-05-22
  • 0
    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.2012-05-22

2 Answers 2

7

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}$$

  • 0
    :) 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.2012-05-22
  • 2
    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.](http://math.stackexchange.com/a/20904)2012-05-22
  • 0
    Ok. Nice. +1. Essentially, $n(a,b) = (na,nb)$. Thanks.2012-05-22
  • 0
    @Marvis I added an example in the answer.2012-05-22
  • 0
    Thanks. It was clear from the previous comment itself.2012-05-22
1

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

http://www.physicsforums.com/showthread.php?t=50060

  • 1
    Note that the linked proofs all use unique factorization (min/mx on exponents), which the OP wishes to avoid.2012-05-22