Is gcd the right adjoint of something?

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

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