 |
Az A. 792. feladat (2021. január) |
A. 792. Legyen \(\displaystyle p\ge 3\) prímszám és \(\displaystyle 0\le r\le p-3\). Legyen \(\displaystyle x_1, x_2, \ldots, x_{p-1+r}\) egész számok, melyekre \(\displaystyle \sum\limits_{j=1}^{p-1+r} x_j^k\equiv r~ \textrm{(mod}\ p\textrm{)}\) minden \(\displaystyle 1\le k\le p-2\)-re.
Mik lehetnek az \(\displaystyle x_1,x_2,\ldots ,x_{p-1+r}\) számok maradékai modulo \(\displaystyle p\)?
Javasolta: Matolcsi Dávid (Budapest)
(7 pont)
A beküldési határidő 2021. február 15-én LEJÁRT.
Legyen \(\displaystyle g\) primitív egységgyök modulo \(\displaystyle p\). A nem \(\displaystyle 0\) maradékokat felírom \(\displaystyle 1\), \(\displaystyle g\), \(\displaystyle g^2\), \(\displaystyle g^3\),...,\(\displaystyle g^{p-2}\) alakban.
Az \(\displaystyle x_1\), \(\displaystyle x_2\),...\(\displaystyle x_{p-1+r}\) számok között \(\displaystyle a_i\) darab \(\displaystyle g^i\) értékű van.
Legyen \(\displaystyle f(y)=a_0+a_1y+a_2y^2+...+a_{p-2}y^{p-2}\).
\(\displaystyle 1\le k\le p-2\)-re \(\displaystyle f(g^k)=\sum x_i^k \equiv r\,(\text{mod} p)\) .
Tehát \(\displaystyle f(y)-r\)-nek \(\displaystyle F_p\) (a mod \(\displaystyle p\) maradékok teste) fölött gyöke a \(\displaystyle 0\) és az \(\displaystyle 1\) kivételével az összes maradék.
\(\displaystyle f(y)-r\) egy legfeljebb \(\displaystyle p-2\) fokú polinom, tehát ez csak úgy lehetséges, ha \(\displaystyle f(y)-r\equiv 0\) vagy \(\displaystyle f(y)-r\equiv c(y^{p-2}+...+y^2+y+1)\) valamilyen \(\displaystyle c\)-re modulo \(\displaystyle p\).
Mivel az \(\displaystyle a_i\) értékek pozitívak és az összegük a nemnulla \(\displaystyle x_j\) maradékok száma, ami legfeljebb \(\displaystyle p-1+r\), ezért \(\displaystyle f(y)-r\equiv 0\) csak úgy érhető el, ha \(\displaystyle f(y)=r\).
\(\displaystyle f(y)-r\equiv c(y^{p-2}+...+y^2+y+1)\) általánosan úgy érhető el, ha \(\displaystyle f(y)=y^{p-2}+...+y+(r+1)\). (Itt használjuk, hogy \(\displaystyle r\le p-3\), azaz \(\displaystyle p-1+r\le 2p-4\), tehát c=2 csak úgy lenne lehetséges, ha nincs 0-s és 1-es maradékú szám, és a többi maradékból 2 van, ez viszont nem ad jó megoldást, mert ekkor a maradékok összege \(\displaystyle p-2\)-vel kongruens.)
Átírva arra, hogy melyik maradékból hány van az \(\displaystyle x\)-ek közül, ezek lehetnek a megoldások:
\(\displaystyle r\) darab \(\displaystyle 1\) és \(\displaystyle p-1\) darab \(\displaystyle 0\), illetve
a nem \(\displaystyle 0\) és nem \(\displaystyle 1\) maradékok közül mindből egy darab, és az \(\displaystyle 1\)-ből \(\displaystyle r+1\) darab.
Könnyen ellenőrizhető, hogy ezek valóban mind jó megoldások.
Statisztika:
4 dolgozat érkezett. 7 pontot kapott: Fleiner Zsigmond, Füredi Erik Benjámin, Simon László Bence. 1 pontot kapott: 1 versenyző.
A KöMaL 2021. januári matematika feladatai