if the starlight never fade

定义$f(i)$表示方程${(x+y)}^{i} equiv {x}^{i} (mod p), 1 leq x leq p-1, 1 leq y leq m $ 解的数量, $p$为素数。
要求计算$sum_{i=1}^{p-1}if(i)$。

令$g$为$p$的原根,$x equiv {g}^{a} (mod p)$, $y equiv {g}^{b} (mod p)$，那么有

$${ ({g}^{a}+{g}^{b}) }^{i} equiv {g}^{ai} (mod p)$$ $${(1+{g}^{b-a}) }^{i} equiv 1 (mod p)$$

注意到$1+{g}^{b-a} > 1$

可以令$1+{g}^{b-a} equiv {g}^{k} (mod p)$，则有

$${g}^{ki} equiv 1 (mod p).$$ $$ki equiv 0 (mod p-1).$$ $$k= frac{s times (p-1)}{i}$$ $$k= frac{t times (p-1)}{gcd(i, p-1)}$$

因为$k$不能取0，所以$k$有$gcd(i,p-1)-1$种取值，逆推上去，$f(i)=m (gcd(i, p-1)-1).$

$$sum_{i=1}^{p-1}if(i) = sum_{i=1}^{p-1}i m (gcd(i,p-1)-1)$$ $$= m sum_{i=1}^{p-1}igcd(i,p-1) - m frac{(p-1)p}{2}$$ $$S_{1} = m sum_{d|(p-1)}^{p-1}{d}^{2} sum_{e=1}^{ frac{p-1}{d}}e[gcd(e, frac{p-1}{d}) == 1]$$ $$= m sum_{d|(p-1)}^{p-1}{d}^{2} frac{ frac{(p-1)}{d} varphi(frac{(p-1)}{d})}{2}.$$