Školjka

Neka je $n=\prod \limits_{i=0}^k p_i^{a_i}$. Nađimo pomoću toga sumu djelitelja $n$. Neka je to funkcija $f(n)$. Tada je $$f(n)=\sum \limits_{0 \leq s_i \leq a_i} \prod \limits_{i=1}^k p_i^{s_i} =p_1^0 \sum \limits_{0 \leq s_i \leq a_i} \prod \limits_{i=2}^k p_i^{s_i} +...+ p_1^{a_1} \sum \limits_{0 \leq s_i \leq a_i} \prod \limits_{i=2}^k p_i^{s_i} =(p_1^0+...+p_1^{a})f(\frac{n}{p_1^{a_1}}) = ... = \prod \limits_{i=1}^k (p_i^0+...+p_i^{a_i})=\prod \limits_{i=1}^k \frac{p_i^{a_i+1}-1}{p_i-1}$$. Iz toga da je $f(n)$ potencija dva slijedi da je $p_i^{a_i+1}-1=2^k(p_i-1)$. Radi jasnoće (XD) zapišimo to u općenitijem obliku $a^x-1=2^k(a-1)$. Neka je $x=2^\alpha y$ gdje je $y$ neparan. Tada $a^y-1 \mid a^x-1 = 2^k(a-1)$. Slijedi da je $a^{y-1}+...+1$ potencija dva, ali kako je $y$ neparan dolazimo do kontradikcije pa je $y=1$ odnosno $x$ potencija broja dva. U našem slučaju je to $a_i+1$ potencija broja dva. Kako je broj djelitelja po poznatoj lemmi $\prod \limits_{i=1}^k (a_i+1)$ to je onda također potencija broja dva, što je i trebalo dokazati.