Problem B. 4827. (November 2016)

B. 4827. Suppose that \(\displaystyle p\) is a polynomial of integer coefficients, not identically 0, such that \(\displaystyle p(n)\) is divisible by 2016 for all integers \(\displaystyle n\). What is the minimum possible value of the sum of the absolute values of the coefficients of \(\displaystyle p\)?

(5 pont)

Deadline expired on December 12, 2016.

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

Megoldás. Mivel \(\displaystyle p\) nem azonosan 0, ezért együtthatói abszolút értékének összege legalább 1. Ha pontosan 1, akkor \(\displaystyle p(x)=\pm x^k\) alakú, azonban ez a polinom például \(\displaystyle x=1\) esetén olyan értéket vesz fel, ami nem osztható 2016-tal. Beláttuk tehát, hogy egy, a feladat feltételeinek eleget tevő polinom együtthatói abszolút értékének összege legalább 2 kell legyen.

Keressünk egy megfelelő polinomot \(\displaystyle p(x)=x^a-x^b\) alakban. Mivel \(\displaystyle p\) egész együtthatós, ezért elegendő, ha \(\displaystyle p(1)\), \(\displaystyle p(2)\), \(\displaystyle \dots\), \(\displaystyle p(2016)\) mind oszthatók 2016-tal. Legyen \(\displaystyle 1\leq i\leq 2016\) tetszőleges. Az \(\displaystyle 1\), \(\displaystyle i\), \(\displaystyle i^2\), \(\displaystyle i^3\), \(\displaystyle \dots\) sorozat periodikus moduló 2016, tegyük fel, hogy az első ,,tiszta'' periódus \(\displaystyle i^{n_i}\)-nél kezdődik, és a periódus hossza \(\displaystyle k_i\). Legyen \(\displaystyle b=\max(n_1,n_2,\dots,n_{2016})\) és \(\displaystyle a=b+[k_1,k_2,\dots,k_{2016}]\). Ekkor az \(\displaystyle i^a\) és \(\displaystyle i^b\) számok ugyanazt a maradékot adják 2016-tal osztva, hiszen \(\displaystyle a\geq b\geq n_i\) és \(\displaystyle k_i|b-a\). Ez minden \(\displaystyle 1\leq i\leq 2016\) esetén igaz, így egy megfelelő polinomot kaptunk.

Tehát egy, a feladat feltételeinek eleget tevő polinomban az együtthatók abszolút értékének összege legalább 2 (és lehet is 2).

Megjegyzés. Az Euler-Fermat tétel felhasználásával megmutatható, hogy a \(\displaystyle p(x)=x^{\varphi(2016)+5}-x^5\) polinom megfelel a feltételeknek. Legyen ugyanis \(\displaystyle n\) tetszőleges egész szám, \(\displaystyle q^{\alpha}\) pedig 2016 egy prímhatvány osztója. Ha \(\displaystyle q\nmid n\), akkor az Euler-Fermat tétel szerint \(\displaystyle n^{\varphi(2016)}-1\) osztható \(\displaystyle q^{\alpha}\)-nal, hiszen \(\displaystyle \varphi(q^\alpha)\mid \varphi(2016)\). Így \(\displaystyle q^\alpha\mid p(n)\) is teljesül. Ha pedig \(\displaystyle q\mid n\), akkor mivel \(\displaystyle \alpha\leq 5\) (ugyanis \(\displaystyle 2016=2^5\cdot 3^2\cdot 7\)), ezért \(\displaystyle q^\alpha\mid n^5\) miatt szintén teljesül, hogy \(\displaystyle q^\alpha\mid p(n)\).

Statistics:

71 students sent a solution.
5 points:	Baran Zsuzsanna, Csuha Boglárka, Daróczi Sándor, Dobák Dávid, Döbröntei Dávid Bence, Fajszi Bulcsú, Gál Hanna, Gáspár Attila, Győrffy Ágoston, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Kiss Gergely, Klász Viktória, Kocsis Júlia, Kovács 246 Benedek, Kőrösi Ákos, Kővári Péter Viktor, Molnár Bálint, Nagy Nándor, Németh 123 Balázs, Schrettner Jakab, Simon Dániel Gábor, Sulán Ádám, Tiszay Ádám, Tóth Viktor, Vágó Ákos, Vári-Kakas Andor, Weisz Máté.
4 points:	Alexy Milán, Besenyi Tibor, Borbényi Márton, Busa 423 Máté, Csiszár Zoltán, Dömsödi Bálint, Harsányi Benedek, Harsch Leila, Keresztfalvi Bálint, Kocsis Anett, Kovács 526 Tamás, Matolcsi Dávid, Radnai Laszló, Saár Patrik, Schrettner Bálint, Sokvári Olivér, Szabó 417 Dávid, Szakály Marcell, Szemerédi Levente, Török Tímea.
3 points:	3 students.
2 points:	1 student.
1 point:	17 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, November 2016