A B. 4290. feladat (2010. szeptember)

B. 4290. Legyenek a és b pozitív egész számok. Tegyük fel, hogy p olyan egész együtthatós polinom, amely az egész helyeken felvesz a-val osztható értéket és b-vel oszthatót is. Igazoljuk, hogy van olyan egész szám, ahol p értéke a és b legkisebb közös többszörösével is osztható.

(5 pont)

A beküldési határidő 2010. október 11-én LEJÁRT.

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.

Statisztika:

29 dolgozat érkezett.
5 pontot kapott:	Á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 pontot kapott:	Kiss 542 Robin, Kúsz Ágnes, Palincza Richárd.
3 pontot kapott:	2 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	4 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2010. szeptemberi matematika feladatai