# Uniqueness of $q$ and $r$ of Division Algorithm doesn't hold in a general Euclidean Domain?

I heard that in a general Euclidean Domain, the quotient $q$ and remainder $r$ when an element $a$ is divided by an element $b$ by Division Algorithm, may not be unique. Is it true? If yes, can anyone give me examples where such a thing happens.

## 3 Answers

The ring of Gaussian integers $$\mathbb{Z}[i]$$ is a Euclidean domain with the complex norm in the role of the function measuring the size of elements. There we have plenty of examples. For example, take $$a=3$$ and $$b=1+i$$. Do we write the division step as $$3=(1-i)\cdot(1+i)+1,$$ i.e. $$q=1-i$$ and $$r=1$$, or $$3=(2-i)\cdot(1+i)-i,$$ i.e. $$q=2-i$$ and $$r=-i$$ or some other way (there are two more possibilities with $$r=-1$$ and $$r=i$$).

The problem is that the size function does not in general order the elements. Even in $$\mathbb{Z}$$ we get the following kind of non-uniqueness ($$a=3, b=2$$) $$3=2\cdot2-1=1\cdot2+1$$ unless we specify that the remainder $$r$$ must be non-negative. In a more general Euclidean domain there is no such thing as a set of positive elements, so we have no choice but to give up on that requirement.

You do get uniqueness of $$q$$ and $$r$$ in the important case of a polynomial ring over a field. The degree of a polynomial is a very well-behaved function in this sense.

It is almost never unique. If $u$ is any unit, then usually $a$ and $u \cdot a$ have the same degree. Thus there are far more than $d$ elements of degree $<d$. Even in $\mathbb{Z}$, there are $2d-1$ elements of degree $<d$.

• +1 for the key observation that the number of small elements exceeds the number of cosets of the ideal generated by the divisor (in the cases where these numbers are finite). A much better explanation than my mumbling about singling out positive remainders. – Jyrki Lahtonen Apr 28 '13 at 9:43

Not much is demanded of the size function $$\lambda$$ for a Euclidean domain. In particular, we may have $$\lambda(x+y)>\max\{\lambda(x),\lambda(y)\}$$. This is crucial to the question of uniqueness in the divisional algorithm, which can be rephrased as asking whether some equation $$\begin{equation}\tilde r = \varphi g+r \end{equation}$$ has a nontrivial solution $$\varphi$$, given $$g\ne 0$$ and $$\max\{\lambda(\tilde r),\lambda(r)\}<\lambda(g)$$.

For polynomial rings over integral domains, we always have $$\deg(\tilde r-r)\le\max\{\deg(\tilde r),\deg(r)\}$$, and $$\deg(\varphi g) \ge \deg(g)$$, so if the division algorithm yields some solution, then it must be unique.