Polynomials — Arithmetic, Roots, and Theorems
Pillar: SET — "A polynomial is a set of coefficients; operations on polynomials are operations on these sets."
What Is a Polynomial?
A polynomial in \(x\) is an expression of the form:
The values \(a_0, a_1, \ldots, a_n\) are the coefficients. The highest power with a nonzero coefficient is the degree. The coefficient of that highest power is the leading coefficient.
Example: \(p(x) = 3x^4 - 2x^2 + 7\) has degree 4, leading coefficient 3.
| Term | Degree | Coefficient |
|---|---|---|
| \(3x^4\) | 4 | 3 |
| \(-2x^2\) | 2 | \(-2\) |
| \(7\) | 0 | 7 |
Note: There is no \(x^3\) or \(x^1\) term, so those coefficients are 0.
Why Think of Polynomials as Coefficient Sets?
In competitive programming, a polynomial is almost always stored as an array of coefficients: {3, 0, -2, 0, 7} for \(3x^4 - 2x^2 + 7\). Every operation — addition, multiplication, evaluation — is an operation on this array. The SET pillar applies: the polynomial is its coefficient list, and polynomial arithmetic is array manipulation.
This perspective pays off hugely in Chapter 11, where you learn that polynomial multiplication can be done in \(O(n \log n)\) using FFT, by viewing the coefficient array as a signal to transform.
Polynomial Evaluation — Horner's Method
The naive way to evaluate \(p(x) = 2x^3 - 3x^2 + x - 5\) at \(x = 4\):
This requires computing each power of \(x\) separately. Horner's method is smarter — it rewrites the polynomial as nested multiplications:
Evaluation trace at \(x = 4\):
| Step | Computation | Result |
|---|---|---|
| Start | \(2\) | \(2\) |
| \(\times 4 + (-3)\) | \(2 \times 4 - 3\) | \(5\) |
| \(\times 4 + 1\) | \(5 \times 4 + 1\) | \(21\) |
| \(\times 4 + (-5)\) | \(21 \times 4 - 5\) | \(79\) |
Same answer, but only \(n\) multiplications and \(n\) additions for a degree-\(n\) polynomial (instead of \(O(n^2)\) with naive powering). This is how polynomial evaluation is done in code.
Polynomial Addition and Subtraction
To add polynomials, add corresponding coefficients:
To subtract, subtract corresponding coefficients (watch the signs):
In code, if polynomials are stored as coefficient arrays, addition is just element-wise addition with zero-padding for different lengths.
Polynomial Multiplication
To multiply two polynomials, every term in the first multiplies every term in the second:
The Coefficient Rule
If \(p(x) = \sum a_i x^i\) and \(q(x) = \sum b_j x^j\), then \(r(x) = p(x) \cdot q(x)\) has coefficients:
This is convolution of the coefficient arrays. For degree-\(n\) and degree-\(m\) polynomials, the product has degree \(n + m\) and the naive algorithm takes \(O(nm)\) time.
Key fact: The degree of a product equals the sum of the degrees.
This simple rule is surprisingly useful. If you know the degree of a product must be at most \(d\), and one factor has degree \(k\), the other has degree at most \(d - k\).
Polynomial Long Division
Just like integers, polynomials can be divided to produce a quotient and remainder:
where \(\deg(r) < \deg(d)\).
Example: Divide \(2x^3 + 3x^2 - 5x + 1\) by \(x - 2\).
2x² + 7x + 9
┌─────────────────────────
x - 2 │ 2x³ + 3x² - 5x + 1
-(2x³ - 4x²)
─────────────
7x² - 5x
-(7x² - 14x)
───────────
9x + 1
-(9x - 18)
─────────
19
So \(2x^3 + 3x^2 - 5x + 1 = (x - 2)(2x^2 + 7x + 9) + 19\).
Synthetic Division
When dividing by a linear factor \((x - c)\), synthetic division is a shortcut. It is essentially Horner's method — the intermediate values give you the quotient coefficients, and the final value is the remainder.
Divide \(2x^3 + 3x^2 - 5x + 1\) by \((x - 2)\):
Write coefficients: \(2, 3, -5, 1\). The root is \(c = 2\).
| Bring down | Multiply by 2 | Add to next |
|---|---|---|
| \(2\) | ||
| \(2 \times 2 = 4\) | \(3 + 4 = 7\) | |
| \(7 \times 2 = 14\) | \(-5 + 14 = 9\) | |
| \(9 \times 2 = 18\) | \(1 + 18 = 19\) |
Quotient: \(2x^2 + 7x + 9\). Remainder: \(19\). Same answer, much faster.
The Remainder Theorem
Theorem: When a polynomial \(p(x)\) is divided by \((x - c)\), the remainder is \(p(c)\).
This follows immediately from \(p(x) = (x - c) \cdot q(x) + r\). Substituting \(x = c\): \(p(c) = 0 \cdot q(c) + r = r\).
Example: Find the remainder when \(p(x) = x^4 - 3x^2 + 2\) is divided by \((x - 1)\).
Remainder is 0. This means \((x - 1)\) divides \(p(x)\) evenly — which leads us to the next theorem.
The Factor Theorem
Theorem: \((x - c)\) is a factor of \(p(x)\) if and only if \(p(c) = 0\).
This is the Remainder Theorem's direct consequence: the remainder is zero precisely when \(c\) is a root.
Example: Is \((x + 2)\) a factor of \(p(x) = x^3 + 5x^2 + 8x + 4\)?
Check \(p(-2) = -8 + 20 - 16 + 4 = 0\). Yes, \((x + 2)\) is a factor.
Now divide to find the other factor:
Using the Factor Theorem to Find Roots
For a polynomial with integer coefficients, the Rational Root Theorem tells you where to look:
Rational Root Theorem: If \(\frac{p}{q}\) (in lowest terms) is a root of \(a_n x^n + \cdots + a_0\), then \(p\) divides \(a_0\) and \(q\) divides \(a_n\).
Example: Find the rational roots of \(2x^3 - x^2 - 7x + 6\).
Possible rational roots: \(\pm \frac{\text{divisors of } 6}{\text{divisors of } 2} = \pm 1, \pm 2, \pm 3, \pm 6, \pm \frac{1}{2}, \pm \frac{3}{2}\).
Test \(x = 1\): \(2 - 1 - 7 + 6 = 0\). Root found.
Divide by \((x - 1)\) (synthetic division with \(c = 1\)):
Coefficients \(2, -1, -7, 6\):
\(2 \to 2(1) + (-1) = 1 \to 1(1) + (-7) = -6 \to -6(1) + 6 = 0\)
Quotient: \(2x^2 + x - 6 = (2x - 3)(x + 2)\).
All roots: \(x = 1\), \(x = \frac{3}{2}\), \(x = -2\).
Vieta's Formulas (General)
For a polynomial \(a_n x^n + a_{n-1}x^{n-1} + \cdots + a_0 = 0\) with roots \(r_1, r_2, \ldots, r_n\):
In general, the \(k\)-th elementary symmetric polynomial of the roots equals \((-1)^k \frac{a_{n-k}}{a_n}\).
Degree 3 Vieta's
For \(x^3 + bx^2 + cx + d = 0\) with roots \(r, s, t\):
| Symmetric function | Value |
|---|---|
| \(r + s + t\) | \(-b\) |
| \(rs + rt + st\) | \(c\) |
| \(rst\) | \(-d\) |
Example: If \(r, s, t\) are roots of \(x^3 - 6x^2 + 11x - 6 = 0\), find \(r^2 + s^2 + t^2\).
From Vieta's: \(r + s + t = 6\), \(rs + rt + st = 11\).
(The actual roots are \(1, 2, 3\) — check: \(1 + 4 + 9 = 14\). Correct.)
A Brief Word on Complex Roots
Real polynomials of odd degree always have at least one real root (because a continuous function that goes from \(-\infty\) to \(+\infty\) must cross zero). But even-degree polynomials may have no real roots at all — \(x^2 + 1 = 0\) has no real solution.
The Fundamental Theorem of Algebra says: every degree-\(n\) polynomial with complex coefficients has exactly \(n\) roots in the complex numbers (counting multiplicity).
For polynomials with real coefficients, complex roots come in conjugate pairs: if \(a + bi\) is a root, then \(a - bi\) is also a root.
This matters for CP when a recurrence has complex characteristic roots — the solution still works, it just involves oscillating terms. You will see this in Chapter 10 (matrix exponentiation).
Practice Problems
Problem 1. Evaluate \(p(x) = 3x^3 - 2x^2 + x - 4\) at \(x = -1\) using Horner's method.
Solution
Coefficients: \(3, -2, 1, -4\). Root \(x = -1\).
\(3 \to 3(-1) + (-2) = -5 \to (-5)(-1) + 1 = 6 \to 6(-1) + (-4) = -10\)
\(p(-1) = -10\).
Check: \(3(-1) - 2(1) + (-1) - 4 = -3 - 2 - 1 - 4 = -10\). Correct.
Problem 2. Multiply \((x^2 - x + 1)(x + 1)\).
Solution
\((x^2 - x + 1)(x + 1) = x^3 + x^2 - x^2 - x + x + 1 = x^3 + 1\)
This is actually the factorization of \(a^3 + b^3 = (a + b)(a^2 - ab + b^2)\) with \(a = x\), \(b = 1\).
Problem 3. Find the remainder when \(x^{100} + x^{99} + \cdots + x + 1\) is divided by \((x - 1)\).
Solution
By the Remainder Theorem, the remainder is \(p(1) = 1 + 1 + \cdots + 1 = 101\).
(There are 101 terms, from \(x^{100}\) down to \(x^0 = 1\).)
Problem 4. Find all roots of \(x^3 - 4x^2 + x + 6\).
Solution
Try \(x = -1\): \(-1 - 4 - 1 + 6 = 0\). Root found.
Divide by \((x + 1)\): synthetic division with \(c = -1\) on \(\{1, -4, 1, 6\}\):
\(1 \to 1(-1) + (-4) = -5 \to (-5)(-1) + 1 = 6 \to 6(-1) + 6 = 0\)
Quotient: \(x^2 - 5x + 6 = (x - 2)(x - 3)\).
Roots: \(x = -1, 2, 3\).
Problem 5. The polynomial \(x^3 + ax^2 + bx + 8\) has roots \(r, 2r, 4r\) for some value \(r\). Find \(a\) and \(b\).
Solution
By Vieta's:
\(r + 2r + 4r = 7r = -a\)
\(r \cdot 2r + r \cdot 4r + 2r \cdot 4r = 2r^2 + 4r^2 + 8r^2 = 14r^2 = b\)
\(r \cdot 2r \cdot 4r = 8r^3 = -8\), so \(r^3 = -1\), \(r = -1\).
\(a = -7(-1) = 7\), \(b = 14(1) = 14\).
Check: \(x^3 + 7x^2 + 14x + 8\). Roots should be \(-1, -2, -4\).
\((-1)^3 + 7(1) + 14(-1) + 8 = -1 + 7 - 14 + 8 = 0\). Correct.
Problem 6 (Competition Style). Let \(p(x)\) be a monic cubic polynomial such that \(p(1) = 0\), \(p(2) = 0\), and \(p(0) = 10\). Find \(p(3)\).
Solution
Since \(p\) is monic cubic with roots at 1 and 2:
for some \(r\). Using \(p(0) = 10\):
\(p(0) = (-1)(-2)(-r) = -2r = 10\), so \(r = -5\).