Sea $p$ sea un primo impar. ¿Es posible calcular $\sum_{k=1}^{\frac{p-1}{2}}k^{-1}\bmod p$ más eficazmente que en $O(p)$ ?
Respuesta
¿Demasiados anuncios?
Roger Hoover
Puntos
56
En realidad no es una respuesta, sino un comentario largo para recopilar ideas.
Utilizando números de Stirling del segundo tipo $$\sum_{k=1}^{(p-1)/2}k^{-1}\equiv \sum_{k=1}^{(p-1)/2}k^{p-2}\equiv \sum_{k=1}^{(p-1)/2}\sum_{h=0}^{p-2}{p-2 \brace h}\binom{k}{h}h!\equiv \sum_{h=0}^{p-2}{p-2 \brace h}\binom{(p+1)/2}{h+1}h!\pmod{p} $$ y podría ser útil analógico de Teorema de Lucas para estos números de Stirling.
Otra posibilidad podría ser definir $$ P_l \equiv \sum_{k=1}^{(p-1)/2}k^l\pmod{p} $$ e inferir el valor de $P_{p-2}$ de $P_0=-\frac{1}{2},P_1=-\frac{1}{2^3},P_2=0,P_3=\frac{1}{2^6},P_4=0,P_5=-\frac{1}{2^7},P_6=0,P_7=\frac{17}{2^{11}}\ldots$
Aquí, por supuesto $\frac{1}{2}$ significa $2^{-1}\pmod{p}$ es decir $\frac{p+1}{2}$ . Algunas estrategias para la evaluación de los números de Bernoulli $\pmod{p}$ implican el teorema de Von Staudt-Clausen y el teorema chino del resto.
