Opravovatelia

Vilčo [email protected]

Zo zadania vieme, že $p, q$ sú vzájomne rôzne prvočísla a že $r, s \in \mathbb{Z}^{+}$. Číslo $n$ je podľa zadania definované ako $n = p^r q^s$, teda $n^2 = (p^r q^s)^2 = p^{2r} q^{2s}$. Keďže chceme zistiť počet deliteľov $n^2$ neprevyšujúcich a zároveň nedeliacich $n$, poďme sa pozrieť na počty deliteľov čísel $n^2$ a $n$.

Ako zistíme počet deliteľov nejakého čísla? Nech číslo $a$ má prvočíselný rozklad $p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}$, kde $p_1, p_2, \dots, p_k$ sú vzájomne rôzne prvočísla. Na to, aby bolo nejaké číslo $d$ deliteľom čísla $a$, musí platiť, že prvočíselný rozklad čísla $d$ je nejaká časť prvočíselného rozkladu čísla $a$. Musí teda obsahovať rovnaké prvočísla $p_1, p_2, \dots, p_k$ ako prvočíselný rozklad čísla $a$, no tieto prvočísla môžu mať iné exponenty, ktoré ale nemôžu byť väčšie ako exponenty v prvočíselnom rozklade $a$. Teda keď chceme vytvoriť deliteľa čísla $a$, tak pri každom prvočísle $p$ z prvočíselného rozkladu vyberáme exponenty z množiny $\left{0, 1, \dots, m\right}$, ktorých je $m+1$. Počet deliteľov čísla $a$ teda bude $(m_1 + 1) (m_2 + 1) \cdots (m_k + 1)$.

Koľko deliteľov teda má $n$? A koľko $n^2$? S použitím vyššie ukázaného vzorčeka vieme zistiť, že $n$ má $(r + 1)(s + 1) = r s + r + s + 1$ deliteľov, zatiaľ čo $n^2$ má $(2r + 1)(2s + 1) = 4rs + 2r + 2s + 1$ deliteľov. Nech $d \in \mathbb{Z}^+$ je nejaký deliteľ $n^2$, ktorý neprevyšuje $n$. Potom vieme, že podiel $\frac{n^2}{d}$ určite nie je menší ako $n$, teda $\frac{n^2}{d} \geq n$. Každý deliteľ $n^2$, ktorý je menší alebo rovný ako $n$, má svoj „opak“, teda deliteľa väčšieho alebo rovného $n$. Polovica deliteľov $n^2$ bude menšia alebo rovná $n$, čo je $2rs + r + s + 1$ deliteľov ($n^2$ má $n$ ako „zdvojeného deliteľa“). Taktiež však vieme, že každý deliteľ $n$ je aj deliteľom $n^2$ a zároveň žiaden z deliteľov čísla $n$ ho určite neprevyšuje. Počet deliteľov čísla $n^2$, ktoré neprevyšujú číslo $n$ a ani nie sú jeho deliteľmi, je teda $(2rs + r + s + 1) - (rs + r + s + 1) = rs$.