Problem B. 4290. (September 2010)

B. 4290. Let a and b denote positive integers. Given that p is a polynomial of integer coefficients that has both a value divisible by a and a value divisible by b at integer points. Prove that there is an integer point where the value of p is also divisible by the least common multiple of a and b.

(5 pont)

Deadline expired on October 11, 2010.

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

Megoldás. Válasszunk először olyan egymáshoz relatív prím \(\displaystyle a',b'\) pozitív egész számokat, melyek legkisebb közös többszöröse megegyezik \(\displaystyle a\) és \(\displaystyle b\) legkisebb közös többszörösével, továbbá teljesül még az is, hogy \(\displaystyle a'\) osztja \(\displaystyle a\)-t és \(\displaystyle b'\) osztja \(\displaystyle b\)-t. Ilyen számokat a következő módszerrel találhatunk. Az \(\displaystyle a,b\) számok összes különböző prí mosztóját jelölje \(\displaystyle p_1, p_2, \ldots, p_t\). Legyen \(\displaystyle a=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_t^{\alpha_t}\) és \(\displaystyle b=p_1^{\beta_1}p_2^{\beta_2}\ldots p_t^{\beta_t}\), ahol \(\displaystyle \alpha_i,\beta_i\) nemnegatív egész számok. Ekkor az \(\displaystyle a'=p_1^{\gamma_1}p_2^{\gamma_2}\ldots p_t^{\gamma_t}\) és \(\displaystyle b'=p_1^{\delta_1}p_2^{\delta_2}\ldots p_t^{\delta_t}\) választás megfelelő lesz, ahol \(\displaystyle \alpha_i\ge \beta_i\) esetén \(\displaystyle \gamma_i=\alpha_i\) és \(\displaystyle \delta_i=0\), \(\displaystyle \alpha_i<\beta_i\) esetén pedig \(\displaystyle \gamma_i=0\) és \(\displaystyle \delta_i=\beta_i\).

Legyenek most a feltétel szerint \(\displaystyle x\) és \(\displaystyle y\) olyan egész számok, amelyekre \(\displaystyle a\mid p(x)\) és \(\displaystyle b\mid p(y)\) teljesül. Tegyük fel, hogy a \(\displaystyle z\) egész számra \(\displaystyle a'\mid z-x\) és \(\displaystyle b'\mid z-y\) teljesül. Ekkor \(\displaystyle z-x\mid p(z)-p(x)\), \(\displaystyle z-y\mid p(z)-p(y)\) miatt \(\displaystyle a'\mid p(z)-p(x)\) és \(\displaystyle b'\mid p(z)-p(y)\). Minthogy \(\displaystyle a'\mid a\) és \(\displaystyle b'\mid b\), kapjuk hogy \(\displaystyle a'\mid p(x)\), \(\displaystyle b'\mid p(y)\), vagyis a \(\displaystyle p(z)\) szám osztható \(\displaystyle a'\)-vel és \(\displaystyle b'\)-vel is. Ezért ekkor \(\displaystyle p(z)\) osztható lesz \(\displaystyle a'\) és \(\displaystyle b'\) legkisebb közös többszörösével is, ami választásunk miatt megegyezik \(\displaystyle a\) és \(\displaystyle b\) legkisebb közös többszörösével.

Most már csak annyit kell megmutatni, hogy létezik olyan \(\displaystyle z\) egész szám, amely eleget tesz a fenti oszthatósági feltételeknek. Az \(\displaystyle 1,2,\ldots, a'\) számok között van pontosan egy, amely \(\displaystyle a'\)-vel osztva ugyanolyan maradékot ad, mint \(\displaystyle x\). Jelöljük ezt a számot \(\displaystyle r\)-rel, és tekintsük az \(\displaystyle r+a',r+2a',\ldots,r+b'a'\) számokat; ezek mindegyike ugyanolyan maradékot ad \(\displaystyle a'\)-vel osztva, mint az \(\displaystyle x\) szám. Ezek a számok \(\displaystyle b'\)-vel osztva páronként különböző maradékot adnak, hiszen ha \(\displaystyle r+ia'\) és \(\displaystyle r+ja'\) ugyanolyan maradékot ad, akkor különbségük, \(\displaystyle (j-i)a'\) osztható \(\displaystyle b'\)-vel. Mivel \(\displaystyle a'\) és \(\displaystyle b'\) relatív prímek, ez azt jelenti, hogy \(\displaystyle j-i\) is osztható \(\displaystyle b'\)-vel, ami \(\displaystyle 1\le i,j\le b'\) miatt csak \(\displaystyle i=j\) esetén lehetséges. Az \(\displaystyle r+a',r+2a',\ldots,r+b'a'\) számok között tehát van pontosan egy, amely \(\displaystyle b'\)-vel osztva ugyanolyan maradékot ad, mint \(\displaystyle y\); ezt választhatjuk \(\displaystyle z\)-nek.

Statistics:

29 students sent a solution.
5 points:	Ágoston Péter, Beke Lilla, Csuka Róbert, Damásdi Gábor, Dudás 002 Zsolt, Fonyó Viktória, Gyarmati Máté, Janzer Olivér, Karl E. Holter, Lenger Dániel, Nagy Róbert, Perjési Gábor, Strenner Péter, Szabó 928 Attila, Varnyú József, Weisz Gellért, Zilahi Tamás.
4 points:	Kiss 542 Robin, Kúsz Ágnes, Palincza Richárd.
3 points:	2 students.
1 point:	2 students.
0 point:	4 students.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, September 2010