Opravovatelia

Michal Staník [email protected]

Začnime tým, že si spočítame počet spôsobov, ako možno rozmiestniť $p$ vojakov do zadanej tabuľky. Ak už riešite úlohu $10$, malo by to byť jednoduché cvičenie z kombinatoriky. Máme $p^2$ políčok, z nich chceme vybrať $p$, vojaci sú nerozlíšiteľní, takže na poradí nezáleží. Počet možností teda vieme vyjadriť kombinačným číslom $\binom{p^2}{p}$. Od toho ale ešte musíme odpočítať možnosti, ktoré zadanie vylučuje – keď sú všetci vojaci v jednom riadku. Takých možností je $p$, pretože máme $p$ riadkov a ak sú v nejakom riadku všetci vojaci, môže to byť iba jedným spôsobom – zaberajú všetky políčka. Chceme teda dokázať, že $$\left. p^5\ \middle|\ \binom{p^2}{p} - p.\right.$$ Postupne budeme tento výraz upravovať, zjednodušovať a vynímať z neho $p$, až dokým nebudeme mať päť $p$-čok (v súčine), ktoré sme z neho vyňali alebo ktoré ho delia. Poďme na to! Začnime rozpísaním kombinačného čísla podľa definície ako $$\begin{align} \binom{p^2}{p} - p &= \frac{p^2(p^2-1)\cdots(p^2-p+1)}{p!} - p = p\left(\frac{(p^2-1)\cdots(p^2-p+1)}{(p-1)(p-2)\cdots 1} - 1 \right).\end{align}$$ Prvé $p$ sme vyňali, chceme teda ešte nájsť štyri $p$-čka v prvočíselnom rozklade veľkej zátvorky. Tú môžeme vynásobiť $(p-1)!$, pretože toto číslo je nesúdeliteľné s prvočíslom $p$, a teda chceme, aby $p^4$ delilo výraz $$\begin{align} (p^2 - 1)(p^2 - 2)\cdots(p^2 - (p - 1)) - (p - 1)!.\end{align}$$ Predstavme si, že začneme roznásobovať tie zátvorky v člene naľavo od mínus. Z každej vyberieme $p^2$ alebo malé číslo (menšie ako $p$) s mínusom. Ak vyberieme aspoň dvakrát člen $p^2$, dostaneme niečo deliteľné $p^4$, čo nás pri určovaní deliteľnosti $p^4$ nezaujíma. Zaujímajú nás teda členy, kedy vyberieme práve jedno $p^2$ (a zo všetkých zátvoriek vyberieme malé číslo) alebo žiadne $p^2$. Žiadne $p^2$ sa dá iba jedným spôsobom, kedy dostaneme $(p-1)!$ (mínusov je párny počet), čo sa nasčíta na nulu s $-(p-1)!$, ktorý už vo výraze máme.

Aké členy dostaneme s vybraním práve jedného $p^2$? Zo všetkých ostatných zátvoriek vyberieme malé číslo, máme tak súčin všetkých čísel od $-1$ do $-(p-1)$, kde jedno číslo chýba (to zo zátvorky, z ktorej sme vyberali $p^2$). To vieme zapísať ako $\frac{(p-1)!}{-i}$, ak $i$ je to chýbajúce číslo. Dostali sme $$\begin{align} p^2 \left(\frac{(p-1)!}{-1} + \frac{(p-1)!}{-2} + \dots + \frac{(p-1)!}{-(p-1)}\right).\end{align}$$

Z Eulerovej vety vieme, že ak $\phi(n)$ je počet čísel menších alebo rovných $n$ nesúdeliteľných s $n$, tak pre všetky $a$ nesúdeliteľné s $n$ platí $$\begin{align} a^{\phi(n)} &\equiv 1 \pmod{n}, \ a\cdot a^{\phi(n)-1} &\equiv 1 \pmod{n}.\end{align}$$ Ďalej platí $\phi(p^2) = p^2 - p$, takže inverzné prvky (ktoré sa vynásobia s číslom na jednotku) dostaneme umocnením na $p^2 - p - 1$.

Späť k nášmu výrazu: vyňali sme ďalšie dve $p$-čka, takže už iba chceme, aby $p^2$ delilo výraz $$\frac{(p-1)!}{1} + \frac{(p-1)!}{2} + \dots + \frac{(p-1)!}{p-1} \equiv(p-1)!(1^{p^2-p-1} + \dots + (p-1)^{p^2-p-1}) \pmod{p^2}.$$ Je jedno, že sme to prenásobili mínus jednotkou, deliteľnosť to nezmení.

Činiteľ $(p-1)!$ je nesúdeliteľný s $p^2$ a je v súčine so zvyškom výrazu, môžeme ho teda dať preč, nemá vplyv na deliteľnosť $p^2$. Členy v zátvorke popárujeme (člen $a^{p^2-p-1}$ s členom $(p-a)^{p^2-p-1}$) a pomocou binomickej vety (umocňovanie súčtu) máme $$\begin{align} \sum_{a=1}^{\frac{p-1}{2}}\left(a^{p^2-p-1} + (p-a)^{p^2-p-1}\right) &= \sum_{a=1}^{\frac{p-1}{2}}\left(a^{p^2-p-1} + p^2(\dots) + p(p^2-p-1)a^{p^2-p-2}-a^{p^2-p-1}\right) \equiv\ &\equiv\sum_{a=1}^{\frac{p-1}{2}}p(p^2-p-1)a^{p^2-p-2} \pmod{p^2}. \end{align}$$

Člen $p^2(\dots)$ reprezentuje nejaké členy súčtu, kde je $p$ v aspoň druhej mocnine, a teda sú všetky deliteľné $p^2$, čiže nás nezaujímajú.

Výborne, máme ďalšie vyňaté $p$. Ostáva ukázať, že $$\begin{align} &\left. p\ \middle|\ (p^2-p-1)\sum_{a=1}^{\frac{p-1}{2}} a^{p^2-p-2},\right. \ &\left. p\ \middle|\ \sum_{a=1}^{\frac{p-1}{2}} a^{-2},\right.\end{align}$$ pretože $p$ a $p^2-p-1$ sú nesúdeliteľné a $a^{p^2-p}\equiv (a^{p-1})^p \equiv 1^p \equiv 1 \pmod{p}$.

Členy v súčte sú všetky rôzne modulo $p$, pretože ak by sa dva rovnali, tak $$\begin{align} a^{-2} &\equiv b^{-2} \pmod{p},\ b^2 &\equiv a^2 \pmod{p},\ 0 &\equiv a^2-b^2=(a-b)(a+b) \pmod{p}.\end{align}$$ z čoho na intervale od $1$ do $\frac{p-1}{2}$ nutne platí $a=b$.

Uvedomme si, že v súčte je každý kvadratický zvyšok¹ práve raz. Navyše vieme, že $a^2 \equiv (-a)^2$, takže súčet všetkých kvadratických zvyškov, každého práve raz, dostaneme aj sčítaním $a^2$ od $1$ do $\frac{p-1}{2}$. Náš súčet mínus druhých mocnín je teda v skutočnosti súčet druhých mocnín od $1$ do $n=\frac{p-1}{2}$. O ňom vieme, že je to $\frac{1}{6}n(n+1)(2n+1)$. Keďže $p \geq 5$, šestina nás nezaujíma (je nesúdeliteľná s $p$) a $(2n+1)=p$ je deliteľné $p$, čím je dôkaz hotový.

Na záver: krokov je síce veľa, ale úpravy sú ekvivalentné v zmysle, že všetky výrazy cestou musia byť deliteľné tým, čím chceme, ak má dokazované tvrdenie platiť. Preto ak sa znižuje mocnina $p$ a zjednodušujú sa nám výrazy, nevieme sa dostať úplne do slepej uličky (možno sa dostaneme k niečomu, čo je ťažšie dokázať, ale aspoň máme stále platné tvrdenie, tak by sme ho mohli byť schopní dokázať).