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.

Solution 1:

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].

Solution 2:

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.

Solution 3:

$\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)$.