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.