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