Polynomials (S)

Theory

1. Definition. A polynomial is an expression of the form p(x) = a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{0}. a_{n} ≠ 0 unless p(x) is the zero polynomial. The coefficients a_{i} can be from ℝ, ℂ, ℤ, ℚ, ℤ_{n} etc, if the coefficients are from R, we say this is a polynomial (in x) over R. We call a_{n} the leading coefficient, say the degree of p(x) is n, and if a_{n} = 1, we call the polynomial monic.

2. Division Algorithm. For polynomials f, g, there exist unique polynomials q, r such that f = qg + r and deg r < deg g or r = 0. (p = p(x))

3. Factor Theorem. Suppose that p(a) = 0. When this occurs we say a is a root of p(x). Then p(x) = (x − a)q(x) for some polynomial q(x). If p(x) = (x−a)^{m}q(x) for some q(x) with q(a) ≠ 0, then we say a is a root of multiplicity m. If f(x) | g(x) then all roots of f are automatically roots of g.

4. Rational Root Theorem. If p(x) = a_{n}x^{n}+a_{n−1}x^{n−1}+⋯+a_{0} is a polynomial with integer coefficients and p/q is a rational root written in reduced form then p|a_{0} and q|a_{n}.

5. Vieta’s Theorem. This gives the expressions for the coefficients of a polynomial in terms of its roots, which you should know.

6. Lagrange Interpolation Formula. One of the most important tools in polynomial problems is the fact that if two polynomials of degree at most n agree at n + 1 (or an infinite) number of places, then the polynomials are identical. This is equivalent to the statement that a polynomial of degree n can have at most n roots. The Lagrange Interpolation Formula gives an explicit form for the degree n polynomial through n + 1 predetermined points (a_{0}, b_{0}), (a_{1}, b_{1}), …, (a_{n}, b_{n}).

7. Fundamental Theorem of Algebra. Every nonconstant polynomial with coefficients in ℂ has a root (in ℂ).

8. Corollory. A polynomial of degree n over ℂ has exactly n roots counted according to multiplicity.

9. Irreducible Polynomials. A polynomial is said to be irreducible if it cannot be factored into two polynomials of smaller degree. Over ℤ, ℚ, ℝ, ℂ and ℤ_{p} where p is a prime, every polynomial can be factored uniquely into irreducibles up to a constant factor.

10. Eisenstein’s Criterion. Let f(x) = a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{0} be a polynomial with integer coefficients. Suppose that there exists a prime p such that

(a) p |̸ a_{n}

(b) p |a_{i} for 0 ≤ i < n (c) p^{2} |̸ a_{0}

Then f(x) is irreducible over ℤ[x] (and hence by Gauss’ Lemma below is also irreducible over ℚ[x]).

11. Gauss’ Lemma. Let f(x) be a polynomial with integer coefficients. If we can factor f(x) as f(x) = g(x)h(x) over the rationals, then we can factor f(x) over the integers f(x) = g_{1}(x)h_{1}(x) where g_{1}(x) and h_{1}(x) are rational multiples of g(x) and h(x).

12. Descartes’ Rule of Signs. The number of positive roots of a real polynomial is at most the number of sign changes in the list of coefficients of the polynomial, and is equal in parity to this number. (To determine the number of negative roots, use p(−x).)

13. Minimal Polynomials. Suppose α is the root of a polynomial over R in an extension of R. Then there exists a minimal polynomial for α, d(x) with the properties that d(α) = 0 and if p(x) is any polynomial for which p(α) = 0, then d(x) divides p(x). d(x) is necessarily irreducible.

Problems

1. Show that cos^{−1}(\frac{4}{5}) is an irrational multiple of π.

2. (2000 AMO Q1) Find all polynomials f with real coefficients such that

(x − 27)f(3x) = 27(x − 1)f(x)

for every real number x.

3. (1970 Canada) Let P (x) be a polynomial with integral coefficients. Suppose there exist four distinct integers a, b, c and d with P (a) = P (b) = P (c) = P (d) = 5. Prove that there is no integer k with P (k) = 8.

4. (1993 IMO Q1) Let f(x) = x^{n} + 5x^{n−1} + 3, where n > 1 is an integer. Prove that f(x) cannot be expressed as a product of two nonconstant polynomials with integer coefficients.

5. (1999 Canada) If a, b, c are the roots of x^{3} − x − 1 = 0, compute

\frac{1 + a}{1 − a} + \frac{1 + b}{1 − b} + \frac{1 + c}{1 − c}.

6. (1997 China) Let 0 < a_{0} ≤ a_{1} ≤ … ≤ a_{n−1} ≤ 1 be real numbers. Let z be a complex root of the equation x^{n} + a_{n−1}x^{n−1} + … + a_{1}x + a_{0} = 0 such that |z| ≥ 1. Prove that z^{n+1} = 1.

7. (1974 IMO Q6) Let P (x) be a polynomial with integer coefficients of degree d > 0. Let n be the number of distinct integers k such that (P (k))^{2} = 1. Prove that n ≤ d + 2.

8. (1991 AUO) Let a_{1}, a_{2}, …, a_{100}, b_{1}, b_{2}, …, b_{100} be distinct real numbers. A table of 100 × 100 numbers is filled so that the number a_{i} + b_{j} is written down on the intersection of the i’th row with the j’th column. Given, that in each column the product of all numbers is equal to 1, prove that in each row the product of all numbers is equal to −1.

9. (1999 Czech-Slovak) Find all natural numbers k for which the following assertion holds: If F (x) is a polynomial with integer coefficients which satisfies 0 ≤ F (c) ≤ k for all c ∈ {0, 1, …, k + 1} then F (0) = F (1) = ⋯ = F (k + 1).

10. (2002 IMO Q3) Find all pairs of integers m, n ≥ 3 such that there exist infinitely many positive integers a for which

\frac{a^{m} + a − 1}{a^{n} + a^{2} − 1}

is an integer.

11. (2001 APMO Q4) A point in the plane with a cartesian coordinate system is called a mixed point if one of its coordinates is rational and the other one is irrational. Find all polynomials with real coefficients such that their graphs do not contain any mixed point.

12. (1975 USAMO) Let P (x) be a polynomial of degree n, so that P (k) = k/(k+1) for k = 0, 1, … n. Find P (n + 1).

13. (1997 UKMO) Find the number of polynomials of degree 5 with distinct coefficients from the set {1, 2, …, 9} that are divisible by x^{2} − x + 1.

14. Let P (x) = a_{0}x^{n} + a_{1}x^{n−1} + ⋯ + a_{n} be a nonzero polynomial with integer coefficients such that P (r) = P (s) = 0 for some integers r and s, with 0 < r < s. Prove that a_{k} ≤ −s for some k.

15. It is known of a polynomial over ℤ that p(n) > n for every positive integer n. Consider x_{1} = 1, x_{2} = p(x_{1}), . . .. We know that, for any positive integer N, there exists a term of the sequence divisible by N. Prove that p(x) = x + 1.