## Divisibility

There is an interesting preorder we can put on the nonzero elements of any commutative ring with unit. If and are nonzero elements of a ring , we say that divides — and write — if there is an so that . The identity trivially divides every other nonzero element of .

We can easily check that this defines a preorder. Any element divides itself, since . Further, if and then there exist and so that and , so and we have .

On the other hand, this preorder is almost *never* a partial order. In fact since and we see that and , and most of the time . In general, when both and we say that and are associates. Any unit comes with an inverse , so we have and . If for some unit , then and are associates because .

We can pull a partial order out of this preorder with a little trick that works for any preorder. Given a preorder we write if both and . Then we can check that defines an equivalence relation on , so we can form the set of its equivalence classes. Then descends to an honest partial order on .

One place that divisibility shows up a lot is in the ring of integers. Clearly and are associate. If and are positive integers with , then there is another positive integer so that . If then . Otherwise . Thus the only way two positive integers can be associate is if they are the same. The preorder of divisibility on induces a partial order of divisibility on .

Now, there is a neat trick. I don’t run across preorders nearly as much as I run across partial orders, but from your post I gather that they are partial orders where a

Comment by Nick Bornak | April 28, 2007 |

As my first post on orders said, a preorder is reflexive and transitive, and a partial order adds antisymmetry. What I left out there is that you can build a partial order from a preorder like I do here. It’s actually another example of the same sort of thing as all those “free” constructions I did for groups and rings and such, and I’ll unify all of them a little later.

Comment by John Armstrong | April 28, 2007 |

Oh, how embarrassing. There was more to my comment, but I accidentally used > and *poof*.

Anyway, my real question was: if we throw away commutativity, do people still talk about left- and right-divisibility? Maybe they call it something else.

Comment by Nick Bornak | April 28, 2007 |

It’s perfectly possible, yeah. Technically you don’t even need a unit to write down the condition. It’s not even a preorder then, since an element need not divide itself.

In fact I seriously considered doing it in full generality, but it complicates things to no end. By far the most common application is to divisibility of natural numbers, since for more general rings you can do it all with ideals anyway.

Comment by John Armstrong | April 28, 2007 |

[...] Now we know that we can talk about divisibility in terms of ideals, we remember a definition from back in elementary school: a number is [...]

Pingback by Prime Ideals « The Unapologetic Mathematician | May 18, 2007 |

[...] differ by multiplication by a unit, and so each divides the other. This sort of thing happens in the divisibility preorder for any ring. For polynomials, the units are just the nonzero elements of the base field, [...]

Pingback by Euclid’s Algorithm for Polynomials « The Unapologetic Mathematician | August 5, 2008 |