Maths Olympiad Prep

Library / /1375 of 1394

, 2022

Algebra Difficulty 6.3 National Olympiad Prove it United States

Problem:

Suppose P(x)P(x) is a monic polynomial of degree 20232023 such that
P(k)=k2023P(11k) P(k) = k^{2023} P\left(1 - \frac{1}{k}\right)
for every positive integer 1k20231 \leq k \leq 2023. Then P(1)=abP(-1) = \frac{a}{b}, where aa and bb are relatively prime integers. Compute the unique integer 0n<20270 \leq n < 2027 such that bnab n - a is divisible by the prime 20272027.

Solution

Solution:

Let n=2023n = 2023. If P(x)=xn+an1xn1++a0P(x) = x^{n} + a_{n-1} x^{n-1} + \cdots + a_{0}, then let
R(x)=xnP(11x)=(x1)n+an1(x1)nx++a0xn R(x) = x^{n} P\left(1 - \frac{1}{x}\right) = (x-1)^{n} + a_{n-1}(x-1)^{n} x + \cdots + a_{0} x^{n}
Then, note that Q(x)=P(x)R(x)Q(x) = P(x) - R(x) is a polynomial of degree at most nn, and it has roots 1,2,,n1, 2, \ldots, n, so we have Q(x)=k(x1)(xn)Q(x) = k(x-1) \cdots (x-n) for some real constant kk. Now we determine P(x)P(x) in terms of Q(x)Q(x). If g(x)=11/xg(x) = 1 - 1 / x, then g(g(x))=11xg(g(x)) = \frac{1}{1-x} and g(g(g(x)))=xg(g(g(x))) = x. Therefore, we have
P(x)xnP(11x)=Q(x)P(11x)(11x)nP(11x)=Q(11x)P(11x)(11x)nP(x)=Q(11x). \begin{aligned} P(x) - x^{n} P\left(1 - \frac{1}{x}\right) & = Q(x) \\ P\left(1 - \frac{1}{x}\right) - \left(1 - \frac{1}{x}\right)^{n} P\left(\frac{1}{1-x}\right) & = Q\left(1 - \frac{1}{x}\right) \\ P\left(\frac{1}{1-x}\right) - \left(\frac{1}{1-x}\right)^{n} P(x) & = Q\left(\frac{1}{1-x}\right) . \end{aligned}
Adding the first equation, xnx^{n} times the second, and (x1)n(x-1)^{n} times the third yields
2P(x)=Q(x)+xnQ(x1x)+(x1)nQ(11x), 2 P(x) = Q(x) + x^{n} Q\left(\frac{x-1}{x}\right) + (x-1)^{n} Q\left(\frac{1}{1-x}\right),
so
P(x)=k2((x1)(x2)(xn)+(0x1)(1x1)((n1)x1)+(1x+0)(2x+1)(nx+(n1))). \begin{aligned} & P(x) = \frac{k}{2} \big((x-1)(x-2) \cdots (x-n) + (0 x - 1)(-1 x - 1) \cdots (-(n-1) x - 1) \\ & \qquad + (-1 x + 0)(-2 x + 1) \cdots (-n x + (n-1))\big) . \end{aligned}
Therefore,
P(1)=k2((n+1)!+0+(2n+1)!!) P(-1) = \frac{k}{2} (-(n+1)! + 0 + (2n+1)!!)
Also, since PP is monic, we know that
1=k2(1+0n!) 1 = \frac{k}{2} (1 + 0 - n!)
so
P(1)=(2n1)!!(n+1)!1n! P(-1) = \frac{(2n-1)!! - (n+1)!}{1 - n!}
Modulo 20272027, (n+1)!=2024!1(n+1)! = 2024! \equiv -1 and n!=2023!1n! = 2023! \equiv 1 (by Wilson's theorem and properties of factorials mod prime). Also, (2n+1)!!0(2n+1)!! \equiv 0. So our answer is
1/211/6=3520305=406 \frac{1/2}{1 - 1/6} = \frac{3}{5} \equiv \frac{2030}{5} = 406

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.