2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +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. $\endgroup$ – Jyrki Lahtonen Apr 28 '13 at 9:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.