素数平方余数

令$p_n$为第n个素数，并记$r_n$为$(p_n-1)^n+(p_n+1)^n$模$p_n^2$所得的余数，例如： $$r_3\equiv (5-1)^3+(5+1)^3\equiv 280 \equiv 5 \pmod 25,$$ 首个超过$10^9$的余数$r_{7037}$，求使$r_n$超过$10^{10}$的最小n。

本题难度:

解答

用第120题中的方法可知需要找到最小的奇数$n$，使得$2np_n$模$p_n^2$超过$10^10$，暴力搜索即得$n=21035$。

target=1000000

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
p=[k for k in range(2,target) if d[k]==0]

i=2
while (2*p[i]*(i+1))%(p[i]*p[i])<=10000000000:
    i+=2
print i+1,p[i],(2*p[i]*(i+1))%(p[i]*p[i])