Zadanie
Veronika v pivnici tiež našla starú ošúchanú knižku. Mimo iného v nej bola legenda o bájnom uhorskom kráľovstve a táto úloha:
Dané sú prvočísla \(p\) a \(q\) také, že \(q=2p+1\). Dokážte, že existuje prirodzené číslo deliteľné \(q\) také, že jeho ciferný súčet v desiatkovej sústave je najviac \(3\).
Inšpirované skutočnou udalosťou a tiež riešením Lukáša Gáboríka.
Najprv ošetrime jednoduchý prípad, a to že \(q=5\). Za tohto predpokladu je riešiaci násobok tohto čísla napríklad \(10\). Vidíme, že \(q\) nemôže byť rovné dvom ani trom, lebo by to nesedelo s tým, že \(q=2p+1\), kde \(p\) je prvočíslo.
Teraz serióznejšia matika. Vhodní kandidáti na čísla s ciferným súčtom menším ako 4 sú mocniny desiatky, prípadne súčty niekoľkých mocnín desiatky. Preto nie je zlé sa hrať práve so zvyškami mocniny desiatky po delení \(q\). Aplikujme Malú Fermatovu vetu na desiatku a upravíme: \[\begin{aligned} 10^{q-1} \equiv 10^{2p} \equiv 1 \pmod q,\\ 10^{2p}-1 \equiv 0 \pmod q,\\ (10^{p}-1)(10^{p}+1) \equiv 0 \pmod q.\end{aligned}\] Keďže \(q\) ako prvočíslo delí súčin zátvoriek v poslednej kongruencii, musí deliť aspoň jednu z nich (a môžeme si všimnúť, že dokonca práve jednu z nich). Ak \(q \mid 10^p+1\), tak sme vyhrali, lebo použijeme toto číslo ako príklad spomínaného čísla.
Uvažujme teda naopak, že \(q \mid 10^p-1\). Z toho ale vyplýva, že rád1 prvku \(10\) modulo \(q\) delí prvočíslo \(p\) a teda je buď rovný 1, alebo \(p\). Ak je rovný 1, potom musí platiť, že \(10^1 \equiv 1 \pmod q\), a teda \(q=3\), čo je spor. Preto rád \(10\) modulo \(q\) je presne \(p\).
Pozrime sa, aké zvyšky môže nadobúdať \(10^x\) modulo \(q\), pre \(1 \le x \le p\). Zjavne prípad \(10^x \equiv 0 \pmod q\) nemôže nastať, pre \(q>5\). Ak existuje \(x\), že \(10^x \equiv 2p \pmod q\), potom \(10^x+1\) je príkladom násobku \(q\) s požadovaným ciferným súčtom. Ak existuje \(x\), že \(10^x \equiv p \pmod q\), tak \(2 \cdot 10^x+1\) je oným príkladom (stále spĺňa podmienku o cifernom súčte).
V prípade, že ani jedna z predošlých možností nenastáva, musia byť zvyšky mocnín \(10^x\) modulo \(q\), v množine \(\{1,2,\dots,p-1,p+1,\dots,2p-1\}\). Rozdeliac túto množinu na \(p-1\) dvojíc s rovnakým zvyškom po delení \(p\) a využijúc fakt, že zvyšky \(10^x\) modulo \(q\), pre \(x \in \{1,2,\dots,p\}\) musia byť na základe vlastností rádu rôzne čísla, dostávame z Dirichletovho princípu, že aspoň jedna dvojica bude dosahovaná na oboch svojich prvkoch. Nech prislúchajúce mocniny \(10\), pre ktoré sa nadobúdajú dané zvyšky sú \(k,l\). Potom zjavne \(q \mid 10^k+10^l+1\) a zároveň toto číslo zrejme spĺňa podmienky zo zadania.
v prípade, že ste ešte nepočuli o ráde, silno odporúčam pozrieť si prvý článok tohto pekného zborníku: http://iksko.org/files/sbornik5.pdf↩︎
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ť.