8. Konvolúcia Množstva Šošoviek vzorové riešenie

Zoberme si postupnosť, ktorej členy sú počty šošoviek postupne v každej minúte. Keď si vypíšeme prvých pár členov, zistíme, že zo štvorcov sú tam práve štvorce prvočísel. Chceli by sme dokázať, že to naozaj platí pre všetky prvočísla – teda že sú tam práve ich štvorce a žiadne iné.

Pozrime sa teda na to, ako sa postupnosť správa od bodu, keď nadobudne hodnotu \(p^2\) pre nejaké prvočíslo \(p\). Najväčší prvočíselný deliteľ \(p^2\) je \(p\), takže ďalší člen bude \(p(p+1)\). Takto budeme pripočítavať \(p\) až dovtedy, kým \(p(p+k)\) nebude mať väčšieho prvočíselného deliteľa ako \(p\). Prvý takýto deliteľ môže byť až najbližšie prvočíslo väčšie ako \(p\), označme ho \(q\). Postupným pripočítavaním \(p\) sa potom dostaneme až k \(pq\). Teraz je najväčší prvočíselný deliteľ \(q\), postupnosť teda bude pokračovať členmi \((p+k)q\). Kým bude \(p+k<q\), najväčší prvočíselný deliteľ bude stále \(q\) a teda sa takto dostaneme až po \(q^2\).

Tým sme dokázali, že takto dosiahneme postupne všetky prvočísla. Ostáva ešte ukázať, že žiadne iné štvorce nedosiahneme. Ak by sme taký štvorec mali dosiahnuť, musel by byť tvaru \(p(p+k)\) alebo \((p+k)q\), kde \(p+k<q\). Štvorec tvaru \((p+k)q\) nedosiahneme, lebo \(p+k\) nemôže byť deliteľné \(q\), keďže je menšie. Štvorec tvaru \(p(p+k)\) by musel byť deliteľný \(p\), teda aj \(p^2\), a najbližší väčší taký štvorec od \(p^2\) je \(4p^2\). Muselo by sa teda stať, že \(q>4p\), teda by nemohli byť žiadne prvočísla medzi \(p\) a \(4p\), čo znie celkom podozrivo, teda že by sa to nemalo stať. Aby sme dokázali, že sa to naozaj nemôže stať, použijeme tvrdenie známe ako Bertrandov postulát, ktorý hovorí, že pre každé prirodzené \(n\) existuje prvočíslo medzi \(n\) a \(2n\). K najbližšiemu inému štvorcu, ktorý by vyhovoval, sa teda nedostaneme, preto sú to naozaj len štvorce prvočísel.