KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

apehman

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 4251. Let p>3 be a prime number. Determine the last two digits of the number


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

written in base-p numeral system.

(Based on the idea of G. Mészáros, Kemence)

(5 points)

Deadline expired on 10 March 2010.


Google Translation (Sorry, the solution is published in Hungarian only.)

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.


Statistics on problem B. 4251.
19 students sent a solution.
5 points:Á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 points:Mészáros András, Nagy Balázs, Nagy Róbert.
3 points:1 student.


  • Problems in Mathematics of KöMaL, February 2010

  • Támogatóink:   Ericsson   Google   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program  
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley