Polynomial Divisibility & the Remainder Theorem
IMO‑style Algebra – Study Notes
These notes are written for competitors who already know elementary algebraic identities and the basic properties of integers. They aim to give you a compact, but complete, reference for polynomial divisibility tests, the Remainder Theorem, and common techniques used in Olympiad problems.
1. Simple Explanation
-
Polynomial Division: Just like integers, a polynomial (P(x)) can be divided by a non‑zero polynomial (D(x)). The result is a quotient (Q(x)) and a remainder (R(x)) of degree strictly less than (\deg D):
[ P(x)=D(x),Q(x)+R(x),\qquad \deg R<\deg D ]
-
Remainder Theorem:
If (D(x)=x-a) (a linear divisor), then the remainder is simply (R=a). In other words, [ P(a)=\text{remainder of }P(x)\text{ on division by }x-a. ] -
Polynomial Remainder Theorem:
If (D(x)) is any polynomial of degree (m), the remainder (R(x)) has degree (<m). To find it, it is enough to know the values of (P(x)) at (m) distinct points (roots of (D)). -
Divisibility Criterion:
A polynomial (P(x)) is divisible by (D(x)) iff the remainder is the zero polynomial – i.e. all its coefficients are zero.
2. Key Points
| Concept | What to remember | Typical use in IMO |
|---|---|---|
| Division Algorithm | (P(x)=D(x)Q(x)+R(x)), (\deg R<\deg D) | To simplify expressions, find remainders |
| Remainder Theorem | (P(a)=) remainder for (x-a) | Quick checks of root‑status, linear divisors |
| Polynomial Remainder Theorem | Use values at roots of (D) to determine (R(x)) | When (D) has high degree, or for modular arithmetic |
| Factor Theorem | (x-a\mid P(x)) iff (P(a)=0) | Proving that a polynomial has a given factor |
| Cyclic Polynomial Division | If (P(x)) has symmetry like (P(1/x)=x^{-n}P(x)), then (x^n-1) often divides it | Common in functional equation problems |
| Congruence of Polynomials | (P\equiv Q\pmod{D}) means (D\mid(P-Q)) | Used in “modulo” arguments for polynomials |
| Symmetric Polynomials | Replace (x) by (1/x) or (-x) to reveal factors | Useful for cyclotomic factors |
| Roots of Unity | (x^k-1=\prod_{\zeta^k=1}(x-\zeta)) | Divisibility by (x^k-1) or (\Phi_k(x)) |
| Euclidean Algorithm for Polynomials | Repeatedly divide to compute GCD | Useful for “greatest common divisor” problems |
3. Worked Example
Problem (IMO‑style)
Let
[ P(x)=x^{10}+x^5+1. ]
Show that (x^2-x+1) divides (P(x)).
Solution
-
Find the roots of the divisor
(x^2-x+1=0) has roots
[ \omega,\ \omega^2,\quad\text{where }\omega=e^{2\pi i/3}\text{ and }\omega^3=1,\ \omega\neq1. ] -
Evaluate (P) at both roots
Because (\omega^3=1), we have (\omega^6=1) and (\omega^9=1).
Compute [ P(\omega)=\omega^{10}+\omega^5+1 =\omega^1+\omega^2+1 =\omega+\omega^2+1. ] But (\omega+\omega^2+1=0) (since (1+\omega+\omega^2=0)).
Similarly, [ P(\omega^2)=\omega^{20}+ \omega^{10}+1 =\omega^2+\omega+1 =0. ] -
Apply the Polynomial Remainder Theorem
Since (P(\omega)=P(\omega^2)=0), both roots of (x^2-x+1) are also roots of (P).
Therefore (x^2-x+1) divides (P(x)). -
Optional – find the quotient
Perform division if desired: [ P(x)= (x^2-x+1),(x^8+x^7-x^5-x^4+x^2+x+1). ]
Conclusion
Using the Remainder Theorem and the fact that a polynomial is divisible by a quadratic iff it vanishes at the two roots, we proved the divisibility.
4. Quick Revision Summary
- Division Algorithm: (P=DQ+R,; \deg R<\deg D).
- Linear Divisor: (P(a)=) remainder for (x-a).
- Factor Theorem: (x-a\mid P\iff P(a)=0).
- Polynomial Remainder Theorem: Use values at roots of (D) to determine (R(x)).
- Divisibility Test: (D\mid P \iff) remainder (=0).
- Roots of Unity: Helpful for divis