Opravovatelia

Alicka [email protected]

Dominik [email protected]

Poznamenajme, že počas celého riešenia narábame so zlomkami ako s modulárnymi inverzami a naopak. Označme $H_n=\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{n}$ pre $n\in\mathbb{N}$. Ľahko spočítame, že $H_1=\frac{1}{1}\equiv 1 \pmod{5}$, $H_2=\frac{3}{2}\equiv 4 \pmod{5}$, $H_3=\frac{11}{6}\equiv 1 \pmod{5}$, $H_4=\frac{25}{12}\equiv 0 \pmod{5}$. Vidíme tak, že $n\in{1,2,3,4}$ vyhovujú zadaniu.

Tvrdenie 1. Pre celé $n\geq5$ platí $5\nmid q_n$ práve vtedy, keď $\left.5~\middle|~ p_{\left\lfloor n/5\right\rfloor}\right.$.

Dôkaz. Nech $k\in\mathbb{N}$ je také, že $5^k\leq n < 5^{k+1}$. Ďalej označme $L=\operatorname{nsn}(1,2,\cdots,n)$. Potom platí $v_5(L)=k$. Máme tak $$H_n=\frac{\frac{L}{1}+\frac{L}{2}+\cdots+\frac{L}{n}}{L}.$$ Všimnime si, že $5\nmid q_n$ práve vtedy, keď $v_5(H_n)\geq 0$, teda práve vtedy, keď čitateľ má v svojom rozklade aspoň toľko pätiek ako menovateľ, teda $\left.5^{k}~\middle|~\frac{L}{1}+\frac{L}{2}+\cdots+\frac{L}{n}\right.$. Nakoľko $\left.5^k~\middle|~\frac{L}{i}\right.$ pre $5\nmid i$, je to to isté ako $$\left.5^{k}~\middle|~\frac{L}{5}+\frac{L}{10}+\cdots+\frac{L}{5\left\lfloor n/5\right\rfloor}\right.,$$ čo je ekvivalentné s $\left.5^{k+1}~\middle|~\frac{L}{1} + \frac{L}{2} + \cdots + \frac{L}{\left\lfloor n/5\right\rfloor}\right.$. Toto je však to isté, ako keď povieme $\left.5~\middle|~p_{\left\lfloor n/5\right\rfloor}\right.$, keďže $$H_{\left\lfloor n/5\right\rfloor}=\frac{\frac{L}{1}+\frac{L}{2}+\cdots+\frac{L}{\left\lfloor n/5\right\rfloor}}{L},$$ pričom stále $v_5(L)=k$. $\square$

Tvrdenie 2. Pre $a\in\mathbb{N}_0$ platí $$\frac{1}{5a+1}+\frac{1}{5a+2}+\frac{1}{5a+3}+\frac{1}{5a+4} \equiv 0 \pmod{25}.$$

Dôkaz. $$\left(\frac{1}{5a+1}+\frac{1}{5a+4}\right)+\left(\frac{1}{5a+2}+\frac{1}{5a+3}\right) = \frac{10a+5}{(5a+1)(5a+4)}+\frac{10a+5}{(5a+2)(5a+3)}=$$ $$= (10a+5)\left(\frac{1}{25a^2+25a+4} + \frac{1}{25a^2+25a+6}\right) \equiv (10a+5)\left(\frac{1}{4}+\frac{1}{6}\right)= (10a+5)\cdot \frac{5}{12} \equiv 0 \pmod{25}. \ \square$$

Tvrdenie 3. Všetky $n\in\mathbb{N}$ také, že $5| p_n$, sú $n\in{4,20,24}$.

Dôkaz. Všimnime si, že ak $5| p_n$, tak potom $5 \nmid q_n$, a teda $\left.5~\middle|~ p_{\left\lfloor n/5\right\rfloor}\right.$. Preto $n$ môžeme iteratívne deliť piatimi a aplikovať dolnú celú časť, až kým nedostaneme jedno z čísel $n\in{1,2,3,4}$ (ak by sme totiž dostali číslo väčšie ako $4$, môžeme ho opäť vydeliť $5$ a aplikovať dolnú celú časť). Všimnime si zároveň, že jediné z týchto štyroch čísel, pre ktoré platí $5| p_n$, je $n=4$, ako vieme z úvodného odstavca.

Generujme teda hľadané $n$ „odzadu“. Začíname s $n=4$. Rovnica $\left\lfloor \frac{n}{5}\right\rfloor=4$ má riešenia $n\in{20,21,22,23,24}$. Všimnime si, že s využitím Tvrdenia 2 $$H_{20}= \frac{1}{1}+\cdots + \frac{1}{20}\equiv \frac{1}{5}+\frac{1}{10}+\frac{1}{15}+\frac{1}{20} = \frac{1}{5}\cdot H_4 = \frac{5}{12} \equiv 0 \pmod{5}.$$ Vidíme tak, že $5| p_{20}$. Všimnime si ďalej, že $H_1, H_2, H_3 \not\equiv 0 \pmod{5}$, preto $H_{20+i}\equiv H_{20}+H_i \equiv H_i \not \equiv0 \pmod{5}$ pre $i\in{1,2,3}$. Avšak nakoľko $H_4\equiv 0 \pmod{5}$, tak vidíme, že $H_{24}\equiv 0 \pmod{5}$, teda $5| p_{24}$. V tomto kroku tak vyhovujú $n=20$ a $n=24$.

V ďalšom kroku začíname s dvoma možnosťami, a to $n=20$ a $n=24$. Rovnica $\left\lfloor \frac{n}{5}\right\rfloor = 20$ má päť riešení $n\in{100,101,102,103,104}$. Všimnime si, že $$H_{100}=\frac{1}{1}+\cdots + \frac{1}{100}\equiv \frac{1}{5}+\frac{1}{10}+\cdots + \frac{1}{100}=\frac{1}{5}\cdot \left( \frac{1}{1} + \cdots + \frac{1}{20}\right) \equiv \frac{1}{5}\cdot \left( \frac{1}{5} + \frac{1}{10} + \frac{1}{15} + \frac{1}{20}\right) =\frac{1}{25}\cdot H_4 = \frac{1}{12}\equiv 3 \pmod{5},$$ pričom tu na kongruencie opäť používame Tvrdenie 2. Navyše, $H_{100+i}\equiv H_{100}+H_i\equiv 3+H_i\not\equiv 0 \pmod{5}$ pre $i\in{1,2,3,4}$, ako ľahko overíme z úvodného odstavca. Vidíme tak, že pre žiadne z týchto $n$ neplatí $5| p_n$.

Podobne, rovnica $\left\lfloor \frac{n}{5}\right\rfloor = 24$ platí pre $n\in{120,121,122,123,124}$. Všimnime si, že $H_{120}\equiv H_{100}+H_{20}\equiv 3 \pmod{5}$, a teda analogickým dokončením ako vyššie vidíme, že ani tu nie sú žiadne vyhovujúce $n$. Preto ďalšie $n$ generovať nemôžeme, a teda ${4,20,24}$ sú naozaj jediné hľadané $n$ z Tvrdenia 3. $\square$

Spojením úvodného pozorovania a Tvrdení 1 a 3 tak dostávame, že všetky $n\in\mathbb{N}$, pre ktoré $5\nmid q_n$, sú práve $$n\in{1,2,3,4,20,21,22,23,24,100,101,102,103,104,120,121,122,123,124}.$$