Is gcd the right adjoint of something?

Question

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?

---

A note about the answers below

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.

Answer 1

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.

Answer 2

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.