What divisibility function is between GCD and LCM with three inputs

definitiondivisibilityelementary-number-theorygcd-and-lcmlattice-orders

It is known that, for positive integers, $\text{GCD}(x,y)\cdot\text{LCM}(x,y)=x\cdot y$. I wanted to generalize this to three variables:

$$\text{GCD}(x,y,z)\cdot F(x,y,z)\cdot\text{LCM}(x,y,z)=x\cdot y\cdot z.$$

What function $F$ would make this true? We could use this equation as a definition of $F$; but a better definition comes from prime factorization:

$$x=\prod_{\text{prime }p}p^{v_p(x)}$$

$$\text{GCD}(x,y,z)=\prod_{\text{prime }p}p^{\min(v_p(x),v_p(y),v_p(z))}$$

$$F(x,y,z)=\prod_{\text{prime }p}p^{\text{mid}(v_p(x),v_p(y),v_p(z))}$$

$$\text{LCM}(x,y,z)=\prod_{\text{prime }p}p^{\max(v_p(x),v_p(y),v_p(z))}$$

where, also by definition, $(x',y',z')=(\min(x,y,z),\text{mid}(x,y,z),\max(x,y,z))$ is a permutation of $(x,y,z)$ such that $x'\leq y'\leq z'$. Since $x'+y'+z'=x+y+z$, the triple product equation follows.

It also follows that the three functions have divisibility relations

$$\text{GCD}(x,y,z)|F(x,y,z)|\text{LCM}(x,y,z).$$

Now here's the question: Can $F$ be defined directly in terms of multiplication and divisibility relations, without using prime factorization or the division operation? (In particular, I want something that works when some of $x,y,z$ are $0$.)

The other two functions can be defined by

$$\text{GCD}(x,y,z)=\max\{w\mid w|x,w|y,w|z\}$$

$$\text{LCM}(x,y,z)=\min\{w\mid x|w,y|w,z|w\}$$

(and here $\max$ can mean either $w'\leq w$ or $w'|w$). But from the example

$$x=2^2\cdot3,\;y=3^2\cdot5,\;z=5^2\cdot2,$$

$$F(x,y,z)=2\cdot3\cdot5,$$

we see that $F(x,y,z)$ does not divide and is not divided by any of $x,y,z$.

Best Answer

According to this post (the 2nd and 3rd equations), we should have

$$F(x,y,z)=\frac{\text{GCD}(x,y)\text{GCD}(x,z)\text{GCD}(y,z)}{\text{GCD}(x,y,z)^2}$$

$$=\frac{\text{LCM}(x,y)\text{LCM}(x,z)\text{LCM}(y,z)}{\text{LCM}(x,y,z)^2};$$

this corresponds to the fact that

$$\text{mid}(x,y,z)=\min(x,y)+\min(x,z)+\min(y,z)-2\min(x,y,z)$$

$$=\max(x,y)+\max(x,z)+\max(y,z)-2\max(x,y,z).$$

But $\text{mid}$ is a purely order-theoretic function; it shouldn't depend on addition or subtraction. Indeed, this answer describes $\text{mid}$ in terms of $\max$ and $\min$. Here's a more symmetric expression:

$$\text{mid}(x,y,z)=\min(\max(x,y),\max(x,z),\max(y,z))$$

$$=\max(\min(x,y),\min(x,z),\min(y,z)).$$

Applied to the exponents in prime factorization, this gives a formula for $F$:

$$F(x,y,z)=\text{GCD}\Big(\text{LCM}(x,y),\text{LCM}(x,z),\text{LCM}(y,z)\Big)$$

$$=\text{LCM}\Big(\text{GCD}(x,y),\text{GCD}(x,z),\text{GCD}(y,z)\Big).$$

These dual expressions are sandwiched between the "meet" and "join" of $(x,y,z)$ in any lattice, and are equal in any distributive lattice.

Using the facts that $\text{LCM}(x,0)=0$ and $\text{GCD}(x,0)=x$, we get

$$F(x,y,0)=\text{LCM}(x,y)$$

$$F(x,0,0)=0$$

$$F(0,0,0)=0.$$


Generalizing to $n$ variables (and arbitrary lattices), we can define functions

$$\begin{align}F_1(x_1,\cdots,x_n)&=\text{GCD}\Big(\text{LCM}(x_1),\text{LCM}(x_2),\text{LCM}(x_3),\cdots,\text{LCM}(x_n)\Big) \\ F_2(x_1,\cdots,x_n)&=\text{GCD}\Big(\text{LCM}(x_1,x_2),\text{LCM}(x_1,x_3),\text{LCM}(x_2,x_3),\cdots,\text{LCM}(x_{n-1},x_n)\Big) \\ F_3(x_1,\cdots,x_n)&=\text{GCD}\Big(\text{LCM}(x_1,x_2,x_3),\cdots,\text{LCM}(x_{n-2},x_{n-1},x_n)\Big) \\ &\;\;\vdots \\ F_n(x_1,\cdots,x_n)&=\text{GCD}\Big(\text{LCM}(x_1,x_2,x_3,\cdots,x_n)\Big)\end{align}$$

and

$$\begin{align}G_1(x_1,\cdots,x_n)&=\text{LCM}\Big(\text{GCD}(x_1),\text{GCD}(x_2),\text{GCD}(x_3),\cdots,\text{GCD}(x_n)\Big) \\ G_2(x_1,\cdots,x_n)&=\text{LCM}\Big(\text{GCD}(x_1,x_2),\text{GCD}(x_1,x_3),\text{GCD}(x_2,x_3),\cdots,\text{GCD}(x_{n-1},x_n)\Big) \\ G_3(x_1,\cdots,x_n)&=\text{LCM}\Big(\text{GCD}(x_1,x_2,x_3),\cdots,\text{GCD}(x_{n-2},x_{n-1},x_n)\Big) \\ &\;\;\vdots \\ G_n(x_1,\cdots,x_n)&=\text{LCM}\Big(\text{GCD}(x_1,x_2,x_3,\cdots,x_n)\Big).\end{align}$$

It follows easily that

$$\text{GCD}=F_1\mid F_2\mid F_3\mid\cdots\mid F_n=\text{LCM}$$

and

$$\text{GCD}=G_n\mid G_{n-1}\mid\cdots\mid G_2\mid G_1=\text{LCM}.$$

Furthermore, $F_k=G_{n+1-k}$ in any distributive lattice. And for the special case of a total order, $(F_1,F_2,F_3,\cdots,F_n)$ is a permutation of $(x_1,x_2,x_3,\cdots,x_n)$.

Related Question