 |
Az A. 813. feladat (2021. december) |
A. 813. Legyen \(\displaystyle p\) prímszám és \(\displaystyle k\) pozitív egész. Legyen továbbá
\(\displaystyle t=\sum_{j=0}^{\infty} \left\lfloor\frac{k}{p^j}\right\rfloor. \)
\(\displaystyle a)\) Legyen \(\displaystyle f(x)\) egy egész együtthatós, \(\displaystyle 1\) főegyütthatós, \(\displaystyle k\)-adfokú polinom, amelynek a konstans tagját osztja \(\displaystyle p\). Bizonyítsuk be, hogy létezik \(\displaystyle n\in \mathbb{N}\), amelyre \(\displaystyle p\mid f(n)\), de \(\displaystyle p^{t+1}\nmid f(n)\).
\(\displaystyle b)\) Bizonyítsuk be, hogy a fenti állítás éles, azaz létezik olyan egész együtthatós, \(\displaystyle 1\) főegyütthatós, \(\displaystyle k\)-adfokú \(\displaystyle g(x)\) polinom, amelynek a konstans tagját osztja \(\displaystyle p\), és ha egy \(\displaystyle n\in \mathbb{N}\) esetén \(\displaystyle p\mid g(n)\) teljesül, akkor \(\displaystyle p^t\mid g(n)\) is igaz.
Javasolta: Szabó Kristóf (Budapest)
(7 pont)
A beküldési határidő 2022. január 10-én LEJÁRT.
Megoldás. Először a következő állítást látjuk be: ha egy \(\displaystyle n\)-edfokú \(\displaystyle p(x)\) polinom minden egész helyen egész értéket vesz fel, akkor léteznek olyan \(\displaystyle a_0\), \(\displaystyle a_1\),..., \(\displaystyle a_n\) egész értékek, melyekre
\(\displaystyle p(x)=a_n\binom{x}{n}+a_{n-1}\binom{x}{n-1}+...+a_1\binom{x}{1}+a_0. \)
(Itt \(\displaystyle \binom{x}{i}\) az \(\displaystyle i\)-edfokú \(\displaystyle x(x-1)...(x-i+1)/i!\) polinomot jelöli.)
Ezt az állítást \(\displaystyle n\) szerinti teljes indukcióval igazoljuk. \(\displaystyle n=0\) esetén az állítás nyilvánvaló. Ha pedig \(\displaystyle n\ge 1\), akkor tekintsük a \(\displaystyle q(x)=p(x+1)-p(x)\) polinomot. Ez egy legfeljebb \(\displaystyle n-1\)-edfokú polinom, amely az indukciós feltevés szerint felírható alkalmas \(\displaystyle b_0\), \(\displaystyle b_1\),..., \(\displaystyle b_{n-1}\) egészekkel
\(\displaystyle b_{n-1}\binom{x}{n-1}+b_{n-2}\binom{x}{n-2}+...+b_0 \)
alakban. Legyen ezután
\(\displaystyle r(x)=b_{n-1}\binom{x}{n}+b_{n-2}\binom{x}{n-1}+...+b_0\binom{x}{1}+p(0). \)
A jól ismert \(\displaystyle \binom{x+1}{n}=\binom{x}{n}+\binom{x}{n-1}\) (polinom)azonosság miatt \(\displaystyle r(x+1)-r(x)=q(x)\) (is) teljesül, és definíció szerint \(\displaystyle p(0)=r(0)\). Ezekből teljes indukcióval könnyű belátni, hogy \(\displaystyle p(k)=q(k)\) teljesül minden pozitv egész \(\displaystyle k\) számra. Az pedig jól ismert, hogy ha két valós együtthatós polinom értéke végtelen sok helyen megegyezik, akkor a két polinom is megegyezik, ahonnan \(\displaystyle p(x)=r(x)\), és a bizonyítandóval készen vagyunk.
Ebből az állításból nekünk csak annyira lesz szükségünk, hogy ha egy \(\displaystyle n\)-edfokú polinom minden egész helyen egész értéket vesz fel, akkor az együtthatóinak \(\displaystyle n!\)-szorosa egész szám, ami a fenti állítás alapján nyilvánvaló, hiszen \(\displaystyle k\le n\) esetén az \(\displaystyle n!\binom{x}{k}\) polinom egész együtthatós. Ezt az állítást fogjuk a feladatban felhasználni.
a) Az állítást indirekt úton látjuk be. Legyen egy ellenpélda az \(\displaystyle f(x)\) polinom. Tekintsük most a \(\displaystyle g(x)=f(xp)/p^{t+1}\) polinomot. Mivel \(\displaystyle f(x)\) konstans tagja osztható \(\displaystyle p\)-vel, ezért ha \(\displaystyle x\) egy \(\displaystyle p\)-vel osztható egész szám, akkor \(\displaystyle f(x)\) is osztható \(\displaystyle p\)-vel. Emiatt és az indirekt feltevés miatt a \(\displaystyle g(x)\) polinom minden egész helyen egész értéket vesz fel. A korábban bizonyított állítás szerint tehát \(\displaystyle k!g(x)\) egész együtthatós. Ennek a polinomnak a főegyütthatója \(\displaystyle k!p^k/p^{t+1}\), ami viszont a Legendre-formula alapján nem egész szám, mert az előző tört nevezőjében \(\displaystyle p\) kitevője eggyel nagyobb, mint a számlálójában.
b) A fenti bizonyítás alapján nem nehéz példát mutatni: a \(\displaystyle g(x)=x(x-p)(x-2p)...(x-kp+p)\) polinom 1 főegyütthatós, \(\displaystyle k\)-ad fokú, és egész \(\displaystyle n\)-re \(\displaystyle p|g(n)\) akkor és csak akkor teljesül, ha \(\displaystyle p|n\). Ilyen esetekben pedig \(\displaystyle n\)-et \(\displaystyle a\cdot p\) alakban felírva \(\displaystyle g(n)=p^kk!\binom{a}{k}\), vagyis \(\displaystyle g(n)\) osztható \(\displaystyle p^kk!\)-sal, ez utóbbi pedig ismét a Legendre-formula alapján osztható \(\displaystyle p^t\)-nel.
Statisztika:
10 dolgozat érkezett. 7 pontot kapott: Bán-Szabó Áron, Ben Gillott, Kovács 129 Tamás, Varga Boldizsár. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 4 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2021. decemberi matematika feladatai