# Relating $\operatorname{lcm}$ and $\gcd$

I would appreciate help to show this equality is valid: $\operatorname{lcm} (u, v) = \gcd (u^{- 1}, v^{- 1})^{- 1}$, where $u, v$ are elements of a field of fractions.

In the text it is stated that lcm is: there is an element $m$ in K for which $u| x$ and $v| x$ is equivalent to $m| x$

It goes on to say sending $t$ to $t^{- 1}$ in K reverses divisibility. So the proof of the existence of lcm's reduces to the proof of the existence of gcd's.

Then from the relation I am asking about above, one obtains $\operatorname{lcm} (u,v)\gcd (u,v) = uv$

I know independently how to show $\operatorname{lcm} (u,v)\gcd (u,v) = uv$. But the text I am looking at uses the first to show the second.

Thanks.

-
In what context are you taking the gcd of $u^{-1}$ and $v^{-1}$? If $u$ is invertible, then it is a unit, so it divides everything and only units divide it, same for $v$, so that $\gcd(u^{-1},v^{-1})$ would necessarily be $1$. So you must mean something other than the standard definition of $\gcd$. What do you mean? –  Arturo Magidin May 14 '12 at 16:09
In addition to @ArturoMagidin's comment, also 1 is a multiple of $u$ and $v$ if they are invertible. So the equation does make sense but for trivial reasons. –  Simon Markett May 14 '12 at 16:11
However, you may mean "gcd" in terms of a largest "common measure", as per Euclid. That is, if $u$ and $v$ are integers, then you are looking for the largest rational of the form $\frac{1}{a}$ such that $\frac{1}{u}$ and $\frac{1}{v}$ are integer multiples of $\frac{1}{a}$. Is that what you mean? –  Arturo Magidin May 14 '12 at 16:13
@Arturo Magidin You're right, I should have said u,v are elements of a field of fractions, K. Will fix that. To be honest, I don't know if that will answer what you pose. –  Andrew May 14 '12 at 16:14
My understanding is that $\gcd$ and $\operatorname{lcm}$ can be uniquely extended from a ring to its field of fractions with their multiplicative properties (e.g. $\gcd(ac,bc)=c\gcd(a,b)$). But to use the first equation to go to the second seems strangely backwards. –  anon May 14 '12 at 16:14

I'm going to assume that you have a domain $D$, and are looking at the field of fractions as a $D$-module. You are now looking for multiples and divisors but only $D$-multiples. That is, letting $D$ be the domain and $F$ be the field of fractions, we define:

Let $a,b\in F$. We say $x\in F$ is a least common multiple of $a$ and $b$ if and only if:

1. There exist $r,s\in D$ such that $ra=x$ and $sb=x$; and
2. If $y\in F$ is such that there exist $u,v\in D$ with $ua=y$ and $vb=y$, then there exists $t\in D$ such that $xt=y$.

Note well: we are only talking about "$D$-multiples". If we take $D=\mathbb{Z}$ and $F=\mathbb{Q}$, this would be the equivalent of saying that $a$ and $b$ "measure" $x$, and that $x$ measures any number that is measured by both $a$ and $b$ (in the sense of Euclid).

Similarly,

Let $a,b\in F$. We say that $d\in F$ is a greatest common divisor of $a$ and $b$ if and only if:

1. There exist $r,s\in D$ such that $rd=a$ and $sd=b$; and
2. If $c\in F$ is such that there exist $u,v\in D$ with $uc=a$ and $vc=b$, then there exists $t\in D$ such that $tc=d$.

Note again: We are talking about "$D$-divisors" only. Again, in the language of Euclid, this means that $d$ "measures" both $a$ and $b$, and that any common measure of $a$ and $b$ "measures" $d$.

Now, suppose that $d$ is a gcd for $a^{-1}$ and $b^{-1}$. We are trying to show that $d^{-1}$ is a least common multiple of $a$ and $b$.

Since there exist $r,s\in D$ with $rd = a^{-1}$ and $sd=b^{-1}$, we see that $ra=d^{-1}$ and $sb=d^{-1}$, so $d^{-1}$ is a common $D$-multiple of $a$ and $b$. Now suppose that $c$ is a common $D$-multiple of $a$ and $b$. Then there exist $x,y\in D$ such that $ax=c$ and $by=c$. Therefore $c^{-1}x = a^{-1}$ and $c^{-1}y=b^{-1}$, so $c^{-1}$ is a common $D$-divisor of $a^{-1}$ and $b^{-1}$. Since $d$ is a gcd for $a^{-1}$ and $b^{-1}$, it follows that there exists $z\in D$ such that $zc^{-1}=d$, and therefore $zd^{-1}=c$. Thus, $c$ is a $D$-multiple of $d^{-1}$.

This proves that $d^{-1}$ is a least common multiple of $a$ and $b$, under these definitions. That is, we have shown that $$\mathrm{lcm}(a,b) = \gcd(a^{-1},b^{-1})^{-1}$$ as desired.

Added. More generally, as noted by Bill Dubuque in this old sci.math post, we have:

Theorem. Let $a,b,c,d\in D$. If $\gcd(a,b)=\gcd(c,d)=1$, then $$\gcd\left(\frac{a}{b},\frac{c}{d}\right) = \frac{\gcd(a,c)}{\mathrm{lcm}(b,d)}.$$

In the case at hand, assuming $u$ and $v$ are in $D$, we have $a=1$, $c=1$, $b=u$, $d=v$, so we obtain $$\gcd\left(\frac{1}{u},\frac{1}{v}\right) = \frac{\gcd(1,1)}{\mathrm{lcm}(u,v)}$$ which gives the result as well.

-
@ArturoMagidinThanks very much. –  Andrew May 14 '12 at 17:03
@Andrew Yes. Fixed. –  Arturo Magidin May 14 '12 at 18:06

Below is a proof that works in any GCD domain, using the universal definitions of GCD, LCM. These ideas go back to Euclid, who defined the greatest common measure of line segments. Nowadays this can be viewed more generally in terms of fractional ideals or Krull's $v$-ideals.

Theorem $\rm\ \ \ \left(\dfrac{a}b,\,\dfrac{A}B\right)\: =\: \dfrac{(a,A)}{[b,B]}\ \$ if $\rm\ \ (a,b) = 1 = (A,B),\ \$ where $\rm\ \ \begin{eqnarray} (a,b) &:=&\rm\ gcd\rm(a,b)\\\ \rm [a,b]\, &:=&\rm\ lcm(a,b)\end{eqnarray}$

Proof
$\rm\begin{eqnarray} &\rm\quad c &|&\rm a/b,\,A/B \\ \quad\iff&\rm Bbc &|&\rm\ aB,\,Ab \\ \iff&\rm Bbc &|&\rm (aB,\,\color{#C00}A\color{#0A0}b) \\ \iff&\rm Bbc &|&\rm (aB,\, (\color{#C00}A,aB)\,(\color{#0A0}b,aB))\ \ &\rm by\quad (x,\color{#C00}y\color{#0A0}z) = (x,\,(\color{#C00}y,x)\,(\color{#0A0}z,x)),\ \ see\ [1] \\ \iff&\rm Bbc &|&\rm (aB,\, (A,a)\, (b,B))\ \ &\rm by\quad (a,b) = 1 = (A,B) \\ \iff&\rm Bbc &|&\rm (a,A)\,(b,B)\ \ &\rm by\quad (A,a)\ |\ a,\ (b,B)\ |\ B \\ \iff&\rm\quad c &|&\rm (a,A)/[b,B]\ \ &\rm by\quad (b,B)\:[b,B] = bB, \ \ see\ [2] \end{eqnarray}$

Here are said links to proofs of the gcd laws used: law [1] and law [2].

-

$\newcommand{\lcm}{\operatorname{lcm}}$Here is the way I usually show $ab = \lcm(a,b)\gcd(a,b)$. Inequality $(2)$ uses that we are working in an integral domain. Without something like that, the argument seems circular.

First notice that $\frac{ab}{\gcd(a,b)} = a(\frac{b}{\gcd(a,b)}) = b(\frac{a}{\gcd(a,b)})$ is a common multiple of $a$ and $b$. By the minimality of the $\lcm$, $\frac{ab}{\gcd(a,b)} \ge \lcm(a,b)$. That is $$ab \ge \lcm(a,b)\gcd(a,b)\tag{1}$$ By division, we can write $ab = q\lcm(a,b) + r$ where $0 \le r < \lcm(a,b)$. Because $ab$ and $\lcm(a,b)$ are common multiples of $a$ and $b$, so is $r$. By the minimality of the $\lcm$, $r = 0$. Therefore, $\lcm(a,b)$ divides $ab$. Notice that $\frac{ab}{\lcm(a,b)} = \frac{a}{\lcm(a,b)/b} = \frac{b}{\lcm(a,b)/a}$ is a common divisor of $a$ and $b$. By the maximality of the $\gcd$, $\frac{ab}{lcm(a,b)} \le \gcd(a,b)$. That is $$ab \le \lcm(a,b)\gcd(a,b)\tag{2}$$ Combining $(1)$ and $(2)$, we get $ab = \lcm(a,b)\gcd(a,b)$.

-
@RobjohnThanks for your answer. As I mentioned, I can do this. What I was trying to see is the relation I am asking about. If I am not mistaken, going from what you show is probably doable. But the text goes the other way. –  Andrew May 14 '12 at 16:46
@andrew: so the question was how to extend gcd and lcm to rationals. I apologize for missing that. –  robjohn May 14 '12 at 17:15
@RobjohnNo need - I appreciate anything anyone does for others here. –  Andrew May 14 '12 at 17:29