# In general, when does a ring have a division algorithm?

I'm working through Herstein's "Abstract Algebra" text, and am currently working through section 5.

Theorem 4.5.5 introduces the division algorithm for polynomial rings over fields, which states:

Given the polynomial $f(x), g(x) \in F[x]$, where $g(x) \neq 0$, then $$f(x) = q(x)g(x) + r(x),$$ where $q(x), r(x) \in F[x]$ and $r(x) = 0$ or $\deg r(x) < \deg g(x).$

What requirements must be put on a ring to ensure a division algorithm exists? It seems that the existence of some kind of norm is necessary (in this case, the $\deg$ function).

In other words, does the division algorithm hold, say, in any integral domain? Or do you need a unique factorization domain, or perhaps a principle ideal domain instead? My thought is that it almost certainly holds in any Euclidean domain, but I'm wondering if this is too strong of a requirement.

• "Euclidean domain" is necessary and sufficient; see wiki. – vadim123 Feb 13 '16 at 23:40
• @vadim123 In the examples of Euclidean domains from the Wikipedia article, "$K[X]$, the ring of polynomials over a field $K$." Field is necessary and sufficient. I'm writing a proof for this right now. – Noble Mushtak Feb 13 '16 at 23:42
• @NobleMushtak, although the coefficients are from a field, $K[X]$ is a ring, not a field. – vadim123 Feb 13 '16 at 23:44
• @vadim123 Sorry. I thought the question was asking what the requirements were for $K$ given that $K[X]$ is a Euclidean domain. – Noble Mushtak Feb 13 '16 at 23:45
• I don't think the question really is about division-algebras, so I removed the tag. It is unavoidable that some terms have a more advanced technical meaning in math. That's why I recommend reading tag wikis before using them. – Jyrki Lahtonen Feb 24 '16 at 9:02

A Euclidean Domain is usually defined to be an integrals domain in which there is a division algorithm. Whatever definition you had should be equivalent to this. It turns out that every Euclidean Domain is a Primitive Ideal Domain, and every Primitive Ideal Domain is a Unique Factorization Domain, but the other direction for both statements is false.

One commenter was under the impression that you were asking "Let $R$ be a ring. What conditions on $R$ ensure that $R[x]$ has a division algorithm." For this question, the answer is that it's necessary and sufficient for $R$ to be a field.
Essentially, you need to be able to decrease the degree of a polynomial via division algorithm, but since the remainder term cannot influence the leading coefficient, this means that the leading coefficient of $f(x)$ must equal the leading coefficient of $q(x)g(x)$. It should be clear that this is always possible if and only if $R$ is a field. Otherwise, you could pick the leading coefficient of $f(x)$ to be non-invertible and the leading coefficient of $g(x)$ to be an element that doesn't divide the leading coefficient of $f(x)$.
• This doesn't answer the question. If you have a ring $K$ such that $K[X]$ is a Euclidean domain, then what is are the necessary and sufficient conditions for $K$? – Noble Mushtak Feb 13 '16 at 23:41
• Oh...I misread the question. I thought they were asking about $K[X]$ not $K$. Sorry! – Noble Mushtak Feb 13 '16 at 23:44
• Ah yep, I was asking about the ring itself. But I'd definitely be interested in how to work backwards when $K[x]$ is a Euclidean domain! In that case, is it absolutely necessary that $K$ is a field? – D. Zack Garza Feb 13 '16 at 23:48