0381 素数阶乘
* * * *
拉格朗日计划
* * * *
素数阶乘

给定素数p,令 $$S(p)=\sum_{k=1}^5(p-k)! \pmod p.$$ 例如 $$S(7)=(7-1)!+(7-2)!+(7-3)!+(7-4)!+(7-5)!=6!+5!+4!+3!+2!=720+120+24+6+2=872=4 \pmod p.$$ 可以验证 $$\sum_{5\le p < 100}S(p)=480.$$ 求$\sum_{5\le p < 10^8}S(p)$。

本题难度:



解答

令 $$a=(p-5)! \bmod p,$$ 则有 $$S(p)=a+(-4)a+(-4)(-3)a+(-4)(-3)(-2)a+(-4)(-3)(-2)(-1)a=9a \pmod p.$$ 又由Wilson定理可知$(p-1)! \bmod p=-1$,即 $$24a=-1 \pmod p.$$ 在模p乘法群中求出a的值(为减少码量,这一步用sympy实现)再汇总即得结果$139602943319822$。

注:因需使用sympy库,以下代码为Python 3。

import sympy

target=10**8
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

print(sum((9*sympy.mod_inverse(-24,p))%p for p in range(5,target) if d[p]==0))