4. Ktorého Moreplavca Splatiť? vzorové riešenie

Kľúčovým krokom k riešeniu tejto úlohy bolo uvedomiť si, ako nejak viac matematicky uchopiť posledných \(5\) cifier nejakého čísla. Posledných \(5\) cifier čísla predstavuje jeho zvyšok po delení \(10^5\). Je to vidno napríklad vtedy, keď si vezmeme číslo \(12345678 = 123 \cdot 10^5 + 45678\). Zvyšok po delení \(10^5\) je naozaj jeho \(5\) posledných cifier.

My teda hľadáme najmenšie číslo \(n\), pre ktoré platí, že \(n^2\) má zvyšok \(1\) po delení \(10^5\) (vedúce nuly teraz už písať nemusíme). Rozdiel čísla a jeho zvyšku (aj všeobecne rozdiel dvoch čísel s rovnakým zvyškom) je násobok čísla, ktorým delíme, teda v našom prípade \(n^2-1\) musí byť násobok \(10^5\). Toto vieme zapísať aj v tvare \(10^5 \mid n^2-1\). Tento zápis znamená, že \(10^5\) delí \(n^2-1\).

S prvočíslami a ich mocninami sa pracuje o niečo lepšie, ako so zloženými číslami (ako \(10^5\)), pretože o nich platia pekné vzťahy. Napríklad ak prvočíslo delí súčin \(a \cdot b\), musí deliť aspoň jedného činiteľa (\(a\) alebo \(b\)), pretože sa nevie „rozdeliť“ do oboch.

Ak je číslo deliteľné \(10^5 = 5^5 \cdot 2^5\), tak je nutne deliteľné aj samotným \(5^5\). Výraz \(n^2-1\) si vieme rozpísať na súčin podľa známeho vzorčeka ako \((n+1)(n-1)\). Teda musí platiť \(5^5 \mid (n-1)(n+1)\). Číslo \(5\) nemôže deliť naraz obe zátvorky, keďže sa líšia o \(2\). Musí teda platiť \(5^5 \mid n-1\) alebo \(5^5 \mid n+1\). To nám už dáva celkom silnú podmienku pre \(n\). Číslo \(1\) nevyhovuje – druhá mocnina nemá dosť cifier, takže ďalšími kandidátmi budú \(5^5-1\), \(5^5+1\), \(2 \cdot 5^5-1\), \(2 \cdot 5^5+1\), … Mohli by sme ich skúšať zaradom a onedlho by sme sa dostali k výsledku. Skúsme to však o niečo rýchlejšie.

Môžeme si všimnúť, že hľadané \(n\) je nepárne, pretože aj jeho druhá mocnina musí byť nepárna. Stačí teda skúmať tie čísla, v ktorých sa \(5^5\) násobí niečím párnym; po odpočítaní alebo pripočítaní jednotky dostaneme nepárne \(n\). Keď si teraz vypíšeme niekoľko málo možností

\[\begin{aligned} 2 \cdot 5^5-1 =6249 &\longrightarrow 6249^2 = 39050001,\\ 2 \cdot 5^5+1 =6251 &\longrightarrow 6251^2 = 39075001,\\ 4 \cdot 5^5-1 =12499 &\longrightarrow 12499^2 = 156225001,\\ 4 \cdot 5^5+1 =12501 &\longrightarrow 12501^2 = 156275001,\\ 6 \cdot 5^5-1 =18749 &\longrightarrow 18749^2 = 351525001,\\ 6 \cdot 5^5+1 =18751 &\longrightarrow 18751^2 = 351600001,\end{aligned}\]

rýchlo nájdeme hľadané najmenšie \(n = 6 \cdot 5^5+1 = 18751\), ktoré je riešením našej úlohy.