Problem B. 4251. (February 2010)

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

written in base-p numeral system.

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

(5 pont)

Deadline expired on March 10, 2010.

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

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:

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