8. Konkurz Menejcenného Štvorca vzorové riešenie

Pozrime sa najprv, či tvrdenie platí, keby sme ho sformulovali naopak… t. j. nech \(a=s^2\) pre nejaké \(s\) prirodzené. Potom \(n^2s^2-1=(ns-1)(ns+1)\), kde \(ns+1>1\) spĺňa nami požadované vlastnosti. Vďaka tomuto zároveň máme lacno získaných nekonečno príkladov na čísla spĺňajúce zadanie.

Našou úlohou je však dokázať opačnú implikáciu. Nech teda pre všetky \(n>1\) existuje taký deliteľ \(d>1\) výrazu \(n^2a-1\), ktorý dáva zvyšok \(1\) po delení \(n\). To ale znamená, že existuje také \(k \in \mathbb{N}\), že \(d=nk+1 \mid n^2a-1\). Z tejto deliteľnosti zároveň vidíme, že \(k<na\).

Jednou zo základných vlastností deliteľnosti je, že ak pre celé čísla platí \(x\mid y\), tak aj \(x\mid y+zx\), kde \(z\) je ľubovoľné celé číslo. Toto viackrát aplikujeme na našu deliteľnosť: \[nk+1 \mid n^2a-1 \Rightarrow nk+1 \mid n^2a-1+nk+1=n(na+k) \Rightarrow nk+1\mid na+k\] (lebo čísla \(n\) a \(nk+1\) sú nesúdeliteľné).

Potom ďalej \[nk+1\mid na+k \Rightarrow nk+1\mid na+k-k(nk+1)=n(a-k^2) \Rightarrow nk+1\mid k^2-a.\] Toto má platiť pre všetky \(n \in \mathbb{N}\). Zvoľme \(n\) „rádovo väčšie“ ako \(a\) (to znamená niečo v zmysle \(n>100a+1000\), ale pre účely tejto úlohy bude stačiť slovný popis, rozmyslite si, ako by ste potrebné odhady dokázali presne).

Na pravej strane máme výraz, ktorý kvadraticky závisí od \(k\), kým na ľavej máme lineárnu závislosť. Aby platila deliteľnosť, musí platiť: \(a-k^2=0\) alebo \(|nk+1| \le | k^2-a|\). Predpokladajme, že tá prvá možnosť neplatí. Pre \(k=1\) je hodnota výrazu \(|nk+1|\) rovná \(n+1\), kým hodnota \(| k^2-a|\) je rovná \(a-1\). Hodnota \(| k^2-a|\) bude s rastúcim \(k\) klesať až do chvíle, kým \(k^2>a\), potom začne rásť. Hodnota \(nk+1\) rastie s rastúcim \(k\) stále. Po dosadení \(k=n\) dostávame na ľavej strane \(n^2+1\) a na pravej strane \(n^2-a\), čo evidentne ešte stále nespĺňa nami požadovanú nerovnosť. Preto sme dostali aj dolné aj horné ohraničenie pre \(k\), konkrétne: \(n<k<na\), a ako uvidíme, bude sa nám hodiť.

Deliteľnosť \(nk+1\mid k^2-a\) musí byť realizovaná nejakým konkrétnym celým číslom. Keďže \(n\) aj \(k\) sú rádovo väčšie ako \(a\), naskytá sa nám dosť úzke ohraničenie pre celé číslo \(z\), pre ktoré \(z(nk+1)=k^2-a\). Na prvý pohľad vidíme \(z \cong k/n\). Vyskúšajme teda vynásobiť \(nk+1\) číslom \(k/n\) (aby sme dostali nejaké ohraničenie pre z). Dostaneme \(k^2+k/n>k^2-a\). Nevyšlo. Skúsme \((nk+1)(k/n-1)=k^2-nk+k/n-1\). Lenže \(k/n\) neprevyšuje \(a\), kým \(nk\) je mimoriadne veľké: \(k^2-nk+k/n-1<k^2-a\).

Máme teda interval o veľkosti jedna, vnútri ktorého sa musí nachádzať celé číslo \(z\). Lenže potom vieme \(z\) jednoznačne určiť. Nech \(k \equiv c \pmod n\). Potom \(z=(k-c)/n\). Teda dostávame \((nk+1)(k/n-c/n)=k^2+k/n-ck-c/n= k^2+(k-c)/n-ck\). Toto má byť presne rovné \(k^2-a\). Teda \(ck-(k-c)/n=a\). Vieme, že \(c \ge 1\), lebo ak by sa rovnalo nule, dostávame jasnú nerovnosť. Lenže potom \(ck\) je mimoriadne veľké, kým \((k-c)/n\) je zhora ohraničené \(a\). Takýmto spôsobom teda nemôže byť dosiahnutá rovnosť.

Možno sme už aj zabudli, čo sme týmto dosiahli. Dosiahli sme spor, ktorý sme si na začiatku piateho odseku vytvorili… predpokladali sme, že \(k^2-a \neq 0\). Nuž teda \(a=k^2\) pre nejaké prirodzené \(k\), čo o \(a\) prezrádza, že je štvorcom.