A Taste of Modern Algebra: Remainder Theorem for Polynomials

Introduction

In high school curriculum we are taught the "Remainder Theorem" as one of the important results of Algebra. The theorem and its proof are quite simple, but the practical application and theoretical ramifications of this result are quite interesting. To recall, the theorem is stated as follows:

Remainder Theorem: If $ f(x) = a_{0}x^{n} + a_{1}x^{n - 1} + \cdots + a_{n - 1}x + a_{n}$ is a polynomial with real coefficients then the remainder obtained on dividing $ f(x)$ by $ (x - a)$ is $ f(a)$.

To prove this we can write $ f(x) = q(x)(x - a) + r$ using division algorithm for polynomials where $ q(x)$ is the quotient and $ r$ is the remainder (note that since the degree of remainder must be less than degree of divisor $ (x - a)$, this must be a constant). Putting $ x = a$ in the above equation we get $ r = f(a)$.

As an example the remainder when $ x^{3} - 2x^{2} + 5x + 3$ is divided by $ (x - 2)$ is $ 2^{3} - 2\cdot 2^{2} + 5 \cdot 2 + 3 = 13$.

Also as a corollary of the theorem we have the result:
If $f(x)$ is a polynomial with real coefficients and $ f(a) = 0$ for some real number $ a$, then $ (x - a)$ is a factor of polynomial $ f(x)$.

This is used frequently to factor polynomials of higher degree using hit and trial. We should note that the theorem will remain valid even if we replace the phrase "real coefficients" with "rational coeffcients" or "complex coefficients". In fact the theorem holds true for polynomials over any field.

We will now think about the remainder theorem in a different way and provide a different proof.

Congruences of Polynomials

Let $ f(x), g(x)$ be polynomials over some field $ F$ and let $ p(x)$ be a polynomial of positive degree over $ F$. We say that $ f(x)$ is congruent to $ g(x)$ modulo $ p(x)$ if $ (f(x) - g(x))$ is divisible by $ p(x)$. This is exactly the same concept as the modular arithmetic of integers and turns out to be very fruitful in theoretical investigations.

We also write $ f(x) \equiv g(x) \pmod{p(x)}$ in this case. It is easily seen that the congruence of polynomials for a given modulus is an equivalence relation. It is also clear that if $ r(x)$ is the remainder when $ f(x)$ is divided by $ p(x)$ then $ f(x) \equiv r(x) \pmod{p(x)}$. The following properties of congruences are obvious and straightforward:

If $ f(x) \equiv a(x) \pmod{p(x)}$ and $ g(x) \equiv b(x) \pmod{p(x)}$ then

• $ k\cdot f(x) \equiv k\cdot a(x) \pmod{p(x)}$
• $ f(x) + g(x) \equiv a(x) + b(x) \pmod{p(x)}$
• $ f(x)g(x) \equiv a(x)b(x) \pmod{p(x)}$

Now it is trivial that $ x \equiv a \pmod{(x - a)}$ and by above properties $ x^{n} \equiv a^{n} \pmod{(x - a)}$ and further $$ a_{0}x^{n} + a_{1}x^{n - 1} + \cdots + a_{n - 1}x + a_{n} \equiv a_{0}a^{n} + a_{1}a^{n - 1} + \cdots + a_{n - 1}a + a_{n} \pmod{(x - a)}$$ i.e $ f(x) \equiv f(a) \pmod{(x - a)}$ where $ f(x)$ is a polynomial. This proves the Remainder Theorem.

The advantage of this approach is that it can be used to generalize the Remainder Theorem. Let's take an example. Suppose we are required to find the remainder when $ x^{4} + 2x + 1$ is divided by $ x^{2} + x + 1$. Then for brevity we write $ p(x) = x^{2} + x + 1$ and we have \begin{align} x^{2} + x + 1 &\equiv 0 \pmod{p(x)}\notag\\ \Rightarrow x^{2} &\equiv (-x - 1) \pmod{p(x)}\notag\\ \Rightarrow (x^{2})^{2} &\equiv (-x - 1)^{2} \pmod{p(x)}\notag\\ \Rightarrow x^{4} &\equiv x^{2} + 2x + 1 \pmod{p(x)}\notag\\ &\equiv (-x - 1) + 2x + 1 \pmod{p(x)}\notag\\ \Rightarrow x^{4} &\equiv x \pmod{p(x)}\notag\\ \Rightarrow x^{4} + 2x + 1 &\equiv 3x + 1 \pmod{p(x)}\notag \end{align} Hence the desired remainder is $ 3x + 1$. More generally if $$ p(x) = b_{0}x^{m} + b_{1}x^{m - 1} + \cdots + b_{m - 1}x + b_{m}$$ with $ b_{0} \neq 0$ and $ f(x)$ is another polynomial then the remainder when $ f(x)$ is divided by $ p(x)$ can be found by replacing all powers of $ x$ higher than $ x^{m - 1}$ in $ f(x)$ using $ x^{m} \equiv -(b_{1}x^{m - 1} + \cdots + b_{m - 1}x + b_{m}) / b_{0} \pmod{p(x)}$.

As an exercise based on this simple technique the reader should try to calculate the remainder when $ x^{5} + x^{4} + 2x^{2} + 1$ when it is divided by $ x^{3} + x^{2} + x + 1$.

Extension Fields

Let's see where these congruences lead us. To that end let $ p(x)$ be a polynomial of positive degree over a field $ F$. Then the congruence modulo $ p(x)$ is an equivalence relation on the set of all polynomials over $ F$ (this set of polynomials we shall denote by $ F[x]$). Thus the set $ F[x]$ is divided into a set of congruence classes. Any such congruence class will be of the form: $$ [f(x)] = \{ g(x) \mid g(x) = f(x) + p(x)q(x)\}$$ where $ f(x), q(x)$ are arbitrary polynomials in $ F[x]$. In other words $ [f(x)]$ represents the set of all polynomials in $ F[x]$ which are congruent to $ f(x)$ modulo $ p(x)$. Clearly there will be a unique polynomial $ r(x)$ in $ [f(x)]$ which will be of lowest degree and it will be the remainder when $ f(x)$ is divided by $ p(x)$. We will use this element $ r(x)$ as a representative of the equivalence class $ [f(x)]$ and preferably use $ [r(x)]$ in place of $ [f(x)]$. The set of all such congruence classes is denoted by $ F[x]/\langle p(x) \rangle$ and it consists of the following members: $$ F[x]/\langle p(x) \rangle = \{[r(x)] \mid r(x) \in F[x]\,\,\text{ and deg}(r(x)) < \text{deg}(p(x))\}$$ In slightly informal terms we may take $ F[x]/\langle p(x) \rangle$ to consists of all polynomials of degree less than that of $ p(x)$. We can now define addition and multiplication in $ F[x]/\langle p(x) \rangle$ as follows: $$ [f(x)] + [g(x)] = [f(x) + g(x)],\,\,\, [f(x)][g(x)] = [f(x)g(x)]$$ The above definitions are unambiguous i.e. the result of addition or multiplication is independent of the representative element chosen in $ [f(x)],[g(x)]$. Moreover it should also be obvious that the set $ F[x]/\langle p(x) \rangle$ forms a commutative ring with unity under these operations. The classes $ [0]$ and $ [1]$ represent the additive and multiplicative identities respectively.

A surprising fact is that the above ring becomes a field when $ p(x)$ is irreducible over $ F$. To see that this is so we need to prove only the existence of inverse of non-zero elements in $ F[x]/\langle p(x) \rangle$. Let $ [f(x)]$ be a non-zero element in $ F[x]/\langle p(x) \rangle$. Then the polynomial $ f(x)$ is not divisible by $ p(x)$. And since $ p(x)$ is irreducible this means that $ f(x)$ and $ p(x)$ are relatively prime. Thus by Euclidean Algorithm there exist polynomials $ a(x), b(x)$ in $ F[x]$ such that $ a(x)f(x) + b(x)p(x) = 1$. This means that $ a(x)f(x) + b(x)p(x) \equiv 1 \pmod{p(x)}$ and since $ b(x)p(x) \equiv 0 \pmod{p(x)}$ we have $ a(x)f(x) \equiv 1 \pmod{p(x)}$.

We thus have $ [a(x)][f(x)] = [1]$ in $ F[x]/\langle p(x) \rangle$ and so $ [a(x)]$ acts as the multiplicative inverse of $ [f(x)]$.

We have the following theorem now:
If $ p(x)$ is an irreducible polynomial over field $ F$ then the set of all congruence classes modulo $ p(x)$ forms a field denoted by $ F[x]/\langle p(x) \rangle$.

Compare this with the corresponding theorem from elementary Number Theory:
If $ p$ is a prime in $ \mathbb{Z}$ then the set of all congruence classes modulo $ p$ forms a field.

The proof techniques in both cases are exactly the same and this gives us a taste of Modern Algebra where we are not concerned so much about the entities in question, but rather their behavior in relation to other entities. Moreover there is an important difference between the above two cases. In case of the integers the generated field is a finite field whereas in case of polynomials the field is generally infinite. Also in the case of polynomials we have the following subset $ F'$ of $ F[x]/\langle p(x) \rangle$ given by:
$$ F' = \{[a] \mid a \in F,\, [a] \in F[x]/\langle p(x) \rangle\}$$ The set $ F'$ is clearly isomorphic to original field $ F$ in the sense that the element $ [a] \in F[x]/\langle p(x) \rangle$ behaves exactly the same as element $ a \in F$. Thus we can identity $ F'$ with $ F$ and then we see that $ F \subset F[x]/\langle p(x) \rangle$ so that $ F[x]/\langle p(x) \rangle$ is a field extension of $ F$.

Further beauty of this field is that there is an special element $ \alpha = [x]$ in $ F[x]/\langle p(x) \rangle$ which has the property that $ p(\alpha) = [0]$. For clarity let us write $ p(x) = a_{0}x^{n} + a_{1}x^{n - 1} + \cdots + a_{n - 1}x + a_{n}$. Since $ F \subset F[x]/\langle p(x) \rangle$ we can see that $ p(x)$ is also a polynomial over $ F[x]/\langle p(x) \rangle$ and then we can interpret $ p(\alpha)$ as an element of $ F[x]/\langle p(x) \rangle$. Clearly we then have: \begin{align} p(\alpha) &= a_{0}\alpha^{n} + a_{1}\alpha^{n - 1} + \cdots + a_{n - 1}\alpha + a_{n}\notag\\ &= a_{0}[x]^{n} + a_{1}[x]^{n - 1} + \cdots + a_{n - 1}[x] + a_{n}\notag\\ &= [a_{0}x^{n} + a_{1}x^{n - 1} + \cdots + a_{n - 1}x + a_{n}]\notag\\ &= [p(x)] = [0]\notag \end{align} It follows that $ \alpha = [x]$ is a root of the polynomial $ p(x)$.

Thus we have found the root of $ p(x)$ without actually finding it. Well let me explain the apparent contradiction in the previous line. Whenever we solve an algebraic equation by methods of algebra all we try to do is postulate a number which has the property that it is the root of the given polynomial. For example if we try to solve $ x^{2} - 2 = 0$ we postulate the existence of root which we denote by symbol $ \sqrt{2}$ with the property that $ (\sqrt{2})^{2} - 2 = 0$. Apart from this algebra can't give any more meaning to the symbol $ \sqrt{2}$. The symbol $ \sqrt{2}$ is not in the base field $ \mathbb{Q}$, but rather lies in an extension field of $ \mathbb{Q}$ (precisely the field $ \mathbb{Q}[x]/\langle (x^{2} - 2)\rangle$).

What is important in algebra is not finding the actual root of $ p(x)$, but rather studying the structure of the extension field $ F[x]/\langle p(x) \rangle$ which depends upon the base field $ F$ as well as the irreducible polynomial $ p(x) \in F[x]$. The root of the polynomial is always $ [x]$, it is the field structure which varies and distinguishes a root of $ p(x)$ from a root of some different polynomial $ q(x)$.

Now let $ f(x)$ be a polynomial of positive degree over field $ F$ which is not necessarily assumed to be irreducible. In that case by the unique factorization in $ F[x]$ we have an irreducible factor $ p(x)$ of $ f(x)$ such that $ p(x)$ is of positive degree. Hence by the reasoning in preceding paragraphs there is a root $ \alpha$ of $ p(x)$ (and hence a root of $ f(x)$) in some extension field of $ F$ (precisely the field $ F[x]/\langle p(x) \rangle$). Dividing $ f(x)$ by $ (x - \alpha)$ in the new field we get another polynomial $ g(x)$. The same argument repeated for $ g(x)$ would give a root $ \beta$ of $ g(x)$ in some other extension field. This way we can find a field extension $ F \subset L$ such that $ L$ contains all the roots of the original polynomials $ f(x)$. Hence we arrive at the following:

Given a polynomial $ f(x)$ of positive degree over a field $ F$ there is a field extension $ F \subset L$ which contains all the roots of the given polynomial.

Hence every non-constant polynomial has a root (and hence all the roots) in some extension field. This sounds like the Fundamental Theorem of Algebra, but it is not. The Fundamental Theorem of Algebra on the other hand talks about polynomials over a specific field and is related more to the structure of the field of real and complex numbers whereas the above is a general statement concerning polynomials over any field. The real power of the Fundamental Theorem of Algebra is that for polynomials with complex coefficients we don't need to extend the field to get to the roots. The field of complex numbers is large enough to contain the roots of all polynomials over itself.

We will have occasion to talk more about the Fundamental Theorem and its proof in later posts. The point which I wish to emphasize in the current post is that simple beginnings like Remainder Theorem and congruence of polynomials lead us to the concept of field extensions which form an important part of Modern Algebra (or what we call Abstract Algebra).

Print/PDF Version