Vieta and symmetric functions, multiple roots via gcd(p,p′), integer polynomials, Lagrange interpolation and finite differences, roots of unity and filters.
Division and roots. For every p and a we have p(x)=(x−a)q(x)+p(a). So a is a root exactly when (x−a)∣p, and a nonzero polynomial of degree n has at most n roots.
Identity principle. Two polynomials of degree ≤n that agree at n+1 points are equal: their difference has n+1 roots.
Fundamental theorem of algebra. Every p∈C[x] of degree n≥1 can be written p(x)=an(x−x1)⋯(x−xn).
Vieta's formulas. If p(x)=anxn+an−1xn−1+⋯+a0 has roots x1,…,xn, then
Proof. Expand an∏i(x−xi): the coefficient of xn−k collects all products of k roots, with sign (−1)k.
Vieta and symmetric functions
Every symmetric polynomial in the roots is a polynomial in e1,…,en, so it can be computed from the coefficients without finding the roots. In practice you need the power sums sk=x1k+⋯+xnk and Newton's identities:
s1=e1,s2=e1s1−2e2,s3=e1s2−e2s1+3e3.
For k>n we have sk=e1sk−1−e2sk−2+⋯+(−1)n−1ensk−n. Proof: each root satisfies xin=e1xin−1−e2xin−2+⋯+(−1)n−1en; multiply by xik−n and sum.
The first one (the logarithmic derivative) is the basic tool for polynomials with only real roots: differentiating again, (p′/p)′=−∑i(x−xi)−2<0 away from the roots.
Trick. If s2=e12−2e2<0 for a polynomial with real coefficients, then not all roots are real.
Multiple roots and gcd(p,p′)
Lemma.a is a root of p of multiplicity ≥2 if and only if p(a)=p′(a)=0. More generally, a root of p of multiplicity exactly m≥1 is a root of p′ of multiplicity exactly m−1.
Proof. If p=(x−a)mq with q(a)=0, then p′=(x−a)m−1(mq+(x−a)q′), and the bracket equals mq(a)=0 at a.
Consequence.p∈C[x] has simple roots if and only if gcd(p,p′)=1. For example xn−1 has n distinct roots, since the only root of nxn−1 is 0. The gcd is computed by the Euclidean algorithm, so you do not need to know the roots.
Integer polynomials
Lemma. If p∈Z[x] and a,b∈Z, then (a−b)∣p(a)−p(b).
Proof.ak−bk=(a−b)(ak−1+ak−2b+⋯+bk−1), and p(a)−p(b) is an integer linear combination of such differences.
Consequences: if a≡b(modm) then p(a)≡p(b)(modm); so if p(0) and p(1) are both odd, p has no integer root (every integer is ≡0 or 1(mod2)).
Rational roots. If p(x)=anxn+⋯+a0∈Z[x] and r/s is a root with gcd(r,s)=1, then r∣a0 and s∣an.
Proof. Multiply p(r/s)=0 by sn: anrn+an−1rn−1s+⋯+a0sn=0. All terms except a0sn are divisible by r, so r∣a0sn and, since gcd(r,s)=1, r∣a0. Similarly s∣anrn, so s∣an.
Example: for 2x3−x2+2x−1 the candidate roots are ±1,±21, and indeed 2x3−x2+2x−1=(2x−1)(x2+1).
Lagrange interpolation and finite differences
For distinct x0,…,xn and values y0,…,yn there is exactly one polynomial of degree ≤n with p(xi)=yi:
p(x)=i=0∑nyij=i∏xi−xjx−xj.
Existence: each term equals yi at xi and 0 at the other nodes. Uniqueness: the identity principle. Comparing coefficients of xn gives a useful identity: for degq≤n, the coefficient of xn in q equals ∑iq(xi)/∏j=i(xi−xj).
Finite differences. Define (Δp)(x)=p(x+1)−p(x). If degp=n≥1 with leading coefficient c, then degΔp=n−1 with leading coefficient nc, since (x+1)n−xn=nxn−1+…. Hence Δnp=n!c and Δn+1p=0. Writing Δ=E−I with (Ep)(x)=p(x+1), the binomial theorem gives
Newton's formula. Every p of degree ≤n can be written p(x)=∑k=0n(Δkp)(0)(kx), where (kx)=k!x(x−1)⋯(x−k+1). (Both sides have degree ≤n and the same differences at 0.)
Integer values. If p has degree ≤n and takes integer values at n+1 consecutive integers m,…,m+n, then p(Z)⊆Z. Proof: apply Newton's formula to p(x+m); the differences (Δkp)(m) are integers, and the (kx) take integer values at every integer. Careful: such a polynomial does not necessarily have integer coefficients, e.g. 2x(x−1).
Roots of unity
Let ω=e2πi/n. The roots of xn−1 are 1,ω,…,ωn−1, so xn−1=∏k=0n−1(x−ωk).
Lemma (sum). For an integer j,
k=0∑n−1ωjk={n,0,n∣j,n∤j.
Proof. If n∣j every term is 1. Otherwise ωj=1 and the geometric series gives ωj−1ωjn−1=0.
Root-of-unity filter. If P(x)=∑jajxj, then
j≡r(modn)∑aj=n1k=0∑n−1ω−krP(ωk).
Proof. The right-hand side is ∑jaj⋅n1∑kωk(j−r), and the inner sum is 1 or 0 by the lemma. The classic example, with n=3 and P(x)=(1+x)m:
j∑(3jm)=32m+2cos(mπ/3),
since 1+ω=eiπ/3 and 1+ω2=e−iπ/3.
The lemma as rotating vectors, and the filter for n=3
Averaging over the roots (Parseval). If degP<N and ζ=e2πi/N, then N1∑k=0N−1∣P(ζk)∣2=∑j∣aj∣2. Expand ∣P∣2=PP and apply the lemma: only the terms ajal with j=l survive, since ∣j−l∣<N. So if ∣P∣≤M on the unit circle, then ∑j∣aj∣2≤M2.
Cyclotomic polynomials.Φd(x)=∏(x−ζ), the product over the primitived-th roots of unity, has degree φ(d) and integer coefficients, and
xn−1=d∣n∏Φd(x).
For a prime p we have Φp(x)=1+x+⋯+xp−1. E.g. Φ3=x2+x+1, Φ4=x2+1, Φ6=x2−x+1, Φ12=x4−x2+1.
Divisibility test. If Q has simple roots, then Q∣P if and only if P vanishes at every root of Q. When Q is a product of cyclotomic polynomials its roots are roots of unity, and the condition becomes arithmetic on the exponents mod n. Example: x2+x+1∣x2m+xm+1 if and only if 3∤m.
A useful identity: setting x=1 in x−1xn−1=∏k=1n−1(x−ωk) gives ∏k=1n−1(1−ωk)=n.
Conjugate roots
Lemma. If p has real coefficients and p(z)=0, then p(zˉ)=0, with the same multiplicity.
Proof. Since the coefficients are real, p(zˉ)=p(z)=0. For the multiplicity apply the same to p′,p′′,… (the multiple-root lemma).
Consequences: p∈R[x] factors into real linear and quadratic factors; a real polynomial of odd degree has a real root.
The same idea for rational coefficients: if a,b∈Q, b=0, d∈/Q and p(a+bd)=0 with p∈Q[x], then p(a−bd)=0. Proof: divide p by m(x)=(x−a)2−b2d∈Q[x], p=mq+(rx+s) with r,s∈Q. At a+bd you get r(a+bd)+s=0; since d is irrational, r=0 and then s=0. So m∣p.
Rouché (optional)
If f,g are holomorphic on an open set containing the closed disc ∣z∣≤R and ∣g(z)∣<∣f(z)∣ on the circle ∣z∣=R, then f and f+g have the same number of zeros (with multiplicity) in the disc ∣z∣<R. Example: for z5−5z+1 take f=−5z, g=z5+1; on ∣z∣=1 we have ∣g∣≤2<5=∣f∣, so there is exactly one root in the open unit disc.
How it appears in the IMC
Symmetric functions. In IMC 2000, Day 1, Problem 2 the two equations, after dividing by w−z, are written in terms of w+z and wz. In IMC 2024, Problem 1 the condition on the unit circle becomes a polynomial equation that factors.
Logarithmic derivative. In IMC 1998, Day 1, Problem 5 (a polynomial with only real roots) you start from p′/p=∑i(x−xi)−1.
Multiplicities. In IMC 2000, Day 2, Problem 3 you count roots of p and p−1 together with their multiplicities, using that they have the same derivative.
Integer values and differences. IMC 2007, Day 1, Problem 1; IMC 2011, Day 2, Problem 4; IMC 2020, Problem 4 (an equation of the form Δp=q).
Roots of unity. IMC 2008, Day 2, Problem 1 (divisibility of polynomials through their roots); IMC 2007, Day 1, Problem 6 (integer coefficients and a bound on the unit circle, where the Parseval average helps).
Degree and leading coefficient. In IMC 2025, Problem 1 a geometric question becomes an equation for a polynomial, and everything is decided by its degree.
Pitfalls
Multiplicities in Vieta's formulas. The x1,…,xn are counted with multiplicity. Do not assume they are distinct.
Integer values = integer coefficients.(2x) takes integer values but has the coefficient 21.
The filter needs all n roots. If you forget the term k=0 (that is, P(1)), the result is wrong.
Conjugate root only for real coefficients.x−i has the root i but not −i.