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