Problem A. 792. (January 2021)
A. 792. Let \(\displaystyle p\ge 3\) be a prime number and \(\displaystyle 0\le r\le p-3\). Let \(\displaystyle x_1, x_2, \ldots, x_{p-1+r}\) be integer numbers satisfying \(\displaystyle \sum_{j=1}^{p-1+r}x_j^k\equiv r~ \textrm{(mod}\ p\textrm{)}\) for all \(\displaystyle 1\le k\le p-2\).
What are the possible remainders of numbers \(\displaystyle x_1,x_2,\ldots,x_{p-1+r}\) modulo \(\displaystyle p\)?
Submitted by Dávid Matolcsi, Budapest
(7 pont)
Deadline expired on February 15, 2021.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
4 students sent a solution. 7 points: Fleiner Zsigmond, Füredi Erik Benjámin, Simon László Bence. 1 point: 1 student.
Problems in Mathematics of KöMaL, January 2021