Zadanie
Jožko sa odpojil od vedúcich, ktorých tlačila Kaja po kružnici a rozhodol sa ich vystrašiť na začiatku ich najbližšieho okruhu. Má však veľmi prísne pravidlá pre strašenie vedúcich.
Jožko je ochotný vystrašiť vedúcich v okruhu s číslom \(k\in\mathbb{N}\) len vtedy, ak pre každé nepárne prirodzené číslo \(n > 100\) platí \(k \mid 20^n + 22^n\). Nájdite všetky také prirodzené čísla \(k\).
Prvé pozorovanie, ktoré môžeme spraviť, je, že sčítame dve párne čísla, takže výsledok musí byť párny. Vieme zájsť dokonca ďalej. Keďže \(n \geq 101\), oba sčítance sú násobkami \(2^{101}\), takže aj ich súčet bude. Môžeme si tiež všimnúť, že vyššie mocniny dvoch už nevyhovujú. Pre \(n = 101\) totiž dostaneme \(2^{101} \cdot (10^{101} + 11^{101})\), pričom číslo v zátvorke bude nepárne. O dvojkách v rozklade \(20^n + 22^n\) už vieme, čo potrebujeme, je teda na čase pozrieť sa aj na iné prvočísla.
Lenže ako na to? Zadanie poskytuje vcelku zaujímavú nápovedu v tom, že \(2 \nmid n\). Pre nepárne \(n\) vieme totiž súčet \(a^n + b^n\) vždy rozložiť ako \[a^n + b^n = (a + b) \cdot (a^{n-1} - a^{n-2}b + \cdots - ab^{n-2} + b^{n-1}).\] V našom prípade \(a = 20,\, b = 22\). Teda, bez ohľadu na veľkosť \(n\), vieme daný výraz vydeliť \(42\), čím v prvočíselnom rozklade nájdeme aj \(3\) a \(7\). Otázkou zostáva, čím môže byť deliteľná tá druhá zátvorka.
Označme \(s_n\) hodnotu v zátvorke pre nepárne \(n\), t. j. \[s_n = 20^{n-1} - 20^{n-2} \cdot 22 + 20^{n-3} \cdot 22^2 - \cdots - 20 \cdot 22^{n-2} + 22^{n-1}.\] Skúmať deliteľov takéhoto výrazu nie je úplne praktické. Nám však stačia delitelia, ktorí sú spoloční pre každé nepárne \(n > 100\). Využijeme teda, ako ľahko vieme pomocou nejakého \(s_n\) dostať iný výraz tohoto typu. Prvé, čo sa nám núka, je fakt, že \[s_{n+2} = 20^2 \cdot s_n - 20 \cdot 22^n + 22^{n+1}.\] Ak teda niečo delí \(s_n\) aj \(s_{n+2}\), nutne to delí aj \(- 20 \cdot 22^n + 22^{n+1} = 2 \cdot 22^n\). Keď si \(s_{n+2}\) vyjadríme ako \(20^{n+1} - 20^n \cdot 22 + 22^2 \cdot s_n\), rovnakou úvahou zistíme, že hľadáme deliteľa \(-2 \cdot 20^n\). Môžeme si všimnúť, že tieto dve čísla majú v prvočíselnom rozklade spoločnú len dvojku (\(11\) nedelí \(20^n\), \(5\) nedelí \(22^n\)). Iné prvočíslo teda nemôže deliť všetky \(s_n\) a nového deliteľa nenájdeme.
Ostáva nám už len určiť všetky \(k\). Vieme, že všetky prípustné hodnoty \(20^n + 22^n\) sú deliteľné \(2^{101},\, 3,\, 7\) (a žiadnym iným prvočíslom, ani väčšou mocninou \(2, 3, 7\)). Vhodné \(k\) teda budú deliteľmi \(2^{101} \cdot 3 \cdot 7\), teda čísla tvaru \(2^a \cdot 3^b \cdot 7^c\), kde \(a \in \{0,\, 1,\, \ldots,\, 101\},\, b \in \{0,\, 1\},\, c \in \{0,\, 1\}\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.