Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

c 2007 The Author(s) and The IMO Compendium Group

Polynomials in One Variable
Duˇan Djuki´
s
c

Contents
1
2
3
4
5
6
7
8
9

1

General Properties
...

Polynomials with Integer Coefficients
Irreducibility
...

Applications of Calculus
...

Problems
...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...


...


...


...


...



...


...


...


...


...
Constant c can be e
...
an integer, rational, real or complex number
...
In other words, it is an expression
of the form
P (x) = an xn + an−1 + · · · + a1 x + a0
...

The constants a0 ,
...
The set of polynomials
with the coefficients in set A is denoted by A[x] - for instance, R[x] is the set of polynomials with
real coefficients
...
l
...
g
...
Then the exponent n is called the degree of polynomial P and denoted by
deg P
...

A nonzero constant polynomial has degree 0, while the zero-polynomial P (x) ≡ 0 is assigned the
degree −∞ for reasons soon to become clear
...
P (x) = x3 (x + 1) + (1 − x2 )2 = 2x4 + x3 − 2x2 + 1 is a polynomial with integer
coefficients of degree 4
...

0x
√
1
R(x) = x2 = |x|, S(x) = x and T (x) = 2x + 1 are not polynomials
...

The behavior of the degrees of the polynomials under these operations is clear:

2

Olympiad Training Materials, www
...
org
...
imocompendium
...
If A and B are two polynomials then:
(i) deg(A ± B) ≤ max(deg A, deg B), with the equality if deg A = deg B
...

The conventional equality deg 0 = −∞ actually arose from these properties of degrees, as else
the equality (ii) would not be always true
...
Instead, like integers, they can be divided with a residue
...
Given polynomials A and B = 0, there are unique polynomials Q (quotient) and R
(residue) such that
A = BQ + R and deg R < deg B
...
Let A(x) = an xn + · · · + a0 and B(x) = bk xk + · · · + b0 , where an bk = 0
...
For n < k the statement is trivial
...
Then A1 (x) = A(x) − ak xn−k B(x) is a polynomial of degree
b
n
less than n (for its coefficient at x iz zero); hence by the inductive assumption there are unique
polynomials Q1 and R such that A1 = BQ1 + R and deg R
...

bk

Example 2
...

x2 − x − 3
x −x−3
We say that polynomial A is divisible by polynomial B if the remainder R when A is divided by
B equal to 0, i
...
if there is a polynomial Q such that A = BQ
...
Polynomial P (x) is divisible by binomial x − a if and only if
P (a) = 0
...
There exist a polynomial Q and a constant c such that P (x) = (x − a)Q(x) + c
...

Number a is a zero (root) of a given polynomial P (x) if P (a) = 0, i
...
(x − a) | P (x)
...
This is not always
possible
...
Nevertheless, the zeros can always be computed with an arbitrary
precision
...

√
Example 3
...

Polynomial x2 − 2x + 2 has no real roots, but it has two complex roots: x1,2 = 1 ± i
...
44, 1
...

More generally, the following simple statement holds
...
If a polynomial P is divisible by a polynomial Q, then every zero of Q is also a zero of
P
...
Although every zero of x2 is a zero of x, x2 does not divide x
...
For which n is the polynomial xn + x − 1 divisible by a) x2 − x + 1, b) x3 − x + 1?

Duˇan Djuki´ : Polynomials in One Variable
s
c

3
√

Solution
...
If x2 − x + 1 divides xn + x − 1,
2
then ǫ1,2 are zeros of polynomial xn + x − 1, so ǫn = 1 − ǫi = ǫ−1
...

b) If f (x) = x3 − x + 1 divides xn + x − 1, then it also divides xn + x3
...
However, f (x) has
a zero between −2 and −1 (for f (−2) < 0 < f (−1)) which is obviously not of modulus 1
...
△
Every nonconstant polynomial with complex coefficients has a complex root
...

The following statement is analogous to the unique factorization theorem in arithmetics
...
Polynomial P (x) of degree n > 0 has a unique representation of the form
P (x) = c(x − x1 )(x − x2 ) · · · (x − xn ),
not counting the ordering, where c = 0 and x1 ,
...

Therefore, P (x) has at most deg P = n different zeros
...
First we show the uniqueness
...

Comparing the leading coefficients yields c = d
...
l
...
g
...
Then P (x1 ) = 0
...

The existence is shown by induction on n
...
Let n > 1
...
By Bezout’s theorem, P (x) = (x−x1 )P1 (x) for some polynomial
P1 of degree n − 1
...
, xn for which
P1 (x) = c(x − x2 ) · · · (x − xn ), which also implies P (x) = c(x − x1 ) · · · (x − xn )
...
If polynomials P and Q has degrees not exceeding n and coincide at n + 1 different
points, then they are equal
...
The exponent αi is called the multiplicity of
the root ai
...
Polynomial of n-th degree has exactly n complex roots counted with their multiplicities
...
The
following statement is a direct consequence of the previous theorem:
Theorem 7
...

Remark: This can be shown without using the existence of roots
...
Now if P = QS = RT
for some polynomials R, S, then R(KT − LS) = KQS − LRS = S, and therefore R | S and
QR | QS = P
...
Thus:

Olympiad Training Materials, www
...
org
...
imocompendium
...
If ξ is a zero of a real polynomial P (x), then so is ξ
...
Polynomial (x − ξ)(x − ξ) =
x2 − 2Reξ + |ξ|2 = x2 − pi x + qi has real coefficients which satisfy p2 − 4qi < 0
...
A real polynomial P (x) has a unique factorization (up to the order) of the form
P (x) = (x − r1 ) · · · (x − rk )(x2 − p1 x + q1 ) · · · (x2 − pl x + ql ),
where ri and pj , qj are real numbers with p2 < 4qi and k + 2l = n
...


2

Zeros of Polynomials

In the first section we described some basic properties of polynomials
...

As we pointed out, in some cases the zeros of a given polynomial can be exactly determined
...
The well-known formula
gives the solutions of a quadratic equation ax2 + bx + c = 0 (a = 0) in the form
x1,2 =

−b ±

√
b2 − 4ac

...
We show Tartaglia’s method
of solving a cubic equation
...

3
27

Putting y = u + v transforms this equation into u3 + v 3 + (3uv + p)y + q = 0
...
Thus the above equation
becomes the system
p
uv = − , u3 + v 3 = −q
3
which is easily solved: u3 and v 3 are the solutions of the quadratic equation t2 + qt −
uv = −p/3 must be real
...
The solutions of the equation y 3 + py + q = 0 with p, q ∈ R
are
yi = ǫj

3

q
− +
2

p3
q2
+
+ ǫ−j
4
27

where ǫ is a primitive cubic root of unity
...
If deg f = n is
odd, then −1 is a zero of f and the polynomial f (x)/(x + 1) is symmetric
...
In particular, x2 + x−2 = y 2 − 2, x3 + x−3 = y 3 − 3y, etc
...

Problem 2
...

Solution
...
Then
f (x)
= g(y) = y 3 − 2y 2 − 2y + 2
...
In other words, |x| = 1 if and only if y is real
with −2 ≤ y ≤ 2, where to each such y correspond two values of x if y = ±2
...
To see this, it is enough to note
that g(−2) = −10, g(0) = 2, g(2) = −2, and that therefore g has a zero in each of the intervals
(−2, 0), (0, 2) and (2, ∞)
...
For example, comparing coefficients at xn−1 on both sides gives us x1 + x2 +
· · · + xn = −a1
...
The
general relations are given by the Vieta formulas below
...
Elementary symmetric polynomials in x1 ,
...
, σn ,
where
σk = σk (x1 , x2 ,
...
xik ,
the sum being over all k-element subsets {i1 ,
...
, n}
...
Also, we usually set σ0 = 1 and
σk = 0 for k > n
...
If α1 , α2 ,
...
, αn ) for k = 1, 2,
...

Proof
...
The case n = 1 is trivial
...
Let us compute the coefficient ak of P (x) at
k−1
xk
...
, xn−1 ) and
k−1 = (−1)
a′ = (−1)k σk (x1 ,
...
, xn )
...
The roots x1 , x2 , x3 of polynomial P (x) = x3 − ax2 + bx − c satisfy a = x1 + x2 + x3 ,
b = x1 x2 + x2 x3 + x3 x1 and c = x1 x2 x3
...
Prove that not all zeros of a polynomial of the form xn + 2nxn−1 + 2n2 xn−2 + · · · can
be real
...
imo
...
yu, www
...
com

6

Solution
...
, xn are real
...


xi = −2n,

i
However, by the mean inequality we have
1
xi xj =
2
i
2

xi
i

1
−
2

x2
i
i

n−1
≤
2n

2

xi
i

= 2n(n − 1),

a contradiction
...
Find all polynomials of the form an xn + an−1 xn−1 + · · · + a1 x + a0 with aj ∈ {−1, 1}
(j = 0, 1,
...

Solution
...
, xn be the roots of the given polynomial
...

n
1 2

By the mean inequality, the second equality implies x2 + · · · + x2 ≥ n; hence n ≤ 3
...
Now we can easily find all solutions: x ± 1, x2 ± x − 1,
x3 − x ± (x2 − 1)
...
On the
other hand, if the task is to show that all zeros of a polynomial are real, but not all are computable,
the situation often gets more complicated
...
Show that all zeros of a polynomial f (x) = x(x − 2)(x − 4)(x − 6) + (x − 1)(x −
3)(x − 5)(x − 7) are real
...
Since f (−∞) = f (∞) = +∞, f (1) < 0, f (3) > 0 and f (5) < 0, polynomial f has a
real zero in each of the intervals (−∞, 1), (1, 3), (3, 5), (5, ∞), that is four in total
...
This
fundamental theorem has many different proofs
...
All imperfections in the proof are made on
purpose
...
Every nonconstant complex polynomial
P (x) has a complex zero
...
Write P (x) = xn + an−1 xn−1 + · · · + a0
...
For each
r > 0, let Cr be the circle in the complex plane with the center at point 0 and radius r
...
The curve described by the monomial xn , i
...

{xn | x ∈ Cr } rounds point 0 n times
...
Thus for such r the curve γr also rounds point 0 n
times; hence, it contains point 0 in its interior
...
Thus,
there exists a minimum r = r0 for which point 0 is not in the exterior of γr
...
Therefore, there is a zero of polynomial P (x) of modulus r0
...
The difference
P (x) − P (y) can be written in the form
an (xn − y n ) + · · · + a2 (x2 − y 2 ) + a1 (x − y),
in which all summands are multiples of polynomial x − y
...
If P is a polynomial with integer coefficients, then P (a) − P (b) is divisible by a − b
for any distinct integers a and b
...

There is a similar statement about rational roots of polynomial P (x) ∈ Z[x]
...
If a rational number p/q (p, q ∈ Z, q = 0, nzd(p, q) = 1) is a root of polynomial
P (x) = an xn + · · · + a0 with integer coefficients, then p | a0 and q | an
...
We have
qn P

p
q

= an pn + an−1 pn−1 q + · · · + a0 q n
...
Hence q | an pn and p | a0 q n and the claim follows
...
Polynomial P (x) ∈ Z[x] takes values ±1 at three different integer points
...

Solution
...
Then by the previous statement the integers a − d, b − d and c − d all divide 1, a
contradiction
...
Let P (x) be a polynomial with integer coefficients
...

Solution
...
Assume xk = x0
...

Suppose that d1 = d0 = d = 0
...
Similarly, d3 = d etc, and hence xk = x0 + kd = x0 for all k, a contradiction
...
△
Note that a polynomial that takes integer values at all integer points does not necessarily have
integer coefficients, as seen on the polynomial x(x−1)
...
If the value of the polynomial P (x) is integral for every integer x, then there exist
integers c0 ,
...


x
x
x

...
imo
...
yu, www
...
com

8

Proof
...
The case n = 1 is trivial; Now assume that n > 1
...
, an−1 ∈ Z such that
Q(x) = an−1

x
x

...
Using the identity
0
1
x−1
x
= k+1 for every integer k we obtain the desired representation of P (x):
k + k + ···+
k
P (x) = an−1

x
x
+ P (0)
...
Suppose that a natural number m and a real polynomial R(x) = an xn + an−1 xn−1 +
· · · + a0 are such that R(x) is an integer divisible by m whenever x is an integer
...

1
Solution
...
The leading
coefficient of this polynomial equals cn +ncn−1 +· · ·+n!c0 , and the statement follows immediately
...

Example 5
...
Such
are e
...
x2 − x − 1 and 2x3 − 4x + 1
...
g
...
However, of the mentioned, only reducibility over Z[x] is of interest
...
In
addition, we have already shown that a real polynomial is always reducible into linear and quadratic
factors over R[x], while a complex polynomial is always reducible into linear factors over C[x]
...
If a polynomial P (x) with integer coefficients is reducible over Q[x],
then it is reducible over Z[x], also
...
Suppose that P (x) = an xn + · · · + a0 = Q(x)R(x) ∈ Z[x], where Q(x) and R(x)
nonconstant polynomials with rational coefficients
...
Then qrP (x) = qQ(x) · rR(x) is a factorization of the polynomial qrP (x) into two
polynomials from Z[x]
...

Let p be an arbitrary prime divisor of q
...
Let i be such
that p | q0 , q1 ,
...
We have p | ai = q0 ri + · · · + qi r0 ≡ qi r0 (mod p), which
implies that p | r0
...

Continuing in this way, we deduce that p | rj for all j
...

We have thus obtained a factorization of rq P (x) into two polynomials from Z[x]
...

From now on, unless otherwise specified, by “irreducibility” we mean irreducibility over Z[x]
...
If a1 , a2 ,
...


Duˇan Djuki´ : Polynomials in One Variable
s
c

9

Solution
...
Since
Q(ai )R(ai ) = −1 for i = 1,
...
It follows that the polynomial Q(x) + R(x)
(which is obviously nonzero) has n zeros a1 ,
...
△
Theorem 17 (Extended Eisenstein’s Criterion)
...
If there exist a prime number p and an integer k ∈ {0, 1,
...
, ak , p ∤ ak+1 and p2 ∤ a0 ,
then P (x) has an irreducible factor of a degree greater than k
...

Proof
...
Since a0 = q0 r0 is
divisible by p and not by p2 , exactly one of q0 , r0 is a multiple of p
...

Further, p | a1 = q0 r1 + q1 r0 , implying that p | q1 r0 , i
...
p | q1 , and so on
...
, qk are divisible by p, but p ∤ qk+1
...

Problem 10
...
Prove
that there are no nonconstant polynomials g(x), h(x) with integer coefficients such that f (x) =
g(x)h(x)
...
By the (extended) Eisenstein criterion, f has an irreducible factor of degree at least n − 1
...
△
Problem 11
...

Solution
...
We have
Φp (x + 1) =

p
(x + 1)p − 1
p
= xp−1 +
xp−2 + · · · +
x + p
...
△
In investigating reducibility of a polynomial, it can be useful to investigate its zeros and their
modules
...

Problem 12
...

Solution
...
If Q and R are polynomials
from Z[x] and deg Q = k, then |Q(0)| is the product of the modules of the zeros of Q and equals
22k/n ; since this should be an integer, we deduce that n = 2k
...
Therefore,
2 | k and 4 | n
...
Estimating
complex zeros of a polynomial is not always simple
...


Olympiad Training Materials, www
...
org
...
imocompendium
...
Let α be its zero
...
We thus come to the following estimate:

Theorem 18
...
If an−1 = · · · = an−k+1 = 0, then all roots of the polynomial P are less than
max
0≤k√
k
1 + M in modulus
...

Problem 13
...
a1 a0 is a decimal representation of a prime number and an > 1, prove that
the polynomial P (x) = an xn + · · · + a1 x + a0 is irreducible
...
2)
Solution
...

Let x1 ,
...
, xn be the zeros of R
...
l
...
g
...

On the other hand, by the estimate in 18, each zero xi has a modulus less than 1 + 9/2 = 11/2 < 9;
hence |10 − xi | > 1 for all i, contradicting the above inequality
...
Let p > 2 be a prime number and P (x) = xp − x + p
...
Prove that all zeros of polynomial P are less than p p−1 in modulus
...
Prove that the polynomial P (x) is irreducible
...

1

1
...
Then |y|p − |y| ≤ |y p − y| = p
...
Here we used the inequality p p−1 >
binomial expansion of pp−1 = ((p − 1) + 1)p−1
...
Suppose that P (x) is the product of two nonconstant polynomials Q(x) and R(x) with integer
coefficients
...
On
1
the other hand, the zeros x1 ,
...
, |xk | < p p−1 by part (a), and
x1 · · · xk = ±p, so we conclude that k ≥ p, which is impossible
...
So, suppose
that P is an n-th degree polynomial and that P (xi ) = yi in different points x0 , x1 ,
...
There
exist unique polynomials E0 , E1 ,
...
Then the polynomial
P (x) = y0 E0 (x) + y1 E1 (x) + · · · + yn En (x)
has the desired properties: indeed, P (xi ) =
j yj Ej (xi ) = yi Ei (xi ) = yi
...
, En
...
This shows that:
j=i (x − xj ), from which we easily obtain Ei (x) =

Duˇan Djuki´ : Polynomials in One Variable
s
c

11

Theorem 19 (Newton’s interpolating polynomial)
...
, yn and distinct
x0 ,
...
, n
...

(xi − xj )

Example 6
...

Solution
...

6

△

In order to compute the value of a polynomial given in this way in some point, sometimes we
do not need to determine its Newton’s polynomial
...

Example 7
...
, 2n, compute
P (−1)
...
P (x) is of course identically equal to 1, so P (−1) = 1
...
△
(2i + 1)i!(n − i)!

Instead, it is often useful to consider the finite difference of polynomial P , defined by P [1] (x) =
P (x + 1) − P (x), which has the degree by 1 less than that of P
...
A simple induction
gives a general formula
k
k
P (x + i)
...
P (x + n + 1) =
i=0

n+1
P (x + i)
...
Polynomial P of degree n satisfies P (i) =
P (n + 1)
...
, n
...
We have
n+1

(−1)i

0=
i=0

It follows that P (n + 1) =

n+1
P (i) = (−1)n+1 P (n + 1) +
i
1,
0,

1,
0,

2 | n;
2 ∤ n
...


Problem 16
...
, n, prove that P (n + 2) = 2P (n + 1) − 1
...
We observe that P [1] (0) = 0 i P [1] (i) = 2i−1 for i = 1,
...
, n−2, etc
...
, n − k, and P [k] (0) is 0 for k odd and 1 for k even
...
△

2n ,
2 | n;
2n − 1, 2 ∤ n
...
imo
...
yu, www
...
com

12

6

Applications of Calculus

The derivative of a polynomial P (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 is given by
P ′ (x) = nan xn−1 + (n − 1)an−1 xn−2 + · · · + a1
...

n+1
n

If the polynomial P is not given by its coefficients but rather by its canonical factorization, as P (x) =
(x − x1 )k1 · · · (x − xn )kn , a more suitable expression for the derivative is obtained by using the
logarithmic derivative rule or product rule:
P ′ (x) = P (x)

kn
k1
+ ···+
x − x1
x − xn


...

Problem 17
...
, n
...
, n
...
Let P (x) = (x − x0 )(x − x1 ) · · · (x − xn )(x − xn+1 )
...

(x − xj )(x − xk )

1
(xi − xj )

for i = 0, 1,
...
Thus the condition of the problem is equivalent to P ′′ (xi ) = 0 for i =
1, 2,
...
Therefore
x(x − 1)P ′′ (x) = (n + 2)(n + 1)P (x)
...
On the other hand, the monic polynomial Q(x) = (−1)n P (1 − x) satisfies the
same equation and has degree n + 2, so we must have (−1)n P (1 − x) = P (x), which implies the
statement
...

Theorem 21
...

Proof
...

Problem 18
...


Duˇan Djuki´ : Polynomials in One Variable
s
c

13

Solution
...
Similarly, P ′ (x) has a double zero at point −1 too
...
Since P ′ (x) is of degree at most 4, it follows that
P ′ (x) = c(x − 1)2 (x + 1)2 = c(x4 − 2x2 + 1)
2
for some constant c
...
The
5
conditions P (−1) = 1 and P (1) = −1 now give us c = −15/8, d = 0 and

5
15
3
P (x) = − x5 + x3 − x
...
For polynomials P (x) and Q(x) and an arbitrary k ∈ C, denote
Pk = {z ∈ C | P (z) = k} and Qk = {z ∈ C | Q(z) = k}
...

Solution
...
l
...
g
...
Let P0 = {z1 , z2 ,
...
, zk+m }
...
, zk+m
...

We have
P (x) = (x − z1 )α1 · · · (x − zk )αk = (x − zk+1 )αk+1 · · · (x − zk+m )αk+m + 1
for some natural numbers α1 ,
...
Let us consider P ′ (x)
...
, k + m; hence,
k+m
i=1

(x − zi )αi −1 | P ′ (x)
...
e
...

△
Even if P has no multiple zeros, certain relations between zeros of P and P ′ still hold
...

Theorem 22 (Rolle’s Theorem)
...

Corollary
...
)
Proof
...
Assume w
...
o
...
that P ′ (a) > 0 and consider
the point c in the interval [a, b] in which P attains a local maximum (such a point exists since the
interval [a, b] is compact)
...
If for example
P ′ (c) > 0 (the case P ′ (c) < 0 leads to a similar contradiction), then P (x) > P (c) would hold in a
small neighborhood of c, a contradiction
...


7

Symmetric polynomials

A symmetric polynomial in variables x1 ,
...
For instance, polynomial x2 is symmetric as a polynomial in x1 (no
1
wonder), but is not symmetric as a polynomial in x1 , x2 as changing places of the indices 1 and 2
changes it to the polynomial x2
...
The polynomial P (x1 , x2 ,
...
, n}, P (x1 , x2 ,
...
, xπ(n) )
...
imo
...
yu, www
...
com

14

An obvious property of a symmetric polynomial is that its coefficients at two terms of the forms
xi1 · · · xin and xj1 · · · xjn , where (j1 ,
...
, in ), always coincide
...

Thus, the polynomials σk (1 ≤ k ≤ n) introduced in section 2 are symmetric
...
g
...

1
2
A symmetric polynomial is said to be homogenous if all its terms are of the same degree
...
, txn ) = td T (x1 ,
...
For instance, x2 + x2 is homogenous of degree d = 2, but x2 + x2 + 1, although symmetric,
2
1
2
1
is not homogenous
...
, xn can be written as a sum of homogenous polynomials
...
These bricks are
the polynomials
a
a
(∗)
Ta =
x1 i1 · · · xnin
for each n-tuple a = (a1 ,
...
, in ) of the indices 1,
...
In the expression for Ta the same
summand can occur more than once, so we define Sa as the sum of the different terms in (∗)
...
For instance,
T(2,2,0) = 2(x2 x2 + x2 x2 + x2 x2 ) = 2S(2,2,0)
...
, sk = s′ and sk+1 > s′
1
k
k+1 for some k ≥ 1,

where si = a1 + · · · + ai
...
, x + 1, x,
...

The polynomials Ta can be multiplies according to the following simple formula:
Theorem 23
...
, an ) and b = (b1 ,
...
(We define (xi )n + (yi )n =
i=1
i=1
(xi + yi )n
...
It suffices to observe that
π (b)

x1 1

π
· · · xnn (b) Ta =

a +πi1 (b)

xi11

a +πin (b)

n
· · · xin

,

and to sum up over all permutations π
...

We need simpler elements which are independent and using which one can express every symmetric
polynomial by basic operations
...
, σn
...
The following polynomials in x, y, z can be written in terms of σ1 , σ2 , σ3 :
xy + yz + zx + x + y + z = σ2 + σ1 ;
x2 y + x2 z + y 2 x + y 2 z + z 2 x + z 2 y = σ1 σ2 − 3σ3 ;
2
x2 y 2 + y 2 z 2 + z 2 x2 = σ2 − 2σ1 σ3
...
Every symmetric polynomial in x1 ,
...
, σn
...
, σn with integer coefficients
...
It is enough to prove the statement for the polynomials Sa of degree d (for each d)
...
The statement is true for
q
the smallest n-tuple m: Indeed, Sm = σn σr , where d = nq + r, 0 ≤ r < n
...

Suppose that a = (a1 ,
...
Consider the polynomial
Sa − σk Sa′ , where a′ = (a1 − 1,
...
, an )
...

The proof of the previous theorem also gives us an algorithm for expressing each symmetric
polynomial in terms of the σi
...

Theorem 25 (Newton’s Theorem on Symmetric Polynomials)
...


(All the polynomials are in n variables
...
Direct, for example by using the formula 23
...
Suppose that complex numbers x1 , x2 ,
...
, k,

where n, k are given positive integers
...
(x − xk ) = xk −

n
n k−1
n k−2

...
We are given sk = n for k = 1,
...
The Newton’s theorem gives us σ1 = n,
1
1
σ2 = 2 (nσ1 − n) = n , σ3 = 3 (nσ2 − nσ1 + n) = n , etc
...
If this holds for 1,
...
△
k

8

n−1
i

+

n−1
i−1

n
k

n
n
n
−
+
− ···
...
A monic polynomial f (x) of fourth degree satisfies f (1) = 10, f (2) = 20 and f (3) = 30
...

2
...
, xn ,
and Q(x) = xn +b1 xn−1 +· · ·+bn with the zeros x2 ,
...
Prove that if a1 +a3 +a5 +· · ·
1
n
and a2 + a4 + a6 + · · · are real numbers, then b1 + b2 + · · · + bn is also real
...
If a polynomial P with real coefficients satisfies for all x
P (cos x) = P (sin x),
show that there exists a polynomial Q such that P (x) = Q(x4 − x2 ) for each x
...
imo
...
yu, www
...
com

16

4
...

(b) Prove that the polynomials Tn satisfy Tm+n +Tm−n = 2Tm Tn for all m, n ∈ N, m ≥ n
...


The polynomials Tn (x) are known as the Chebyshev polynomials
...
Prove that if cos p π = a is a rational number for some p, q ∈ Z, then a ∈ {0, ± 2 , ±1}
...
Prove that the maximum in absolute value of any monic real polynomial of n-th degree on
1
[−1, 1] is not less than 2n−1
...
The polynomial P of n-th degree is such that, for each i = 0, 1,
...
Evaluate P (n + 1)
...
A polynomial P (x) of n-th degree satisfies P (i) =

1
i

for i = 1, 2,
...
Find P (n + 2)
...
Let P (x) be a real polynomial
...

(b) If P (x) ≥ 0 for all x ≥ 0, show that there exist real polynomials A(x) and B(x) such
that P (x) = A(x)2 + xB(x)2
...
Prove that if the equation Q(x) = ax2 + (c − b)x + (e − d) = 0 has real roots greater than 1,
where a, b, c, d, e ∈ R, then the equation P (x) = ax4 + bx3 + cx2 + dx + e = 0 has at least
one real root
...
A monic polynomial P with real coefficients satisfies |P (i)| < 1
...

12
...
)
13
...

14
...

15
...

16
...
(IMO04-2)
17
...
Suppose that there is a polynomial P (x) such that |an | < P (n) for all n
...

18
...
Consider the polynomial Q(x) = P (P (
...
)), where P is applied k
times
...
(IMO06-5)

Duˇan Djuki´ : Polynomials in One Variable
s
c

17

19
...

20
...
Prove that the polynomial
f (x) = xm (x − a)n + p is irreducible
...
Prove that the polynomial F (x) = (x2 + x)2 + 1 is irreducible for all n ∈ N
...
A polynomial P (x) has the property that for every y ∈ Q there exists x ∈ Q such that
P (x) = y
...

23
...
, i − n (where
i2 = −1) and let R(x) and S(x) be the real polynomials such that P (x) = R(x) + iS(x)
...

24
...
Prove that if there exist coprime polynomials P, Q, R with
complex coefficients such that
P a + Qb = R c ,
then

1
a

+

1
b

+

1
c

> 1
...

25
...

Prove that there are only finitely many such polynomials of any given degree; hence show that
all its zeros are actually roots of unity, i
...
P (x) | (xn − 1)k for some natural n, k
...
The polynomial f (x) − 10x vanishes at points x = 1, 2, 3, so it is divisible by polynomial
(x − 1)(x − 2)(x − 3)
...
Now
f (12) + f (−8) = 11 · 10 · 9 · (12 − c) + 120 + (−9)(−10)(−11)(−8 − c) − 80 = 19840
...
Note that Q(x2 ) =
have

(x2 − x2 ) =
i

(x − xi ) ·

(x + xi ) = (−1)n P (x)P (−x)
...

3
...
e
...
Therefore, P (x) = S(x2 ) for some
polynomial S
...
e
...
This is equivalent to R(x − 1 ) = R( 2 − x), i
...
R(y) ≡
2
1
R(−y), where R is a polynomial such that S(x) = R(x − 2 )
...

4
...
For n > 1 we use induction
on n
...
Since T1 Tn and Tn−1 are of degrees n + 1 and n − 1 respectively, Tn+1
is of degree n + 1 and has the leading coefficient 2 · 2n = 2n+1
...

(b) The relation follows from the identity cos(m + n)x + cos(m − n)x = 2 cos mx cos nx
...
imo
...
yu, www
...
com

18

(c) The sequence of polynomials (Un ) satisfies U0 (x) = 2, U1 (x) = x and Un+1 = U1 Un −
Un−1 , implying that each Un has integer coefficients
...

5
...
It follows from the previous problem that Uq (2a) = 2 cos pπ = ±2,
q
where Uq is monic with integer coefficients, so 2a is an integer by theorem 14
...
Note that equality holds for a multiple of the n-th Chebyshev polynomial Tn (x)
...


Moreover, the values of Tn at points 1, cos π , cos 2π , · · · , cos (n−1)π , −1 are alternately
n
n
n
1
and − 2n−1
...
Then
(n−1)π
P (x) − Cn (x) at points 1, cos π , · · · , cos n , −1 alternately takes positive and negative
n
values
...
However, P − Cn is a polynomial of degree n − 1 as
the monomial xn is canceled, so we have arrived at a contradiction
...
Since P [i] (x) = (−2)i−1 (−1)x for x = 0, 1,
...


8
...


9
...

The condition P (x) ≥ 0 for all x implies that the αi are even, whereas the condition P (x) ≥ 0
for x ≥ 0 implies that (∀i) αi is even or ai < 0
...

10
...

√
√
√
If r is a root of the polynomial Q, we have P ( r) = −( r − 1)(br + d) and P (− r) =
√
√
( r+1)(br+d)
...
Hence there must be a zero of P between − r and r
...
Let us write P (x) = (x − x1 ) · · · (x − xm )(x2 − p1 x + q1 ) · · · (x2 − pn x + qn ), where the
polynomials x2 − pk x + qk have no real zeros
...
e
...

k

(∗)

Let a ± bi be the zeros of the polynomial x2 − pk x + qk (and also of the polynomial P )
...

12
...

Comparing the leading coefficients we conclude that P is also monic
...
Since P (x2 ) and Q(x2 ) are coprime
(if they have a common zero, so do P and Q), it follows that Q(x2 ) = Q(x)2 and hence
Q(x) = xn for some n ∈ N
...

Let P (x) = a0 + a1 x + · · · + am−1 xm−1 + xm
...
Clearly, this is only possible if a = 0, or a = 2 and 2m − n = 0
...
Since P is symmetric with respect to point 0, it is easy to show that P is also a polynomial
in x2 , so there is a polynomial Q such that P (x) = Q(x2 + 1) or P (x) = xQ(x2 + 1)
...
The substitution x2 + 1 = y yields Q(y 2 + 1) = Q(y)2 + 1, resp
...

Suppose that yQ(y 2 + 1) = (y − 1)Q(y)2 + 1
...
Note that
if a = 0 and Q(a) = 1 then aQ(a2 + 1) = (a − 1) + 1, so Q(a2 + 1) = 1 as well
...
We conclude that Q ≡ 1
...
Now we easily come to all solutions:
these are the polynomials of the form T (T (· · · (T (x)) · · · )), where T (x) = x2 + 1
...
Let us denote P (1) = a
...
Since P (x) = (x − 1)P1 (x) + a,
substituting in the original equation and simplifying yields (x − 1)P1 (x)2 + 2aP1 (x) = 4(x +
1)P1 (2x2 − 1)
...
e
...
Assume that
P (x) = (x − 1)n Q(x) + a, where Q(1) = 0
...
We conclude that P (x) = a
...
At first, note that there exists x = a for which P (a)2 = Q(a)2
...
Then we also have P (b) = Q(b)
for b = 1 + a + P (a)2
...

16
...
For every x the triple (a, b, c) = (6x, 3x, −2x) satisfies the condition ab + bc + ca = 0
...
Since K(i) is negative for odd
i and positive for i = 0 and even i ≥ 6, ai = 0 is only possible for i = 2 and i = 4
...
It is easily verified that all such
P (x) satisfy the conditions
...
Let d be the degree of P
...
, d + 1
...


20

Olympiad Training Materials, www
...
org
...
imocompendium
...
Polynomial Q might not have integral coefficients, so we cannot deduce
that n − m | Q(n) − Q(m), but it certainly has rational coefficients, i
...
there is a natural
number M for which R(x) = M Q(x) has integral coefficients
...
, d + 1
...
, n − d − 1) ≤ M (an − Q(n)) < Cnd
for some constant C independent of n
...
note that Ln is not less than the product (n − 1) · · · (n −
d − 1) divided by the product P of numbers gcd(n − i, n − j) over all pairs (i, j) of different
numbers from {1, 2,
...
Since gcd(n − i, n − j) ≤ i − j, we have P ≤ 1d 2d−1 · · · d
...
Thus, an = Q(n)
for each sufficiently large n, say n > N
...
Hence
an = Q(n) for all n
...
We have shown in 7 from the text that every such t satisfies P (P (t)) = t
...
Suppose that
P (t1 ) = t2 , P (t2 ) = t1 , P (t3 ) = t4 i P (t4 ) = t3 , where t1 = t2,3,4
...
Assume that
t1 − t3 = t2 − t4 , i
...
t1 − t2 = t3 − t4 = k = 0
...
Therefore, we
must have t1 − t3 = t4 − t2 , which gives us P (t1 ) + t1 = P (t3 ) + t3 = c for some c
...

19
...
Then
P (P (x)) − Q(Q(x)) = [Q(P (x)) − Q(Q(x))] + R(P (x))
...
Therefore the degree of Q(P (x)) − Q(Q(x)) is n2 − n + k
...


It remains to check the case of a constant R ≡ c
...


20
...

Since |f (0)| = p, either |g(0)| = 1 or |h(0)| = 1 holds
...
l
...
g
...

Write g(x) = (x− α1 ) · · · (x− αk )
...
Since f (αi )− p = αm (αi − a)n =
i
−p, taking the product over i = 1, 2,
...

Since g(a) divides |g(a)h(a)| = p, we must have |g(a)| = p and n = k
...


Duˇan Djuki´ : Polynomials in One Variable
s
c

21

21
...
Let us consider
n
n
this equality modulo 2
...
The polynomial x2 + x + 1 is
irreducible over Z2 [x], so there exists a natural number k for which g(x) = (x2 + x + 1)k and
n
h(x) = (x2 + x + 1)2 −k ; of course, these equalities hold in Z2 [x] only
...
Thus,
n

[(x2 + x + 1)k + 2U (x)][(x2 + x + 1)2

−k

+ 2V (x)] = F (x)
...
However,
2
4
this is impossible as the polynomial U (x)V (x) has integer coefficients, so U (ǫ)V (ǫ) must be
1
of the form a + bǫ for some a, b ∈ Z (since ǫ2 = −1 − ǫ), which is not the case with 2
...
It is clear, for example by theorem 16, that P must have rational coefficients
...
Let p be a prime number not dividing
1
m
...

Namely, such an x would also satisfy Q(x) = mpP (x) − 1 = 0
...
This proves our claim
...
Denote P (x) = Pn (x) = Rn (x) + iSn (x)
...

This statement is trivially true for n = 1
...


Since Rn + iSn = (x − i + n)(Rn−1 + iSn−1 ), the polynomials Rn and Sn satisfy the
recurrent relations Rn = (x + n)Rn−1 + Sn−1 and Sn = (x + n)Sn−1 − Rn−1
...


If z1 > · · · > zn−2 are the (real) zeros Rn−2 , by the inductive hypothesis we have zi−1 >
yi > zi
...
Now we conclude from the relation
Rn (yi ) = −[(x + n − 1)2 + 1]Rn−2 (yi ) that
sgnRn (yi ) = (−1)i ,
which means that the polynomial Rn has a zero on each of the n intervals (y1 , +∞), (y2 , y1 ),

...
This finishes the induction
...
We first prove the following auxiliary statement
...
If A, B and C are coprime polynomials with A + B = C, then the degree of each
of the polynomials A, B, C is less than the number of different zeros of the polynomial
ABC
...
Let
m

l

k

A(x) =

(x − pi )ai ,

i=1

B(x) =
i=1

(x − qi )bi ,

C(x) =

(x − ri )ci
...
imo
...
yu, www
...
com

22

Let us rewrite the given equality as A(x)/C(x) + B(x)/C(x) = 1 and differentiate it
with respect to x
...
The statement follows from the coprimeness of
A and B
...
We obtain that each of the numbers
a deg P , b deg Q, c deg R is less than deg P + deg Q + deg R, and therefore
1
deg P
>
,
a
deg P + deg Q + deg R
etc
...

25
...
Let P (x) = (x − z1 ) · · · (x − zn ) = xn + an−1 xn−1 + · · · + a0 ,
where |zi | = 1 for i = 1,
...
By the Vieta formulas, an−i = ±σi (z1 ,
...
Therefore, there are at most
i
i
2 m + 1 possible values of the coefficient of P (x) at xn−i for each i
...

r
r
Now consider the polynomial Pr (x) = (x − z1 ) · · · (x − zn ) for each natural number r
...
Therefore, every polynomial Pr satisfies the conditions
of the problem, but there are infinitely many r’s and only finitely many such polynomials
...




---

Title: Basic Of Math Olympiad-Polynomials in One Variable
Description: All basic notes that you need to answer an IMO questions related to Polynomial In One Variable

Buy These NotesPreview