Problem B. 4401. (November 2011)
B. 4401. Let p=3n+1 be a prime number. Is it possible for the numbers to leave pairwise different remainders when divided by p?
(5 pont)
Deadline expired on December 12, 2011.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. A megoldás során felhasználjuk az
\(\displaystyle 1^3+2^3+\ldots+k^3=(1+2+\ldots+k)^2\)
azonosságot, valamint azt a tényt, hogy modulo \(\displaystyle p\) egy \(\displaystyle k\)-adfokú polinomnak legfeljebb \(\displaystyle k\) különböző gyöke lehet.
Tegyük fel, hogy az \(\displaystyle 1^3,2^3,\ldots,n^3\) számok mind különböző maradékot adnak \(\displaystyle p\)-vel osztva. Legyenek ezek \(\displaystyle m_1,m_2,\ldots,m_n\). Ha egy \(\displaystyle p\)-vel nem osztható \(\displaystyle a\) szám köbe \(\displaystyle m\) maradékot ad \(\displaystyle p\)-vel osztva, akkor a kis Fermat-tétel szerint \(\displaystyle m^n\equiv a^{p-1}\equiv 1\pmod{p}\), tehát modulo \(\displaystyle p\) az \(\displaystyle m\) szám gyöke az \(\displaystyle x^n-1\) polinomnak. Ezek szerint ennek a polinomnak pontosan \(\displaystyle n\) darab különböző gyöke van modulo \(\displaystyle p\), nevezetesen \(\displaystyle m_1,m_2,\ldots,m_n\), és az \(\displaystyle 1^3,2^3,\ldots,(3n)^3\) számok mindegyike ezek valamelyikével egyenlő. Az \(\displaystyle 1,2,\ldots,3n\) számok mindegyike kielégíti tehát modulo \(\displaystyle p\) az \(\displaystyle x^3=m_i\) egyenletek valamelyikét. Mivel egy ilyen egyenletnek legfeljebb 3 megoldása lehet modulo \(\displaystyle p\), ez csak úgy lehet, hogy mindegyiknek pontosan 3 különböző megoldása van.
Mármost \(\displaystyle 1^3+2^3+\ldots+(3n)^3=(1+2+\ldots+3n)^2=(3np/2)^2\) osztható \(\displaystyle p\)-vel. Másrészt a fentiek szerint
\(\displaystyle 1^3+2^3+\ldots+(3n)^3=3(m_1+m_2+\ldots+m_n)\equiv 3(1^3+2^3+\ldots+n^3)=\)
\(\displaystyle =3(1+2+\ldots+n)^2= \frac{3n^2(n+1)^2}{4}\pmod{p},\)
és itt a jobb oldalon álló szám nyilván nem osztható \(\displaystyle p\)-vel. Ellentmondásra jutottunk, ami azt jelenti, hogy az \(\displaystyle 1^3,2^3,\ldots,n^3\) számok között kell legyen kettő, ami ugyanolyan maradékot ad \(\displaystyle p\)-vel osztva.
Statistics:
13 students sent a solution. 5 points: Ágoston Tamás, Gyarmati Máté, Kiss 902 Melinda Flóra, Mester Márton, Nagy Róbert, Strenner Péter, Szabó 928 Attila, Viharos Andor. 2 points: 3 students. 1 point: 1 student. 0 point: 1 student.
Problems in Mathematics of KöMaL, November 2011