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