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.

  • 2
    $\begingroup$ "Euclidean domain" is necessary and sufficient; see wiki. $\endgroup$ – vadim123 Feb 13 '16 at 23:40
  • $\begingroup$ @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. $\endgroup$ – Noble Mushtak Feb 13 '16 at 23:42
  • 1
    $\begingroup$ @NobleMushtak, although the coefficients are from a field, $K[X]$ is a ring, not a field. $\endgroup$ – vadim123 Feb 13 '16 at 23:44
  • $\begingroup$ @vadim123 Sorry. I thought the question was asking what the requirements were for $K$ given that $K[X]$ is a Euclidean domain. $\endgroup$ – Noble Mushtak Feb 13 '16 at 23:45
  • $\begingroup$ 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. $\endgroup$ – 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.

EDIT: Bonus answer!

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 just requires making some observations about norms and degrees to turn it into a proof.

  • $\begingroup$ 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$? $\endgroup$ – Noble Mushtak Feb 13 '16 at 23:41
  • 4
    $\begingroup$ @NobleMushtak There is nothing in the question that makes me think that that is the question. The example given is a polynomial ring, but it never once mentions the relationship between a ring and a polynomial ring. It specifically says "requirements on a ring" $\endgroup$ – Stella Biderman Feb 13 '16 at 23:43
  • 1
    $\begingroup$ Oh...I misread the question. I thought they were asking about $K[X]$ not $K$. Sorry! $\endgroup$ – Noble Mushtak Feb 13 '16 at 23:44
  • 1
    $\begingroup$ 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? $\endgroup$ – D. Zack Garza Feb 13 '16 at 23:48
  • 2
    $\begingroup$ @dzackgarza Yes it is. I added a sketch of the idea in my answer $\endgroup$ – Stella Biderman Feb 13 '16 at 23:49

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.