Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 813. (December 2021)

A. 813. Let \(\displaystyle p\) be a prime number and \(\displaystyle k\) a positive integer. Let

\(\displaystyle t=\sum_{j=0}^{\infty} \left\lfloor\frac{k}{p^j}\right\rfloor. \)

\(\displaystyle a)\) Let \(\displaystyle f(x)\) be a polynomial of degree \(\displaystyle k\) with integer coefficients such that its leading coefficient is 1 and its constant is divisible by \(\displaystyle p\). Prove that there exists \(\displaystyle n\in \mathbb{N}\) for which \(\displaystyle p\mid f(n)\), but \(\displaystyle p^{t+1}\nmid f(n)\).

\(\displaystyle b)\) Prove that the statement above is sharp, i.e. there exists polynomial \(\displaystyle g(x)\) of degree \(\displaystyle k\), integer coefficients, leading coefficient 1 and constant divisible by \(\displaystyle p\) such that if \(\displaystyle p\mid g(n)\) is true for a certain \(\displaystyle n\in \mathbb{N}\), then \(\displaystyle p^t\mid g(n)\) also holds.

Proposed by Kristóf Szabó, Budapest

(7 pont)

Deadline expired on January 10, 2022.


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

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.


Statistics:

10 students sent a solution.
7 points:Bán-Szabó Áron, Ben Gillott, Kovács 129 Tamás, Varga Boldizsár.
2 points:1 student.
1 point:4 students.
0 point:1 student.

Problems in Mathematics of KöMaL, December 2021