# What structure supports division to a unique quotient and remainder?

This has been bugging me for a while.

According to https://en.wikipedia.org/wiki/Euclidean_division, if I divide integer $a$ by integer $b$, I get unique $t$, $r$ such that $a = t b + r$, $0 \le r < b$.

Furthermore, for any Euclidean domain $R$, division with remainder can be defined as follows: $a = t b + r$, and either $r = 0$ or $f(r) < f(b)$. where $f$ is the euclidean function of $R$. $\mathbb{Z}$ fits into this classification by letting $f(n) = |n|$.

My problem with this "generalization" is that $t$ and $r$ need not be unique. Is there a classification for structures which support division with remainder where $t$ and $r$ are unique?

-
What do you mean by "$t$ and $r$ as defined above" for a general Euclidean domain? What does $0 \le r < b$ mean? –  Qiaochu Yuan Oct 16 '12 at 5:12
Modified question to clarify. –  Benjamin Braun Oct 16 '12 at 5:24
Yes, I've seen such a classification somewhere; if memory serves, this article is referred to in "Certain Number-Theoretic Episodes In Algebra" by Sivaramakrishnan. –  Franz Lemmermeyer Oct 16 '12 at 7:37

In [M. A. Jodeit, Jr., Uniqueness in the division algorithm, The American Mathematical Monthly 74 (1967), 835–836] it is shown that a Euclidean Domain in which quotient and remainder are strictly unique (for the integers there is a choice of sign) is either a field or a polynomial ring over a field.

-

A Euclidean domain is a ring such that there is (at least one) valuation function $f$ from the non-zero elements of $R$ to the non-negative integers so that for $a,b \in R$ with $b \ne 0_R$ we can write $a=bq+r$ for some $q,r$ with either $r=0$ or $f(r) \lt f(b).$ The valuation function is not part of the structure so I can imagine (but don't know) that there might be cases with more than one valuation and certain statements would be valid with respect to one but not the other. Maybe even a pair $q,r$ that works with one does not with the other. But one could discuss Euclidean Domains with distinguished valuation functions.

If $D=4k+1$ is a positive square free integer then the field $\mathbb{Q}[\sqrt D]$ has ring of integers $\mathcal{O}_D$ consisting of all $\alpha=u+v\frac{1+\sqrt D}{2}$ with the usual norm $f(\alpha)=|u^2-dv^2|.$ It is known when this $f$ shows that $\mathcal{O}_D$ a Euclidean domain, when $\mathcal{O}_D$ is a Euclidean Domain but that $f$ does not establish it, and when it is not a Euclidean Domain. Similar definitions exist for other algebraic extensions of $\mathbb{Q}$ and there are open questions. So even the question of classifying Euclidean Domains is open.

All this tip-toes around your question. Let me stick for now to the Gaussian integers $u+v\sqrt{-1}$ in $\mathbb{Q}[\sqrt{-1}]$ . We can think of these as the lattice points in the plane. Given Gaussian integers $a,b$ with $A$ not a multiple of $b$, we have $\frac{a}{b}$ in $\mathbb{Q}[\sqrt{-1}]$ a point which falls in some lattice square. Then we can take $q$ as any one of the corners and this gives $r.$ To choose $r$ uniquely we can have a rule such as $q$ should be the corner nearest the origin or the one nearest $\frac{a}{b}$ with a tie-breaker rule if needed. We could even pick our favorite ordering of the Gaussian Integers and pick $q$ (or $r$) as the first in our order. So uniqueness can be imposed in the countable case.

I think that what you really wonder about is not specific to Euclidean Domains. In a ring a unit is an element with a multiplicative inverse. $a,b$ are associates if $a=bu$ for some unit $u$. In the integers, the non-negative integers are closed under addition and multiplication (form a semiring) and contain exactly one member from each (two element) class of associates is a member.

So some starting questions are: For which rings $R$ does the multiplicative group decompose as $(R,\cdot)=PU$ where $U$ is the group of units and $P$ is a set of elements closed under addition or multiplication or both. I don't know the answer to that but perhaps it is very standard. Then one could go on to ask (in the case of Euclidean domains with this property): Is the set $P$ unique? When all this is true and $(R,f)$ is a Euclidean Domain with distinguished valuation function $f$, can the remainders $r$ always be taken to come from $P$ and, in that case, is the choice of $r \in P$ always unique?

-