Opravovatelia

M&M; [email protected]

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.