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