Problem B. 4997. (December 2018)
B. 4997. Consider the following sequence \(\displaystyle p_n(x)\) of polynomials with integer coefficients: let \(\displaystyle p_0(x)=0\), \(\displaystyle p_1(x)=1\), and for all \(\displaystyle n\ge 2\) let
\(\displaystyle p_n(x)=p_{n-1}(x)+x\cdot p_{n-2}(x). \)
Prove that if a polynomial \(\displaystyle f(x)\) divides the polynomials \(\displaystyle p_n(x)\) and \(\displaystyle p_m(x)\) for some positive integers \(\displaystyle n\), \(\displaystyle m\) then it also divides the polynomial \(\displaystyle p_{(m,n)}(x)\).
(\(\displaystyle (n,m)\) denotes the greatest common divisor of \(\displaystyle n\) and \(\displaystyle m\). A polynomial \(\displaystyle P(x)\) divides a polynomial \(\displaystyle Q(x)\) if there exists a polynomial \(\displaystyle R(x)\) of real coefficients for which \(\displaystyle Q(x)=P(x)R(x)\).)
(6 pont)
Deadline expired on January 10, 2019.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Először néhány egyszerű észrevételt igazolunk.
Teljes indukcióval adódik a rekurzió segítségével, hogy \(\displaystyle n\geq 1\) esetén \(\displaystyle p_n(x)\) olyan egész együtthatós polinom, melynek konstans tagja 1.
Mivel \(\displaystyle 0<n\)-re \(\displaystyle p_n\) konstans tagja 1, ezért ekkor \(\displaystyle x\nmid p_n(x)\). Ebből teljes indukcióval következik, hogy két, a sorozatban egymást követő polinom mindig relatív prím: legnagyobb közös osztójuk konstans polinom. Ha ugyanis \(\displaystyle f(x)\mid p_{n-1} (x)\) és \(\displaystyle f(x)\mid p_{n}(x)\), akkor a rekurzió alapján \(\displaystyle f(x)\mid xp_{n-2}(x)\), amiből \(\displaystyle x\nmid f(x)\) miatt (ami teljesül, hiszen \(\displaystyle x\) nem osztja a \(\displaystyle p_n(x)\) polinomokat \(\displaystyle n>1\) mellett) \(\displaystyle f(x)\mid p_{n-2}\) következik. Ezt a lépést ismételgetve pedig végül \(\displaystyle f(x)\mid p_1(x)=1\)-hez jutunk. Tehát a sorozat szomszédos tagjainak legnagyobb közös osztója konstans.
Először megmutatjuk, hogy \(\displaystyle 2\leq k\leq n-1\) esetén
| \(\displaystyle p_n(x)=p_{k}(x)p_{n-k+1}(x)+(p_{k+1}(x)-p_k(x))p_{n-k}(x). \) | \(\displaystyle {(*)}\) |
Ha \(\displaystyle k=2\), akkor a feltétel a megadott rekurzió alapján teljesül, hiszen \(\displaystyle p_3(x)=x+1\), és így valóban
\(\displaystyle p_{2}(x)p_{n-1}(x)+(p_{3}(x)-p_2(x))p_{n-2}(x)=p_{n-1}(x)+xp_{n-2}(x)=p_n(x).\)
Ha az állítást \(\displaystyle k\)-ra már igazoltuk, akkor a rekurziót használva
\(\displaystyle p_n(x)=p_{k}(x)p_{n-k+1}(x)+(p_{k+1}(x)-p_k(x))p_{n-k}(x)=\)
\(\displaystyle =p_{k}(x)(p_{n-k}(x)+xp_{n-k-1}(x))+(p_{k+1}(x)-p_k(x))p_{n-k}(x)=\)
\(\displaystyle =p_{k+1}(x)p_{n-k}(x)+xp_k(x)p_{n-k-1}(x)=p_{k+1}(x)p_{n-k}(x)+(p_{k+2}(x)-p_{k+1}(x))p_{n-k-1}(x),\)
vagyis az állítás \(\displaystyle k+1\)-re is teljesül. Tehát indukcióval következik, hogy minden \(\displaystyle 2\leq k\leq n-1\) mellett teljesül a \(\displaystyle (*)\) állítás.
Most megmutatjuk, hogy ha \(\displaystyle f(x)\) osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomoknak, és mondjuk \(\displaystyle n\geq m\), akkor \(\displaystyle f(x)\) osztója a \(\displaystyle p_{n-m}(x)\) polinomnak is. Innen az állítás már következik, ugyanis az euklideszi algoritmust követve ilyen lépésekkel előbb-utóbb eljutunk oda, hogy \(\displaystyle f(x)\) osztója a \(\displaystyle p_{(m,n)}(x)\) polinomnak is.
Írjuk fel \(\displaystyle (*)\)-ot \(\displaystyle k=n-m\) választással:
\(\displaystyle p_n(x)=p_{n-m}(x)p_{m+1}(x)+(p_{n-m+1}(x)-p_{n-m}(x))p_{m}(x).\)
Ebből leolvasható, hogy \(\displaystyle f(x)\) osztója a \(\displaystyle p_n(x)\) és \(\displaystyle p_m(x)\) polinomoknak, akkor \(\displaystyle f(x)\) osztója a \(\displaystyle p_{n-m}(x)p_{m+1}(x)\) polinomnak is.
Most felhasználjuk, hogy \(\displaystyle p_m\) és \(\displaystyle p_{m+1}\) relatív prímek, és így \(\displaystyle f(x)\mid p_m(x)\) miatt \(\displaystyle f\) és \(\displaystyle p_{m+1}\) is azok: legnagyobb közös osztójuk konstans. Így \(\displaystyle f(x)\mid p_{n-m}(x)p_{m+1}(x)\) oszthatóságból következik, hogy \(\displaystyle f(x)\mid p_{n-m}(x)\) is teljesül.
Ebből pedig a korábbiak szerint az euklideszi algoritmust követve adódik, hogy \(\displaystyle f(x)\) valóban osztója \(\displaystyle p_{(m,n)}(x)\) polinomnak is.
Statistics:
24 students sent a solution. 6 points: Baski Bence, Beke Csongor, Bencsik Ádám, Dobák Dániel, Győrffi Ádám György, Kerekes Anna, Kovács 129 Tamás, Nagy Nándor, Pooya Esmaeil Akhoondy, Soós 314 Máté, Stomfai Gergely, Szabó 417 Dávid, Szabó 991 Kornél, Tóth 827 Balázs, Velich Nóra, Weisz Máté, Zsigri Bálint. 5 points: Várkonyi Zsombor. 4 points: 2 students. 3 points: 1 student. 2 points: 2 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, December 2018