A B. 4251. feladat (2010. február)

B. 4251. Legyen \(\displaystyle p>3\) prímszám. Határozzuk meg a

\(\displaystyle \sum_{i=1}^{p} \binom{i\cdot p}{p}\cdot\binom{(p-i+1)p}{p} \)

szám utolsó két számjegyét a \(\displaystyle p\) alapú számrendszerben.

Mészáros Gábor (Kemence) javaslata nyomán

(5 pont)

A beküldési határidő 2010. március 10-én LEJÁRT.

Megoldás. A megoldáshoz szükségünk lesz a következő észrevételre: ha két \(\displaystyle p\)-vel nem osztható egész szám \(\displaystyle p\)-vel osztva ugyanannyi maradékot ad, a hányadosuk pedig egész szám, akkor az \(\displaystyle p\)-vel osztva 1 maradékot ad. Vagyis, ha az \(\displaystyle a,b,x\) egész számokra \(\displaystyle ax\equiv b\pmod{p}\) és \(\displaystyle a\equiv b\not\equiv0\pmod{p}\), akkor \(\displaystyle x\equiv 1\pmod{p}\). Ugyanis ha \(\displaystyle a(x-1)=ax-a\) osztható \(\displaystyle p\)-vel, akkor \(\displaystyle x-1\) is osztható kell legyen \(\displaystyle p\)-vel. Ugyanígy látható, hogy ha \(\displaystyle a\) nem osztható \(\displaystyle p\)-vel, akkor \(\displaystyle c_1\not\equiv c_2\pmod{p}\) esetén \(\displaystyle ac_1\not\equiv ac_2\pmod{p}\). Ugyanezek az állítások akkor is igazak maradnak, ha \(\displaystyle p\)-vel nem osztható számok esetén a maradékokat modulo \(\displaystyle p^2\) tekintjük.

Legyen most \(\displaystyle k\) tetszőleges nemnegatív egész szám. Ekkor a \(\displaystyle (kp+1)(kp+2)\ldots(kp+p-1)\) szorzatot teljesen kibontva, abban majdnem minden tag osztható lesz \(\displaystyle p^2\)-tel, vagyis

\(\displaystyle (kp+1)\ldots(kp+p-1)\equiv (p-1)!+ kp(p-1)!\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{p-1}\right)\pmod{p^2}.\)

Mivel \(\displaystyle (p-1)!\) nem osztható \(\displaystyle p\)-vel, és az \(\displaystyle 1,2,\ldots,p-1\) számok \(\displaystyle p\)-vel osztva mind különböző maradékot adnak, azért a \(\displaystyle p\)-vel nem osztható

\(\displaystyle \frac{(p-1)!}{1},\frac{(p-1)!}{2},\ldots,\frac{(p-1)!}{p-1}\)

számok is mind különböző maradékot adnak, vagyis

\(\displaystyle (p-1)!\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{p-1}\right)\equiv 1+2+\ldots+(p-1)\equiv 0\pmod{p}.\)

Ezért

\(\displaystyle (kp+1)(kp+2)\ldots(kp+p-1)\equiv (p-1)!\pmod{p^2},\)

ahonnan

\(\displaystyle {{(k+1)p}\choose{p}} ={\frac{(k+1)p}{p}}\cdot{{kp+p-1}\choose{p-1}}\equiv k+1\pmod{p^2}.\)

Ennek alapján pedig

\(\displaystyle \sum_{i=1}^{p} {{ip}\choose{p}}\cdot{{(p-i+1)p}\choose{p}} \equiv\sum_{i=1}^p i(p+1-i)=(p+1)\sum_{i=1}^pi-\sum_{i=1}^pi^2=\)

\(\displaystyle =(p+1)\cdot\frac{p(p+1)}{2}-\frac{p(p+1)(2p+1)}{6}=p\cdot\frac{(p+1)(p+2)}{6} \pmod{p^2}.\)

A \(\displaystyle p>3\) feltétel miatt \(\displaystyle (p+1)(p+2)\) osztható 6-tal. Innen látszik, hogy a szám maga \(\displaystyle p\)-vel osztható, vagyis \(\displaystyle p\) alapú számrendszerben az utolsó számjegy 0. Az utolsó előtti számjegy meghatározásához azt kell megnézni, hogy a \(\displaystyle \frac{(p+1)(p+2)}{6}\) szám milyen maradékot ad \(\displaystyle p\)-vel osztva. Ha \(\displaystyle p\) 6-tal osztva 1 maradékot ad, vagyis alkalmas \(\displaystyle k\) pozitív egész számmal \(\displaystyle p=6k+1\), akkor

\(\displaystyle \frac{(p+1)(p+2)}{6}=\frac{(6k+2)(6k+3)}{6}=6k^2+5k+1=pk+4k+1 \equiv \frac{2p+1}{3}\pmod{p},\)

ha pedig a \(\displaystyle p\) prím \(\displaystyle 6k-1\) alakú, akkor

\(\displaystyle \frac{(p+1)(p+2)}{6}=\frac{(6k)(6k+1)}{6}=6k^2+k=kp+2k\equiv \frac{p+1}{3}\pmod{p}.\)

Tehát annak megfelelően, hogy a \(\displaystyle p\) prím 6-tal osztva 1 vagy 5 maradékot ad, az utolsó két számjegy \(\displaystyle \frac{2p+1}{3}\) és 0, illetőleg \(\displaystyle \frac{p+1}{3}\) és 0.

Statisztika:

19 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Cséke Balázs, Damásdi Gábor, Éles András, Janzer Olivér, Kovács 729 Gergely, Márkus Bence, Mester Márton, Perjési Gábor, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Weisz Ágoston, Weisz Gellért, Zsakó András.
4 pontot kapott:	Mészáros András, Nagy Balázs, Nagy Róbert.
3 pontot kapott:	1 versenyző.

A KöMaL 2010. februári matematika feladatai