Relation between primeness and co-primeness of integers

I wonder what this stunning formal analogy between the definitions of being co-prime (for two integers) and being prime (for one integer) might reveal – and how:

$\alpha, \beta$ are co-prime iff

$$(\forall x)\ \alpha|x \wedge \beta|x \leftrightarrow \alpha\beta|x$$

$\alpha$ is prime iff

$$(\forall xy)\ \alpha|x \vee \alpha|y \leftrightarrow \alpha|xy$$

Note that and how the two definitions are equivalent modulo swapping

• $\wedge$ and $\vee$ on the left side

• constants and variables on the right side together with

• the direction of divisibility $|$ with respect to the product _{[thanks to user Wojowu]}

• the direction of inference $\rightarrow$ _{[thanks to user Roll up and smoke Adjoint]}

Solution 1:

In the poset category of integers dividing one another we write sometimes write $\alpha \to x$ instead of $\alpha \mid x$.

The "product" $\alpha \beta$ of two coprime objects $\alpha, \beta$ is such that $\alpha \to \alpha \beta \leftarrow \beta$ and for any object $x$ such that $\alpha \to x \leftarrow \beta$ then there is a unique arrow $\alpha \beta \to x$. That is precisely the definition of coproduct in a general category.

Thus when $\alpha, \beta$ are coprime, then the category definitely has a coproduct for them.

Thus $\wedge$ is encoded in the fact that $\alpha \to x \leftarrow \beta$, ie. both morphisms exist simultaneously. I believe product is $\gcd(\alpha, \beta)$.

Actually, it turns out that the coproduct exists for any two integers and it's $\text{lcm}(\alpha, \beta)$.

Primality is difficult because of the $\vee$. So create a new definition. An arrow into a coproduct is prime when there exists a morphism into at least one of the coproduct's components such tha the relevant triangle commutes.

Notice we used coproduct here which is $\text{lcm}(\alpha, \beta)$ since the definition of prime is equivalent to $p \mid \text{lcm}(\alpha, \beta) \implies p \mid \alpha \vee p \mid \beta$.

So take the contrapositive of that. $p \nmid \alpha \wedge p \nmid \beta \implies p \nmid \text{lcm}(\alpha, \beta)$.

Form the "negated" poset category of integers not dividing one another. It's formed by mapping each hom-set to $\varnothing$ when it's nonempty and vise-versa, so it's not a functor from the original category.