Problem B. 5434. (January 2025)

B. 5434. For which positive integers \(\displaystyle m>1\) does there exist polynomial \(\displaystyle f(x)\) with integer coefficients such that exactly one of \(\displaystyle k\) and \(\displaystyle f(k)\) is divisible by \(\displaystyle m\)? (5 points)

Proposed by: Bálint Hujter, Budapest and Géza Kós, Budapest

(5 pont)

Deadline expired on February 10, 2025.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Akkor és csak akkor létezik ilyen \(\displaystyle f(x)\) polinom, ha \(\displaystyle m\) prímszám vagy \(\displaystyle m = 4\).

Tekintsük az \(\displaystyle (m-1)\)-ed fokú \(\displaystyle g_m(x) = (x-1)(x-2)(x-3)\cdots(x-(m-1))\) polinomot. Bármely \(\displaystyle m\) pozitív egész esetén teljesül, hogy ha \(\displaystyle k\) nem osztható \(\displaystyle m\)-mel, a \(\displaystyle (k-1),(k-2),\ldots,(k-(m-1))\) szorzótényezők valamelyike, és így a szorzatuk, \(\displaystyle g_m(k)\) is osztható \(\displaystyle m\)-mel. Ha \(\displaystyle m \mid k\), akkor viszont a \(\displaystyle (k-1),(k-2),\ldots,(k-(m-1))\) szorzótényezők közül egyik sem osztható \(\displaystyle m\)-mel.

• (1. eset) Amennyiben \(\displaystyle m\) prím, ebből következik, hogy a szorzatuk, \(\displaystyle g_m(k)\) sem osztható \(\displaystyle m\)-mel (hiszen ha egy prím csak akkor oszthat egy szorzatot, ha valamelyik szorzótényezőt is osztja).
• (2. eset) Ha \(\displaystyle m=4\) és \(\displaystyle 4 \mid k\), akkor \(\displaystyle (k-1)\) és \(\displaystyle (k-3)\) páratlan, míg a \(\displaystyle (k-2)\) tényező 2 maradékot ad \(\displaystyle 4\)-gyel osztva; azaz egyetlen 2-es prímtényezője van. Így a \(\displaystyle (k-1)(k-2)(k-3)\) szorzatban is csak egyetlen 2-es prímtényező lesz, tehát nem osztható 4-gyel.

Megmutattuk, hogy ha \(\displaystyle m\) prímszám vagy \(\displaystyle 4\), akkor a \(\displaystyle g_m(x) = (x-1)(x-2)(x-3)\cdots(x-(m-1))\) kielégíti a feladat feltételeit.

Azt kell még belátnunk, hogy ezektől különböző \(\displaystyle m\) esetén nem létezik a feltételeket kielégítő \(\displaystyle f(x)\) polinom. Indirekt tegyük fel, hogy létezik ilyen \(\displaystyle f(x)\), ezt írjuk fel \(\displaystyle x^2h(x) + bx + c\) alakban (ha \(\displaystyle f(x) = a_nx^n + a_{n-1}x^{n-1} + \ldots + a_2 x^2 + a_1x + a_0\), akkor \(\displaystyle b = a_1\), \(\displaystyle c=a_0\) és \(\displaystyle h(x) = a_nx^{n-2} + a_{n-1}x^{n-3} + \ldots + a_3x + a_2\)).

• (3. eset) Ha \(\displaystyle m\)-nek van két különböző prímtényezője, akkor felírható \(\displaystyle m = qr\) alakban, ahol \(\displaystyle q\) és \(\displaystyle r\) relatív prímek és \(\displaystyle q,r > 1\). Ekkor \(\displaystyle f(q) = q^2h(q) + bq + c\) osztható \(\displaystyle m\)-mel és így \(\displaystyle q\)-val is, amiből \(\displaystyle c = f(0)\) is osztható \(\displaystyle q\)-val. Ugyanígy \(\displaystyle r \mid f(0)\). Mivel \(\displaystyle q\) és \(\displaystyle r\) relatív prímek, ezért így \(\displaystyle m = qr\) is osztja \(\displaystyle f(0)\)-t, ellentmondásba kerülve az indirekt feltevésünkkel.
• (4.a eset) Legyen most \(\displaystyle m = p^t\), ahol \(\displaystyle p >2\) prím és \(\displaystyle t \geq 2\). Tekintsük a \(\displaystyle k_1 = p^{t-1}\) és \(\displaystyle k_2 = p^{t-1} \cdot (p-1) = p^t-p^{t-1}\) pozitív egész számokat (\(\displaystyle k_1 < k_2\) a \(\displaystyle p > 2\) feltevésünk miatt). Mivel \(\displaystyle m\) nem osztja \(\displaystyle k_i\)-t, ezért \(\displaystyle f(k_i)\) osztható \(\displaystyle m\)-mel az indirekt feltevésünk szerint. Mivel \(\displaystyle t \geq 2\) és így \(\displaystyle 2(t-1) \geq t\), ezért \(\displaystyle p^t\) osztja \(\displaystyle k_1^2\)-et és \(\displaystyle k_2^2\)-et is, tehát \(\displaystyle b k_i + c = f(k_i) - k_i^2 h(k_i) \) osztható \(\displaystyle m\)-mel \(\displaystyle i=1\) és \(\displaystyle i=2\) esetén is. Következésképpen

\(\displaystyle m = p^t \quad \text{ osztja a } \quad (b k_2 + c) - (b k_1 + c) = b (k_2 - k_1) = b (p-2) p^{t-1} \quad \text{különbséget.} \)

Innen \(\displaystyle p \mid b(p-2)\), tehát \(\displaystyle p \mid b\) (mivel \(\displaystyle p>2\) prím). Így \(\displaystyle m = pk_1\) osztja \(\displaystyle bk_1\)-et, azaz \(\displaystyle m\) osztja \(\displaystyle c\)-t is. Ez ellentmond az indirekt feltevésünknek, hiszen \(\displaystyle c=f(0)\).

• (4.b eset) Ha \(\displaystyle m = 2^t\), ahol \(\displaystyle t \geq 4\), akkor az előző esethez hasonlóan járunk el, de most \(\displaystyle k'_1 = 2^{t-2}\) és \(\displaystyle k'_2 = 3 \cdot 2^{t-2} = m - 2^{t-2}\). Mivel \(\displaystyle t \geq 4\), ezért \(\displaystyle 2(t-2) \geq t\), azaz \(\displaystyle 2^t\) osztja \(\displaystyle k_i^2\)-et. Ezért (tudva, hogy \(\displaystyle m \mid f(k_i)\)), megint megkaptuk, hogy \(\displaystyle b k_i + c = f(k_i) - k_i^2 h(k_i) \) osztható \(\displaystyle m\)-mel, és így

\(\displaystyle m = 2^t \quad \text{osztja a} \quad (b k_2 + c) - (b k_1 + c) = b (k_2 - k_1) = 3 \cdot 2^{t-2} \cdot b \quad \text{különbséget.} \)

Ebből \(\displaystyle 4 \mid b\), azaz \(\displaystyle 2^t \mid b k_1\) és így \(\displaystyle 2^t\) osztja \(\displaystyle c = f(0)\)-t, ellentmondva az indirekt feltevésünknek.

• (4.c eset) Már csak az \(\displaystyle m=8\) eset maradt ki. Ekkor írjuk \(\displaystyle f(x)\)-et \(\displaystyle x^3 i(x) + ax^2 + bx +c\) alakban. Mivel egy páros szám köbe mindig osztható 8-cal, ezért tudjuk, hogy l c l c l \(\displaystyle 8 \mid f(2)\) \(\displaystyle \Longrightarrow\) \(\displaystyle 8 \mid 4a + 2b + c\)
  \(\displaystyle 8 \mid f(4)\) \(\displaystyle \Longrightarrow\) \(\displaystyle 8 \mid 16 a + 4b + c\) \(\displaystyle \Longrightarrow\) \(\displaystyle 8 \mid 4b + c\)
  \(\displaystyle 8 \mid f(6)\) \(\displaystyle \Longrightarrow\) \(\displaystyle 8 \mid 36a + 6b + c\) \(\displaystyle \Longrightarrow\) \(\displaystyle 8 \mid 4a - 2b + c\)

Az alsó és a felső sor együtt implikálja, hogy \(\displaystyle 8 \mid 4b\), ez a középső sorral együtt azt jelenti, hogy \(\displaystyle 8 \mid c\), azaz \(\displaystyle 8 \mid f(0)\), ellentmondva az indirekt feltevésnek.

Megjegyzés. Ha \(\displaystyle m\) prím, akkor az \(\displaystyle x^{m-1}-1\) polinom is teljesíti a feltételeket – lényegében ez a kis Fermat-tétel állítása. Valójában ez nem különbözik lényegesen az \(\displaystyle (x-1)(x-2)\cdot \ldots \cdot (x-m+1)\) polinomtól, mivel belátható, hogy minden együtthatójuk megegyezik modulo \(\displaystyle m\) tekintve. Világos, hogy egy polinom bármelyik együtthatóját \(\displaystyle m\)-mel növelve vagy csökkentve nem változik semmi a feladat feltételeinek szempontjából.

Statistics:

61 students sent a solution.
5 points:	Ali Richárd, Aravin Peter, Bencze Mátyás, Bolla Donát Andor, Görömbey Tamás, Gyenes Károly, Hodossy Réka, Holló Martin, Kovács Benedek Noel, Molnár István Ádám, Pázmándi József Áron, Prohászka Bulcsú, Rajtik Sándor Barnabás, Sárdinecz Dóra, Sha Jingyuan, Szabó 721 Sámuel, Tamás Gellért, Török Eszter Júlia, Varga 511 Vivien, Vigh 279 Zalán, Vödrös Dániel László, Wágner Márton.
4 points:	Bodor Noémi, Csató Hanna Zita , Kun Zsófia, Li Mingdao, Zhai Yu Fan.
2 points:	6 students.
1 point:	17 students.
0 point:	9 students.

Problems in Mathematics of KöMaL, January 2025