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.
 A: 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.
A: 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$.
A: 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.
