A B. 5293. feladat (2023. január)

B. 5293. Legyen \(\displaystyle p\) egy prímszám. Legfeljebb hány egész együtthatós polinom adható meg úgy, hogy semelyik kettő különbsége ne legyen minden egész helyen \(\displaystyle p^2\)-tel osztható?

Javasolta: Pach Péter Pál (Budapest)

(6 pont)

A beküldési határidő 2023. február 10-én LEJÁRT.

Megoldás. Megmutatjuk, hogy a válasz \(\displaystyle p^{3p}\).

Legyen \(\displaystyle f(x)=a_nx^n+\dots+a_2x^2+a_1x+a_0\) egy egész együtthatós polinom. Tekintsük \(\displaystyle f(x_0+kp)\)-t modulo \(\displaystyle p^2\) (egyelőre \(\displaystyle x_0\) és \(\displaystyle k\) bármely egész lehet). Ehhez először meghatározzuk \(\displaystyle (x_0+kp)^t\) értékét a binomiális tétel felhasználásával \(\displaystyle t>0\) esetén:

\(\displaystyle (x_0+kp)^t\equiv x_0^t+tkpx_0^{t-1} \pmod{p^2},\)

hiszen a további tagokban \(\displaystyle p\) kitevője már legalább 2. Ha pedig \(\displaystyle t=0\), akkor \(\displaystyle (x_0+kp)^t=x_0^t\), második tag ekkor nincs. Ezek alapján

ahol

\(\displaystyle f'(x_0):=\sum\limits_{t=1}^n ta_tx_0^{t-1}.\)

(Formálisan \(\displaystyle f'\) éppen \(\displaystyle f\) deriváltja, de most nem \(\displaystyle \mathbb{R}\to \mathbb{R}\) függvényként tekintünk rá.)

A \(\displaystyle (*)\) kongruenciából már látható, hogy ha előírjuk \(\displaystyle f(x_0) \pmod{p^2}\) és \(\displaystyle f'(x_0)\pmod {p}\) értékét \(\displaystyle x_0=0,1,\dots,p-1\) esetén, az már meghatározza \(\displaystyle f(x_0+kp)\pmod {p^2}\) értékét minden \(\displaystyle k\)-ra (és minden \(\displaystyle 0\leq x_0\leq p-1\)-re), vagyis minden egész \(\displaystyle x\) helyen meghatározza \(\displaystyle f(x) \pmod{p^2}\) értékét. Ez azt jelenti, hogy ha valamely \(\displaystyle f_1\) és \(\displaystyle f_2\) polinomok különbsége nem osztható \(\displaystyle p^2\)-tel minden egész helyen, akkor az \(\displaystyle f_1(x_0) \pmod{p^2}\) és \(\displaystyle f_1'(x_0)\pmod {p}\) értékek sorozata nem lehet ugyanaz, mint az \(\displaystyle f_2(x_0) \pmod{p^2}\) és \(\displaystyle f_2'(x_0)\pmod {p}\) értékek sorozata (\(\displaystyle 0\leq x_0\leq p-1\)-re). A maradékok ilyen sorozata \(\displaystyle (p^2)^pp^p=p^{3p}\)-féle lehet, így ennél több polinom biztosan nem adható meg.

Az is világos, hogy ha az \(\displaystyle f_1\) és \(\displaystyle f_2\) polinomokra a maradékok fenti (\(\displaystyle 2p\) hosszú) sorozata nem egyezik meg, akkor különbségük nem lehet minden egész helyen \(\displaystyle p^2\)-tel osztható. Ha ugyanis

\(\displaystyle f_1(x_0)+kpf_1'(x_0)\equiv f_2(x_0)+kpf_2'(x_0) \pmod {p^2}\)

minden \(\displaystyle 0\leq x_0\leq p-1\) és \(\displaystyle k\in \mathbb{Z}\) esetén, akkor \(\displaystyle k=0\) választás alapján \(\displaystyle f_1(x_0)\equiv f_2(x_0) \pmod{p^2}\) minden \(\displaystyle 0\leq x_0\leq p-1\)-re, és így \(\displaystyle k=1\) szerint \(\displaystyle pf'_1(x_0)\equiv pf'_2(x_0)\pmod{p^2}\), amiből \(\displaystyle f'_1(x_0)\equiv f'_2(x_0)\pmod{p}\), szintén minden \(\displaystyle 0\leq x_0\leq p-1\) mellett.

Ahhoz, hogy belássuk, megadható \(\displaystyle p^{3p}\) darab polinom megfelelő módon, elég megmutatni, hogy az \(\displaystyle a_i,b_i\) maradékok tetszőleges sorozata esetén van olyan \(\displaystyle f\) polinom, melyre \(\displaystyle f(i)\equiv a_i \pmod{p^2}\) és \(\displaystyle f'(i)\equiv b_i \pmod {p}\) teljesül minden \(\displaystyle i=0,1,\dots,p-1\) esetén.

Keressük \(\displaystyle f\)-et az alábbi alakban:

\(\displaystyle f(x)=\sum\limits_{i=0}^{p-1}Q_i(x)R_i(x),\)

ahol

\(\displaystyle Q_i(x)=c_i(x-i)+d_i\)

és

\(\displaystyle R_i(x)=\prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (x-j)^2.\)

Legyen \(\displaystyle 0\leq i \leq p-1\) tetszőleges. Tekintsük először \(\displaystyle f(i) \pmod{p^2}\) értékét. Az \(\displaystyle f\)-et adó \(\displaystyle p\)-tagú összegben egyetlen kivételtől eltekintve mindegyik szorzatban szerepel az \(\displaystyle (x-i)^2\) tényező, így ezek a tagok \(\displaystyle p^2\)-tel oszthatók. Így

\(\displaystyle f(i)\equiv Q_i(i)R_i(i)\equiv d_i\prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (i-j)^2\pmod {p^2}.\)

Mivel a \(\displaystyle \prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (i-j)^2\) szorzat nem osztható \(\displaystyle p\)-vel, ezért \(\displaystyle d_i\) alkalmas megválasztásával elérhető, hogy

\(\displaystyle f(i)\equiv d_i\prod\limits_{\substack{0\leq j\leq p-1,\\ j\ne i}} (i-j)^2\equiv a_i\pmod {p^2}\)

legyen. Ha ugyanis \(\displaystyle d_i\) helyére egy (mod \(\displaystyle p^2\)) teljes maradékrendszert helyettesítünk, akkor a szorzat is egy teljes maradékrendszert alkot mod \(\displaystyle p^2\), hiszen \(\displaystyle p\nmid v\) esetén \(\displaystyle u_1v\equiv u_2v\pmod {p^2}\) pontosan akkor teljesül, ha \(\displaystyle u_1\equiv u_2\pmod {p^2}\). Rögzítsük tehát \(\displaystyle d_i\) értékét úgy, hogy \(\displaystyle f(i)\equiv a_i\pmod {p^2}\) legyen.

Térjünk rá \(\displaystyle f'(i) \pmod{p}\) értékére. Korábban már megjegyeztük, hogy \(\displaystyle f'\) éppen \(\displaystyle f\) deriváltja. A derivált tulajdonságai alapján egy összeg deriváltja az összeadandók deriváltjának összege, továbbá, ha egy polinomnak egy szám legalább kétszeres gyöke, akkor a deriváltjának is gyöke. Ezért

\(\displaystyle f'(i)=\sum\limits_{j=0}^{p-1} \left(Q_j'(i)R_j(i)+Q_j(i)R_j'(i)\right)=Q_i'(i)R_i(i)+Q_i(i)R_i'(i)=c_iR_i(i)+d_iR_i'(i),\)

hiszen \(\displaystyle j\ne i\) esetén \(\displaystyle R_j(i)=R'_j(i)=0\).

Mivel \(\displaystyle R_i(i)\not\equiv 0\pmod {p}\), ezért \(\displaystyle c_i\) megválasztható úgy, hogy \(\displaystyle f'(i)\equiv b_i\pmod {p}\) legyen. (Egy mod \(\displaystyle p\) teljes maradékrendszert helyettesítve \(\displaystyle c_i\) helyére \(\displaystyle c_iR_i(i)\), és így \(\displaystyle c_iR_i(i)+d_iR'_i(i)\) is egy-egy mod \(\displaystyle p\) teljes maradékrendszeren fut végig.) Tehát valóban minden \(\displaystyle 2p\) hosszú maradéksorozathoz megadható megfelelő polinom.

Ezzel igazoltuk, hogy legfeljebb \(\displaystyle p^{3p}\) darab polinom adható meg a feltételeknek megfelelően (és ennyi valóban meg is adható.)

Statisztika:

12 dolgozat érkezett.
6 pontot kapott:	Csonka Illés, Czirják Márton Pál, Szakács Ábel, Varga Boldizsár.
5 pontot kapott:	Fülöp Csilla, Wiener Anna.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2023. januári matematika feladatai