10. Krtkova Maľovacia Seansa vzorové riešenie

Dobrým prístupom, ako pochopiť zadanie, je dosadiť nejaké čísla. Najmenšie \(n\), pre ktoré môžeme zadanie riešiť, je \(n=2\). Potom úlohou je nájsť také \(a\), aby \(a^1+2^1 \mid a^2-2^2\). Keďže \(a^2-2^2 = (a-2)(a+2)\), tak deliteľnosť platí pre ľubovoľné \(a>2\). Prirodzené číslo \(n=2\) je teda riešením, pre ktoré existuje \(n\)-rozložiteľné číslo \(a\). Mať jediného deliteľa \(1\leq d < n\), \(d=1\) sa z pohľadu skúmania úlohy oplatí, pretože treba overovať iba malé množstvo deliteľností. Také čísla \(n\) sú prvočísla.

Nech \(n=p \in \mathbb{P}\), potom je úlohou nájsť také \(a\), pre ktoré \(a+2 \mid a^p-2^p\). Keďže netreba nájsť všetky také \(a\), tak po chvíľke skúšania sa dá ľahko nájsť, že pre \(a=6\) platí \(8\mid 6^p-2^p = 2^p(3^p-1)\) – lebo pre ľubovoľné prvočíslo \(p\geq 2\) platí, že pravá strana je deliteľná aspoň \(2^{p+1}\) (z toho, že \(3^p-1\) je párne).

Pre priaznivcov všeobecnejšieho prístupu, nech \(p\) je nepárne prvočíslo. Potom \[\begin{align} a^p-2^p = (a^p+2^p)-2\cdot 2^p =(a+2)(a^{p-1} - 2\cdot a^{p-2} + 4 \cdot a^{p-3} - \dots + 2^{p-1}) - 2^{p+1}. \tag{1}\end{align}\] Preto \(a+2 \mid a^p-2^p\) práve vtedy, keď \(a+2 \mid 2^{p+1}\), a teda \(a = 2^k-2\), pre vhodné \(2<k \leq p+1\). Ako príklad pre prvočíslo \(5\) sú vyhovujúce riešenia \(a\) iba \(a\in\{62,30,14,6\}\).

Prvočísla sú vyriešené, pozrime sa na zložené čísla. Nech teda \(n=x\cdot y\), kde \(y>1\) je nepárne číslo. Potom podobnými úpravami ako v (1) dostaneme \[\begin{align} a^n-2^n = a^{x\cdot y} -2^{x\cdot y} = (a^x+2^x)(a^{x(y-1)} - 2^x\cdot a^{x(y-2)} + 4^x \cdot a^{x(y-3)} - \dots + 2^{x(y-1)}) - 2^{n+1}, \tag{2}\end{align}\] z čoho je vidieť, že \(a^x+2^x \mid a^n-2^n\) práve vtedy, keď \(a^x+2^x \mid 2^{n+1}\), teda keď \(a^x+2^x\) je mocnina dvojky. Výraz \(a^x+2^x\) má byť mocninou dvojky väčšou ako \(1\), takže vieme, že \(2\mid a\). Nech teda \(a=2\cdot b\). Potom \(a^x+2^x= 2^x(b^x+1)\), a preto výraz \(b^x+1\) má byť tiež mocninou dvojky – nech je to \(2^k\), z čoho \(2^k - b^x = 1\).

Toto je známy problém Catalan’s conjecture (Catalanova domnienka alebo Mihailescova veta)¹, ktorý má vo svojej všeobecnej forme \(x^a-y^b=1\) pre prirodzené \(a,b>1\), \(x,y>0\) jediné riešenie \(x=3,a=2,y=2,b=3\). Toto riešenie však nášmu problému nevyhovuje. Preto jediným riešením rovnice \(2^k - b^x = 1\), kde \(x>1\), je \(b=1\) a \(k=1\). Z toho je ale jasné, že \(a=2\), čo je spor so zadaním. Preto \(n\) nemá nepárneho deliteľa.

Zostávajúca možnosť je, že \(n\) je mocnina dvojky.

Dobrým pozorovaním je, že \(a^{2k}-2^{2k}=(a^k+2^k)(a^k-2^k)\). Zovšeobecnením tejto úvahy je \[\begin{align} a^{2^k}-2^{2^k}&=\left(a^{2^{k-1}}+2^{2^{k-1}}\right)\left(a^{2^{k-1}}-2^{2^{k-1}}\right) = \left(a^{2^{k-1}}+2^{2^{k-1}}\right)\left(a^{2^{k-2}}+2^{2^{k-2}}\right)\left(a^{2^{k-2}}-2^{2^{k-2}}\right) = \\ &=\left(a^{2^{k-1}}+2^{2^{k-1}}\right)\cdot \left(a^{2^{k-2}}+2^{2^{k-2}}\right) \cdot \dots \cdot \left(a^{2 }+2^{2}\right)\cdot\left(a+2\right)\cdot\left(a-2\right).\end{align}\] Každý deliteľ \(2^k\) má svoj príslušný faktor vo výraze. Preto existuje \(n\)-rozložiteľné číslo \(a>2\), a teda \(n\) je riešením.

Preto jediné riešenia sú, keď \(n\) je prvočíslo alebo mocnina dvojky.