# 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]

• Note you also swap the direction of divisibility. This is an interesting observation, but I don't think there is any "stunning" meaning behind it. – Wojowu Nov 2 '18 at 19:28
• Note that you can also replace $\rightarrow$ with $\leftrightarrow$ since each of those propositions on either side are in isomorphism with one another. – BananaCats Category Theory App Nov 3 '18 at 3:29
• There is most likely a nice interpretation in the language of lattices/filters. – Slade Nov 3 '18 at 9:05
• In the poset category for integers dividing one another $\text{Hom}(X,Y)$ consists of a single point or is empty. Let $(X \mid Y)$ denote the nonempty hom-set. Notice that multiplication by an element $\alpha \in \Bbb{Z}$ is a functor from the poset category to itself since $(X \mid Y) \implies (\alpha X \mid \alpha Y)$ and so on proves the functoriality of multiplication. – BananaCats Category Theory App Nov 4 '18 at 6:34

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.

The second can become:$$(\forall xy)\alpha\mid xy\to\alpha\mid x\lor\alpha\mid y$$ The first is: $$(\forall x)\alpha\beta\nmid x \to \alpha\nmid x \lor \beta\nmid x \lor \alpha\beta \gt x\lor(\alpha,\beta)^2\nmid x$$ Not sure it reveals much though.