# Division algorithm for multivariate polynomials?

We know that if $F$ is a field and $f(X)$ a non-zero polynomial in $F[X]$, then for every polynomial $g(X)$ we can find $q(X),r(X)$ such that $$g(X)=f(X)\cdot q(X)+r(X)$$ with $r(X)$ the zero polynomial or $\deg r(X)<\deg f(X)$. My question is: the same algorithm holds for many variables? So can i write $$g(X_1,\ldots,X_n)=f(X_1,\ldots,X_n)\cdot q(X_1,\ldots,X_n)+r(X_1,\ldots,X_n)$$

No, the polynomial division algorithm does not immediately generalize to multivariate rings. Here is a simple proof. Just as for $\rm\:\Bbb Z,\:$ a domain having an algorithm for division with smaller remainder, also enjoys Euclid's algorithm for gcds, which, in extended form, yields Bezout's identity. Therefore gcds have linear representation $\rm\:gcd(a,b) = r a + s b\:$ (i.e. Euclidean domains are Bezout). But this fails in multivariate polynomial rings $\rm\:F[x_1,\ldots, x_n],\ n \ge 2,\:$ since $\rm\:gcd(x_1,x_2) = 1\:$ but there is no Bezout equation $\rm\: 1 = x_1 f + x_2 g\$ (evaluating at $\rm\:x_1 = 0 = x_2\,$ $\Rightarrow$ $\rm\,1 = 0\:$ in $\rm\,F,\,$ contra field axioms).

But all Euclidean is not lost, since one can generalize the polynomial division algorithm in a way that recovers many of the important properties. For this, look up the Grobner basis algorithm, which may be viewed as a nonlinear generalization of the Euclidean/division algorithm and Gaussian elimination.

• Just to point out what I was missing at first: You can try to do polynomial division the way you are used to but then $deg\ r(X) < deg\ f(X)$ will not necessarily hold. Feb 29, 2016 at 14:21

If you can do Euclidean division in a reasonable sense in a domain $R$, then you can prove that $R$ is a principal ideal domain. This is not the case for the $F[x_{1}, \dots, x_{n}]$ for $n > 1$.

• so,suppose $f(b_1,\ldots,b_n)=0$. Can i say that $X_i-b_i$ divides $f$ for every $i=1,\ldots,n$? Feb 28, 2013 at 10:35
• $f(x_{1}, x_{2}) = (x_{1} - 1)^{2} + (x_{2} - 1)^{2} - 1$ has the root $(b_{1}, b_{2}) = (0, 1)$, but surely $x_{1}$ does not divide $f$, because the locus of $f$ does not contain the line $x_{1} = 0$. More generally, if $x-b_{1}$ divides $f(x_{1}, \dots, x_{n})$, then $f(b_{1}, a_{2}, \dots, a_{n}) = 0$ for all $a_{2}, \dots, a_{n}$, so the locus of $f$ contains the affine hyperplane $x_{1} = b_{1}$. Feb 28, 2013 at 10:45
• @Federica But there are extremely useful multivariate generalizations of the division algorithm, such as the Grobner basis algorithm - see my answer. Feb 28, 2013 at 16:47