# The Unapologetic Mathematician

## Divisibility

There is an interesting preorder we can put on the nonzero elements of any commutative ring with unit. If $r$ and $s$ are nonzero elements of a ring $R$, we say that $r$ divides $s$ — and write $r|s$ — if there is an $x\in R$ so that $rx=s$. The identity $1$ trivially divides every other nonzero element of $R$.

We can easily check that this defines a preorder. Any element divides itself, since $r1=r$. Further, if $r|s$ and $s|t$ then there exist $x$ and $y$ so that $rx=s$ and $sy=t$, so $r(xy)=t$ and we have $r|t$.

On the other hand, this preorder is almost never a partial order. In fact since $r(-1)=-r$ and $-r(-1)=r$ we see that $r|-r$ and $-r|r$, and most of the time $r\neq-r$. In general, when both $r|s$ and $r|s$ we say that $r$ and $s$ are associates. Any unit $u$ comes with an inverse $u^{-1}$, so we have $u|1$ and $1|u$. If $r=su$ for some unit $u$, then $r$ and $s$ are associates because $s=ru^{-1}$.

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

One place that divisibility shows up a lot is in the ring of integers. Clearly $n$ and $-n$ are associate. If $m$ and $n$ are positive integers with $m|n$, then there is another positive integer $x$ so that $mx=n$. If $x=1$ then $m=n$. Otherwise $m\lneq n$. Thus the only way two positive integers can be associate is if they are the same. The preorder of divisibility on $\mathbb{Z}^\times$ induces a partial order of divisibility on $\mathbb{N}^+$.

April 28, 2007 - Posted by | Ring theory

1. 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 | Reply

2. 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 | Reply

3. 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 | Reply

4. 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 | Reply

5. [...] 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 | Reply

6. [...] 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 | Reply