A nonzero polynomial of degree at most n has at most n roots. So two such polynomials that agree at n+1 points are equal. This identity theorem finds remainders and proves divisibility by a test at the roots of unity. It also builds the one polynomial through given points, and solves the classic problems where P(k) is known at many points. The roots of unity also pick out every third binomial coefficient.
about 30 min1 simulation2 practice questions1 Python program5 questions to check yourself
This lesson is free to read. Enroll free to keep your place and take the tests.
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
prove that two polynomials are equal by checking them at enough points;
find a remainder from the values of a polynomial, and test divisibility at roots of unity;
build the polynomial through given points, and use the roots of unity to sum binomial coefficients.
Too many roots
A straight line that crosses the x-axis in two places must be the axis itself. A parabola that meets a line in three points must be that line. This is one simple fact: a nonzero polynomial of degree at most n has at most n roots. It turns out to be a very strong tool.
The identity theorem
If P and Q have degree at most n and P(xi)=Q(xi) at n+1 different points, then P−Q has n+1 roots. So P−Q is the zero polynomial, and P=Q.
Example. For any distinct a, b, c,
(a−b)(a−c)(x−b)(x−c)
+(b−c)(b−a)(x−c)(x−a)
+(c−a)(c−b)(x−a)(x−b)=1.
The left side has degree at most 2 and equals 1 at x=a, b and c. That is three points, so it equals 1 everywhere.
Remainders
Divide P(x) by a polynomial D(x) of degree d: P=DQ+R with R of degree less than d. At a root t of D, P(t)=R(t). So
dividing by x−a leaves P(a);
dividing by (x−a)(x−b) leaves the line through (a,P(a)) and (b,P(b)).
Divisibility at roots of unity
x2+x+1 has the roots ω and ω2. A real polynomial is divisible by it exactly when P(ω)=0. For example, x3m+x3n+1+x3p+2 at x=ω gives 1+ω+ω2=0. So it is divisible by x2+x+1 for all whole numbers m, n, p.
The polynomial through given points
Through n+1 points with different xi there is exactly one polynomial of degree at most n. Lagrange's formula writes it as
P(x)=i∑yiLi(x),
Li(x)=j=i∏xi−xjx−xj.
Each Li is 1 at xi and 0 at the other points. The identity above is Lagrange's formula for P=1.
Four points at x = 0, 1, 2 and 3 with heights 1, 2, 4 and 8, and the cubic curve through them. A fifth point at x = 4 shows the cubic at height 15, just below the point of height 16 that doubling would give.
A worked example
A cubic P has P(k)=2k for k=0,1,2,3. Find P(4).
Values.1,2,4,8.
Differences.1,2,4, then 1,2, then 1.
Extend. The third difference of a cubic is constant, so it stays 1. The next second difference is 2+1=3, and the next first difference is 4+3=7.
Answer.P(4)=8+7=15, not 16. A polynomial is not 2x.
Picking every third binomial coefficient
Expand (1+x)n=∑k(kn)xk and put x=1, ω, ω2. Add the three results. A term with 3∣k gives 1+1+1=3, and every other term gives 1+ωk+ω2k=0. So
3∣k∑(kn)
=32n+(1+ω)n+(1+ω2)n.
For n=6: (1+ω)6=(−ω2)6=1, so the sum is 364+2=22. Check: 1+20+1=22.
Practise with new numbers
Try it in Python
The program builds the polynomial through given points with exact fractions, using Lagrange's formula. Then it checks the sum of every third binomial coefficient against the formula with ω.
Common mistakes
Too few points. Degree n needs n+1 points to fix the polynomial.
The degree of a remainder. Dividing by a quadratic leaves at most a line, ax+b.
Divisibility by x2+x+1. Test at ω, not at 1.
(1+ω)n. Write 1+ω=−ω2 first, then use ω3=1.
Remember these
Degree at most n and equal at n+1 points: equal everywhere.
Remainder on division by (x−a)(x−b): the line through (a,P(a)) and (b,P(b)).
P divisible by x2+x+1 exactly when P(ω)=0.
∑3∣k(kn)=32n+2cos3nπ.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
P(x) leaves the remainder 3 on division by x−1 and 7 on division by x−3. Find the remainder on division by (x−1)(x−3).
Is x5+x4+1 divisible by x2+x+1?
A quadratic has P(0)=1, P(1)=3 and P(2)=7. Find P(3).
A polynomial of degree 3 is 0 at x=1, 2, 3 and 4. What can you say about it?
Find (16)+(46), the coefficients with k one more than a multiple of 3, using the total 26=64 and the result 22 above.
References
OpenStax, College Algebra 2e, Chapter 5, the section on dividing polynomials and the remainder theorem.
H. S. Hall and S. R. Knight, Higher Algebra, the chapter on the theory of equations.
Enroll free in Complex Roots and Roots of Unity
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.