Olympiad Algebra & Functional Equations

Write $P(x)=\sum c_kx^k$. Then $P(a)-P(b)=\sum c_k(a^k-b^k)$, and each $a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})$ is a multiple of $a-b$; with integer $c_k$ so is the sum. The three consequences are the lemma with $b=r$, with $a\equiv b\pmod m$, and with $(a,b)=(x_{i+1},x_i)$. Integer coefficients are essential, not integer values — the sidenote below shows the difference. The lemma turns a question about an unknown polynomial into divisibility among finitely many known numbers, which is why it opens most olympiad problems about $P\in\mathbb Z[x]$.

Step 1 — every integer $r$ is congruent mod $2$ to $0$ or to $1$; call that number $s$.

Step 2 — by the lemma, $r-s$ divides $P(r)-P(s)$, and $r-s$ is even, so $P(r)\equiv P(s)\pmod2$.

Step 3 — $P(s)$ is $P(0)$ or $P(1)$, both odd, so $P(r)$ is odd and in particular not $0$.

How to find it. Information about $P$ at a complete set of residues mod $m$ controls $P$ at every integer. Two values, at $0$ and $1$, form a complete residue system mod $2$.

Step 1 — apply the lemma to the three pairs: $a-b\mid P(a)-P(b)=b-c$, then $b-c\mid c-a$, then $c-a\mid a-b$.

Step 2 — all three differences are nonzero, and a nonzero number divides another nonzero number only if it is not larger in absolute value, so $|a-b|\le|b-c|\le|c-a|\le|a-b|$. All three absolute values equal some $d>0$.

Step 3 — but $(a-b)+(b-c)+(c-a)=0$, a sum of three terms each equal to $+d$ or $-d$. Such a sum is an odd multiple of $d$, never $0$. Contradiction.

How to find it. A polynomial that permutes a few integers produces a closed loop of differences, each dividing the next. Going round the loop forces equal sizes, and the signs cannot then add to zero.

Step 1 — reduce to $k=2$. Let $Q(t)=t$ and follow the orbit $x_0=t$, $x_{i+1}=P(x_i)$, which returns to $x_0$ after $k$ steps. Put $d_i=x_{i+1}-x_i$. By the lemma $d_0\mid d_1\mid\cdots\mid d_{k-1}\mid d_k=d_0$, so all $|d_i|$ are equal, say to $m$. If $m=0$, $t$ is a fixed point of $P$. If $m>0$, the $d_i$ are $\pm m$ and add up to $0$ around the loop, so two consecutive ones have opposite signs: $d_{i+1}=-d_i$, i.e. $x_{i+2}=x_i$. Then $P(P(x_i))=x_i$, and applying $P$ repeatedly shows every point of the orbit, $t$ included, satisfies $P(P(x))=x$.

Step 2 — so it suffices to count integer solutions of $P(P(x))=x$. If all of them are fixed points of $P$, they are roots of $P(x)-x$, which has degree $n$: at most $n$ of them.

Step 3 — otherwise pick $a$ with $P(a)=b\ne a$ and $P(b)=a$. Let $r$ be any integer solution and $s=P(r)$, so $P(s)=r$. The lemma gives $r-a\mid s-b$ and $s-b\mid r-a$, so $r-a=\pm(s-b)$; likewise $r-b=\pm(s-a)$. If both signs are $+$, then $r-s=a-b$ and $r-s=b-a$, forcing $a=b$. So one sign is $-$, and either way $r+s=a+b$.

Step 4 — hence every integer solution is a root of $P(x)+x-(a+b)$, a polynomial of degree $n$ (since $n>1$), so there are at most $n$ of them.

How to find it. Iterating $P$ on integers is a walk along an orbit, and the difference lemma links consecutive steps. Divisibility round a closed loop forces equal step sizes — the same mechanism as in USAMO 1974/1 — and then the problem collapses to period $2$, where the pair $(a,b)$ supplies a second polynomial of degree $n$.

The proof of the lemma used integer coefficients $c_k$; $\tfrac{x(x-1)}2$ has coefficients $\tfrac12$ and $-\tfrac12$. Integer-valued polynomials are exactly the integer combinations of the binomial polynomials $\binom xk$, and for them only the weaker statement holds that $k!$ times the leading coefficient is an integer. So when a problem says "$P(n)$ is an integer for all integers $n$", do not use $a-b\mid P(a)-P(b)$; expand in the basis $\binom xk$ or use finite differences instead.

If $n\mid k$ every term is $1$. Otherwise $q=\omega^k\ne1$ and the sum is the geometric series $\tfrac{q^n-1}{q-1}=0$, because $q^n=(\omega^n)^k=1$. Summing $f(\omega^j)=\sum_ka_k\omega^{jk}$ over $j$ and swapping the order of summation keeps exactly $n$ copies of each $a_k$ with $n\mid k$ and kills the rest. For the divisibility test: $x^2+x+1=(x-\omega)(x-\bar\omega)$, and a real polynomial with $P(\omega)=0$ also has $P(\bar\omega)=\overline{P(\omega)}=0$, so both linear factors divide it. The filter trades a sum over an arithmetic progression of indices for a handful of evaluations, which is how one counts objects whose size or sum lies in a residue class.

Step 1 — filter $f(x)=(1+x)^{12}$ with $n=3$: the sum is $\tfrac13\left(f(1)+f(\omega)+f(\omega^2)\right)$.

Step 2 — since $1+\omega+\omega^2=0$, $1+\omega=-\omega^2=e^{i\pi/3}$, a unit complex number at $60^\circ$ (the figure). So $(1+\omega)^{12}=e^{4\pi i}=1$, and likewise $(1+\omega^2)^{12}=1$.

Step 3 — the sum is $\tfrac{2^{12}+1+1}{3}=\tfrac{4098}{3}=1366$. Check: $1+220+924+220+1=1366$.

How to find it. "Every third coefficient" is a residue class of indices — the filter's job. The key computation is always the polar form of $1+\omega^j$.

Step 1 — by the test, it suffices to evaluate at $\omega=e^{2\pi i/3}$, where $\omega^3=1$, so $\omega^n$ depends only on $n\bmod3$.

Step 2 — if $3\mid n$: $\omega^{2n}+\omega^n+1=1+1+1=3\ne0$, so no.

Step 3 — if $3\nmid n$: $\omega^n$ is $\omega$ or $\omega^2$, and $\omega^{2n}=(\omega^n)^2$ is the other one, so the value is $\omega+\omega^2+1=0$ — yes. The answer is all $n$ not divisible by $3$.

How to find it. Divisibility by a product of cyclotomic factors is a question about the values at their roots, and $x^n$ at a root of unity only sees $n$ modulo the order.

Step 1 — the generating function $f(x)=\prod_{k=1}^{2000}(1+x^k)$ has, as coefficient of $x^s$, the number of subsets with sum $s$. The answer is the sum of the coefficients with $5\mid s$, which the filter gives as $\tfrac15\sum_{j=0}^{4}f(\omega^j)$ with $\omega=e^{2\pi i/5}$.

Step 2 — $f(1)=2^{2000}$.

Step 3 — for $j=1,\dots,4$, $\omega^j$ is a primitive fifth root, and as $k$ runs through $1,\dots,2000$ the powers $\omega^{jk}$ run through all five fifth roots of unity $400$ times each, so $f(\omega^j)=\left(\prod_{r=0}^{4}(1+\omega^r)\right)^{400}$.

Step 4 — from $x^5-1=\prod_{r=0}^4(x-\omega^r)$ at $x=-1$: $-2=\prod(-1-\omega^r)=-\prod(1+\omega^r)$, so $\prod_{r=0}^4(1+\omega^r)=2$ and $f(\omega^j)=2^{400}$.

Step 5 — the count is

How to find it. "Sum divisible by $5$" is a residue class of exponents in a product generating function. Evaluating the product at roots of unity needs one identity, $\prod(x-\omega^r)=x^5-1$, evaluated at a convenient point.

The failing step is treating $x^4+x^2+1$ as if its roots were only $\omega$ and $\bar\omega$. In fact $x^4+x^2+1=(x^2+x+1)(x^2-x+1)$, and the second factor has the primitive sixth roots $e^{\pm i\pi/3}$ as roots. A polynomial is divisible by $D$ exactly when it vanishes at every root of $D$ (with multiplicity), so factor $D$ into cyclotomic pieces and test one root of each piece.