Maths Olympiad Prep

Library / /190 of 520

Number theory Difficulty 6.2 National olympiad Prove it

Show that there exists an integer aa for which a336a2+51a97a^{3}-36 a^{2}+51 a-97 is a multiple of 320083^{2008}.

Solution

Define the polynomial P(x)=x336x2+51x97P(x)=x^{3}-36 x^{2}+51 x-97. Starting from P0(x)=181P(9x+1)=9x333x22x1P_{0}(x)=\frac{1}{81} P(9 x+1)=9 x^{3}-33 x^{2}-2 x-1, define recursively polynomials Pk(x)=P_{k}(x)= 3akx3+3bkx2+ckx+dk3 a_{k} x^{3}+3 b_{k} x^{2}+c_{k} x+d_{k} with integers ak,bk,ck,dka_{k}, b_{k}, c_{k}, d_{k}, where ckc_{k} is not divisible by 3, and Pk+1(x)=13Pk(3x+εk)P_{k+1}(x)=\frac{1}{3} P_{k}\left(3 x+\varepsilon_{k}\right) with εk{1,0,1}\varepsilon_{k} \in\{-1,0,1\} for all kk : Since ckc_{k} is not divisible by 3, one can choose εk\varepsilon_{k} such that εkck+dk\varepsilon_{k} c_{k}+d_{k} is divisible by 3; then 13Pk(3x+εk)=3ak+1x3+3bk+1x2+ck+1+dk+1\frac{1}{3} P_{k}\left(3 x+\varepsilon_{k}\right)=3 a_{k+1} x^{3}+3 b_{k+1} x^{2}+c_{k+1}+d_{k+1} with ak+1=9ak,bk+1=9εkak+3bka_{k+1}=9 a_{k}, b_{k+1}=9 \varepsilon_{k} a_{k}+3 b_{k}, ck+1=3(3εk2ak+2εkbk)+ck,dk+1=εk3ak+εk2bk+(εkck+dk)/3c_{k+1}=3\left(3 \varepsilon_{k}^{2} a_{k}+2 \varepsilon_{k} b_{k}\right)+c_{k}, d_{k+1}=\varepsilon_{k}^{3} a_{k}+\varepsilon_{k}^{2} b_{k}+\left(\varepsilon_{k} c_{k}+d_{k}\right) / 3, thus ck+1c_{k+1} is also not divisible by 3.
If we set x2004=0x_{2004}=0 and recursively xk=3xk+1+εkx_{k}=3 x_{k+1}+\varepsilon_{k}, so Pk(xk)=3Pk(xk+1)P_{k}\left(x_{k}\right)=3 P_{k}\left(x_{k+1}\right) for k=2003,,0k=2003, \ldots, 0, then for a=9x0+1a=9 x_{0}+1 the number P(a)=8132004P2004(x2004)P(a)=81 \cdot 3^{2004} P_{2004}\left(x_{2004}\right) is a multiple of 320083^{2008}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.