# Is gcd the right adjoint of something?

In his answer link to the question whether $a|m$ and $a+1|m$ implies $a(a+1)|m$, Bill Dubuque takes a detour to derive the equality $$\gcd(a,b)=ab/\mathrm{lcm}(a,b)$$ from the universal property of $\gcd$ and $\mathrm{lcm}$. Since they have a universal property, the natural question is: is $\gcd$ the right adjoint of something and is $\mathrm{lcm}$ the left adjoint of something?

Originally, the question was meant as: does the functor $\gcd:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ has a left adjoint. This was answered by Qiaochu Yuan by observing that $\gcd$ is a categorical product.

Hurkyl had interpreted my question as: does the functor $\gcd(-,b):\mathbb{N}\to\mathbb{N}$ have a left adjoint for each $b\in\mathbb{N}$? This is not the case, but interestingly the functor $\mathrm{lcm}(-,b):\mathbb{N}\to\mathbb{N}$ has a left adjoint. This shows that if we reverse the ordering of divisibility, the category $\mathbb{N}$ becomes cartesian closed.

-
I don't have time to give a good answer now, but to get you started google "Yoneda's Lemma" and posets, etc, which, e.g. yields an introduction here by Tott Trimble: Toward Stone Duality: Posets and Meets. I'd be very grateful if others could post here links on this and related topics, since it would be useful to have an answer to link to when related questions touch on these universal ideas. –  Bill Dubuque May 21 '12 at 21:18
Accepting an answer very quickly often discourages others from answering, e.g. many experts only browse the unanswered questions. It's usually a good idea to wait at least a day or two before accepting any answer, so that most members will have had a chance to see your question. You can unaccept (and reaccept later), and that is not considered impolite (per prior meta discusson). This might lead to some other answers from different viewpoints. I'd certainly be interested in seeing other viewpoints. –  Bill Dubuque May 21 '12 at 22:00
Note: readers may also find of interest the universal view of the floor function (which I suspect inspired this question). See also this question on Yoneda's Lemma. –  Bill Dubuque May 24 '12 at 21:26
In one sentence: gcd is supremum in poset $(\mathbb N, |)$, and suprema in posets are products in categories, and products are limits, and limits are adjoints to diagonal functors. –  sdcvvc Jun 2 '12 at 1:33

Well, as far as category theory goes, it is a categorical product (and $\text{lcm}$ is a categorical coproduct) in the category whose objects are the natural numbers where there is a single arrow $a \to b$ if $a | b$.

All limits and colimits are adjoints. If $C$ is a category and $J$ a diagram category, then the diagonal inclusion $C \to C^J$ sending every object $c \in C$ to the constant functor $J \to C$ with value $c$ potentially has a left and right adjoint, and these are the limit and colimitcolimit and limit respectively when they exist.

-
It is indeed the other way around. The mnemonic is, right adjoints preserve limits – so the formation of colimits can't be a right adjoint, since those don't usually commute with limits! –  Zhen Lin May 21 '12 at 21:20

Here's an explicit left adjoint $L$ to lcm in the poset of natural numbers ordered by divisibility.

I define $L(a,b)$ in terms of its valuation at each prime: $$v_p(L(a,b)) = \begin{cases} 0 & v_p(a) \leq v_p(b) \\ v_p(a) & v_p(b) < v_p(a) \end{cases}$$

To verify it is a left adjoint:

• $L(a,b) \mid c$
• iff $\forall p: v_p(a) \leq v_p(b) \vee v_p(a) \leq v_p(c)$
• iff $a \mid \mathop{\mathrm{lcm}}(b,c)$

It's sort of a weird function, and I don't think I've seen it before, but there it is!

I computed it by fixing $a,b$ and looking at the requirement

• $L(a,b) \mid c$ if and only if $a \mid \mathop{\mathrm{lcm}}(b,c)$

I picked the smallest value for $c$ that made the right hand side true, which gives an upper bound on $L(a,b)$. Then, I checked that actually defining that upper bound to be $L(a,b)$ works.

There isn't a right adjoint to $\mathop{\mathrm{gcd}}$; my intuition attributes that to the fact that there is no upper bound on things. The proof is short: the condition is

• $\mathop{\mathrm{gcd}}(a,b) \mid c$ if and only if $a \mid R(b,c)$

For a fixed $b,c$, we can pick arbitrarily large values of $a$ relatively prime to $b$, which makes the left hand side true. This contradicts the fact that $R(b,c)$ would be an upper bound on the set of values for $a$, and so $R(b,c)$ cannot exist.

-
I think I don't fully understand the functions $v_p$ and how you construct $L$ in terms of it. So you proved that $\mathrm{lcm}(-,b)$ has a left adjoint; in other words, that the dual of $(\mathbb{N},|)$ is cartesian closed? –  Egbert May 22 '12 at 6:53
Is $L(a,b)=\mathrm{lcm}(a,b)/b$? –  Egbert May 22 '12 at 7:31
$v_p(x)$ is the number of times the prime $p$ divides $x$. So, $v_2(18) = 1$ and $v_3(18) = 2$. A sample value of $L$ is $L(12,18) = 4$. It has this value because $2$ is the only prime that divides $12$ more than it does $18$, and it does so twice. –  Hurkyl May 22 '12 at 8:50
Ok, I get it. But I believe that the assertion in the second item should read: iff $\forall p: v_p(a)\leq v_p(b)\vee v_p(a)\leq v_p(c)$. –  Egbert May 22 '12 at 12:48
I've made the fix. –  Hurkyl May 22 '12 at 16:10