Zadanie
Keď Jožo v noci nevie zaspať, počíta svoje obľúbené prvočísla. Prvočíslo \(p\) sa nazýva Jožovo obľúbené, ak preň existuje prirodzené číslo \(k\), pre ktoré platí, že \(p\) delí \(k^{3}+6\). Ukážte, že nech by sa Jožo snažil ako chcel, všetky svoje obľúbené prvočísla by sa mu spočítať nepodarilo. Inak povedané, dokážte, že Jožovych obľúbených prvočísel je nekonečne veľa.
Zamyslime sa, akým smerom môže dôkaz úlohy postupovať. Môžeme sa pokúsiť nájsť spôsob, ako systematicky nachádzať obľúbené prvočísla a ukázať, že budeme dostávať nové a nové prvočísla. Ďalšia z možností, čo prichádza do úvahy je postupovať sporom – predpokladať, že obľúbených prvočísel je konečne veľa (teda si ich môžeme vypísať do zoznamu) a ukázať, že existuje neoznačené obľúbené prvočíslo.
Poďme dokázať úlohu sporom. Nech sú všetky obľúbené prvočísla \(p_1,\ p_2,\ \dots,\ p_n\). Aby sme dostali spor, chceme nájsť \(k\) také, že výraz \(k^3+6\) má (prvočíselného) deliteľa rôzneho od \(p_1,\ p_2,\ \dots,\ p_n\).
Ako vieme zabezpečiť, aby \(p_i\) nedelilo \(k^3+6\)? Zvolíme \(k\) také, aby bolo deliteľné \(p_i\). Ak \(p_i\) delí \(k^3\) a nedelí \(6\), tak \(p_i\) nedelí \(k^3+6\) (rozmyslite si).
Teda, ak zvolíme \(k=p_1p_2\dots p_n\) (vynechajme odtiaľ \(p_i=2,3\)), tak \(k^3+6\) nebude deliteľné žiadnym prvočíslom \(p_i\) rôznym od \(2\) a \(3\). Ostáva nám doriešiť deliteľnosť dvomi a tromi. Môžeme si všimnúť, že keďže \(2\), \(3\) delia \(6\) a nedelia \(k\), tak nedelia ani \(k^3+6\). Tým pádom \(k^3+6\) je deliteľné inými prvočíslami ako \(p_1,\ p_2,\ \dots,\ p_n\), čo je spor. Ukázali sme, že Jožových obľúbených prvočísel je nekonečne veľa.
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ť.