10. Koeficienty Maťovej Schovávačky vzorové riešenie

Polynóm \(P\) rádu \(n\) je funkcia tvaru \[P(x) = a_{n}x^n + a_{n-1}x^{n-1} + \dots + a_1 x + a_0, \] kde \(a_0,\, a_1,\, \dots,\, a_{n-1},\, a_{n}\) sú jeho parametre. Polynóm je monický, ak jeho vedúci člen je \(a_n = 1\). Každý monický polynóm je určený svojím rádom \(n\) a k tomu \(n\) koeficientami \(a_0,\, \dots,\, a_{n-1}\). V tomto príklade máme nájsť všetky monické polynómy, ktoré spĺňajú \(p \mid 2(P(p)!) + 1\) pre všetky dosť veľké prvočísla \(p\).

Ako prvé si všimnime, že monických polynómov je veľa. Ale naozaj, naozaj veľa. Bolo by teda super obmedziť túto skupinu polynómov, aby sme ich nemuseli uvažovať všetky naraz. Pri príkladoch s polynómami je častý prvý krok rozobrať prípady podľa rádu polynómu, do čoho sa hneď pustíme.

Uvažujme na začiatok polynómy stupňa 0. Takýchto polynómov je dokopy… jeden, keďže vedúci (a zároveň jediný) člen musí byť rovný jednej. Konkrétne je to \(P(x) \equiv 1\). Pre každé prvočíslo \(p\) máme \(2(P(p)!) + 1 = 3,\) čo nie je deliteľné žiadnym prvočíslom okrem 3. Monické polynómy rádu 0 teda nemusíme uvažovať.

Ako druhý prípad uvažujme monické polynómy rádu aspoň dva. V tomto prípade nám bude nápomocné pozorovanie, že ak existuje prvočíslo \(p\) pre ktoré \(P(p) \geq p\), tak potom \(p \nmid 2(P(p)!) + 1\), keďže \(p \mid P(p)!\). Z predchádzajúceho vyplýva, že ak máme polynóm \(P\) a prvočíslo \(p\) pre ktoré \(P(p) \geq p\), tak tento polynóm nespĺňa požiadavku zo zadania. V ďalšom ukážeme, že pre všetky monické polynómy rádu aspoň dva vieme takéto prvočíslo \(p\) nájsť.

Uvažujme polynóm \(Q(x) = P(x) - x\). Polynóm \(Q\) je tiež monický aspoň stupňa dva. Chceme ukázať, že existuje prvočíslo \(p\), pre ktoré \(Q(p) \geq 0\). Jedna z vlastností monických polynómov je, že pre „dosť veľké“ \(x\) majú iba kladné hodnoty. Ak teda zvolíme „dosť veľké“ prvočíslo \(p\), nám bude platiť \(Q(p) \geq 0\), čo sme chceli dokázať a teda monické polynómy rádu aspoň dva uvažovať tiež nemusíme.

Pre úplnosť si tvrdenie o „dosť veľkých“ číslach dokážeme. Nech \(x > 1\) a nech \(M\) je najväčšie z absolútnych hodnôt parametrov \(|a_0|, \dots, |a_{n-1}|\). Potom vieme spraviť nasledovné odhady

kde v poslednom odhade sme použili, že \(x^i > 1\) pre \(x > 1\) a \(i \geq 1\). Ak teda zvolíme \(x > nM\), tak máme \[Q(x) \quad = \quad x^n + a_{n-1}x^{n-1} + \dots + a_1 x + a_0 \quad > \quad x^n - Mnx^{n-1} \quad = \quad x^{n-1}(x - Mn) \quad > \quad 0, \] čo sme presne chceli dokázať.

Na záver nám ostala posledná kategória monických polynómov a tie majú rád 1. Vo všeobecnosti môžeme takýto polynóm zapísať ako \(P(x) = x + k\), kde \(k\) je celé číslo. Všimnime si, že ak \(k \geq 0\), tak bude existovať prvočíslo \(p\) také, že \(P(p) \geq p\), čo nám z vyššie uvedených dôvodov opäť nevyhovuje zadaniu. Ostávajú nám teda polynómy so záporným \(k\), ktoré si pre jednoduchšie chápanie preznačíme na \(P(x) = x - k\), pre \(k > 0\).

Vo zvyšku postupu sa ponoríme do tajomného sveta kongruencií.¹ V nasledujúcom využijeme tri vlastnosti kongruencií, konkrétne:

• \(a + b \equiv b \pmod{a}\), pre všetky \(a \in \mathbb{N}\) a \(b \in \mathbb{Z}\),
• \(a \equiv b \pmod{d} \quad \Rightarrow \quad ac \equiv bc \pmod{d}\), pre všetky \(a,b,c \in \mathbb{Z}\) a \(d \in \mathbb{N}\),
• (Wilsonova veta) \((p-1)! \equiv -1 \pmod{p}\), pre všetky prvočísla \(p\).

Prvé dve vlastnosti sú štandardné. Wilsonova veta je menej známa, ale zároveň kľúčová pre túto úlohu.

Podmienku pre hľadaný polynóm zo zadania môžme pomocou kongruencií zapísať ako \(2(P(p)!) \equiv -1 \pmod{p}\), pre všetky dosť veľké prvočísla \(p\). Dosadením uvažovaného tvaru polynómu \(P\) dostávame podmienku \(2((p-k)!) \equiv -1 \pmod{p}\). Na ľavej strane máme faktoriál, ktorý doplníme do \((p-1)!\) tým, že (využitím 2. vlastnosti vyššie) prenásobíme obe strany postupne \((p-1),\, (p-2),\, \dots,\, (p-k+1)\). Tým dostávame podmienku \[2((p-1)!) \equiv (p-1)(p-2)\dots(p-k+1) \pmod{p}. \] Využitím 1. vlastnosti spomenutej vyššie máme \[(p-1)(p-2) \dots (p-k+1) \equiv (-1)(-2) \dots (-k+1) \equiv (-1)^{k-1}(k-1)! \pmod{p}, \] čo nám upraví pravú stranu podmienky na \[ 2((p-1)!) \equiv (-1)^{k-1}(k-1)! \pmod{p}. \] Použitím Wilsonovej vety na ľavej strane a následne pričítaním čísla 2 na obe strany (zase využitím 1. vlastnosti) dostávame \[0 \equiv (-1)^{k-1}(k-1)! + 2 \pmod{p}. \] Naša posledná kongruencia hovorí, že výraz nezávislý od prvočísla \(p\) je deliteľný všetkými dosť veľkými prvočíslami. To môže nastať, iba ak je daný výraz rovný nule. Teraz už ľahko dopočítame, že jediné \(k\) spĺňajúce rovnosť \((-1)^{k-1} (k-1)! = 0\) je \(k=3.\) Náš jediný kandidát na riešenie príkladu je teda polynóm \(P(x) = x - 3\). Ľahko overíme, že všetky vyššie uvedené kroky vieme nasledovať aj opačným smerom a \(P(x) = x-3\) teda skutočne vyhovuje zadaniu.