# Unique expression of a polynomial under quotient mapping?

Suppose $f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$ is a polynomial over a field $F$. Let $y=x+(f(x))$ be the image of $x$ in the quotient $F[x]/(f(x))$. Then every element of $F[y]$ can be uniquely expressed in form $$b_0+b_1y+\cdots+b_{n-1}y^{n-1}$$ with $b_i\in F$.

I see that $$y^n = x^n+(f(x)) = -(a_{n-1}x^{n-1}+\cdots+a_1x+a_0)+(f(x))\\ = -a_{n-1}x^{n-1}+(f(x))+\cdots+-a_1x+(f(x))+-a_0+(f(x))$$

so it looks like any power of $y$ greater or equal to $n$ can be written in terms of lower powers of $y$ if I could pull out the coefficients. However, why would the coefficients still be in $F$? Wouldn't they be somewhere else? And does uniqueness of this expression follow simply because the expressions $b_0+b_1y+\cdots+b_{n-1}y^{n-1}$ are polynomials, or is there something more to it than that? Thanks.

-
You have done it, at least for $x^n$. For the next one, just multiply by $x$, substitute for the $x^n$ term you get. This is the heart of the induction step. In the same way, one shows that if $y^k$ is expressible as a linear combination, so is $y^{k+1}$. The uniqueness is easy, two polynomials of degree $\le n-1$ whose difference is divisible by $f$ must be the same. –  André Nicolas Jul 9 '12 at 23:47
Hint: by the division algorithm $\rm\ g = q\, f + r\$ with $\rm\: deg\ r < deg\ f.\$ The existence and uniqueness of the remainder $\rm\,r\,$ (and quotient $\rm\,q)$ is analogous to that for division (with remainder) for integers. What do you mean by the coefficients "being somewhere else"? –  Bill Dubuque Jul 9 '12 at 23:52

The map $$\pi:F[x]\longrightarrow F[x]/(f(x))\,\,,\,\,\pi(g(x)):=g(x)+(f(x))$$ is a ring homomorphism under which the field $\,F\,$ is embedded in the field $$\overline F:=\{a+(f(x))\;\:\;a\in F\}$$ Thus, we can, and we actually do, identify the elements of both fields, and under this agreement is that we can say the coefficients you ask about are in $\,F\,$, i.e. in $\,\overline F\,$.

About uniqueness: we know we can divide $\,h(x)\in F[x]\,$, by $\,f(x)\,$ with residue (since we're in an Euclidean domain we can always do this!): $$h(x)=q(x)f(x)+r(x)\,\,,\,\,r(x)=0\,\,or\,\,\deg r<\deg f\,\,\,\,(**)$$ Uniqueness follows from degree considerations: $$q(x)f(x)+r(x)=q'(x)f(x)+r'(x)\Longrightarrow (q(x)-q'(x))f(x)=r'(x)-r(x)$$ but if $\,q(x)-q'(x)\neq 0\,$ then $\,\deg\left(q'(x)-q(x)\right)f(x)\geq f(x)>\deg(r'(x)-r(x))\,$ which, of course, contradicts $\,(**)\,$ above.

The only thing left to do is to observe that $$g(x)+(f(x))=r(x)+(f(x))$$

-
It is not true that the quotient and remainder are always unique in a Euclidean domain. –  Bill Dubuque Jul 10 '12 at 3:04
It is, I think, true in this case as we're in a polynomial ring over a field. Please feel free to correct me if I'm wrong. –  DonAntonio Jul 10 '12 at 3:42
Yes, but your remark above can be read as implying that such uniqueness holds true in any Euclidean domain. Perhaps you could reword that to avoid such. –  Bill Dubuque Jul 10 '12 at 3:57
I don't follow: what remark? I wrote we can do this (divide with residue) since we're in an Euclidean Domain, and the uniqueness wasn't implied in this as afterwards I go on to show uniqueness...Anyway, I think the point is clear now. Thanks. –  DonAntonio Jul 10 '12 at 10:17
The statement "we can divide uniquely with residue (since we're in a Euclidean domain we can always do this!)" is highly likely to be interpreted to mean that the emphasized uniqueness follows from the emphasized Euclideanness. Since this is a common false belief, I pointed it out in the hope that you might reword it, so to avoid propagating this error. If you don't have the time to correct this then I will be happy to lend a hand. –  Bill Dubuque Jul 10 '12 at 17:22

Hint $\$ By the polynomial (long) Division Algorithm in $\rm\:F[x]\:$ we can divide any $\rm\:g\in F[x]\:$ by $\rm\:f\:$ yielding $\rm\ g = q\, f + r\$ with $\rm\: deg\ r < deg\ f.\$ The uniqueness of the remainder $\rm\,r\,$ follows just as for integers: if $\rm\ q\, f + r = g = q'\, f + r'\,$ then $\rm\,(q-q')\,f = r-r'\:$ so $\rm\,r-r' = 0,\,$ else $\rm\:f\:$ would divide the smaller degree $\rm\,r-r'\ne 0.$

-

Hint: Use the Division Algorithm for polynomials. Any polynomial $g(x)$ is congruent modulo $f(x)$ to a unique polynomial $r(x)$, where $r(x)=0$ or $r(x)$ has degree less than the degree of $f(x)$.

Alternately and somewhat more painfully, you have shown the result for $y^n$. Then do an induction, by writing down explicitly the expression for $y^{k+1}$ from the assumed expression for $y^k$.

-