若$m^a=m \bmod pq$，则$m^a$和$m$相差$pq$的若干倍，因此也有$m^e=m \bmod p$以及$m^e=m \bmod q$。
反之若$m^a=x \bmod p$且$m^a=y \bmod q$， 那么$m^a=x+\left ((y-x)p^{-1} \bmod q\right)p \pmod pq$，其中$p^{-1}$是p在模q乘法群$\mathbb Z_q^*$中的逆，因此若$x=y=m$，则也有$m^a=m \bmod pq$。
进一步分析可知，若$m^a=m \bmod p$，则移项后可得或者p能整除m、或者$m^{a-1}=1 \bmod p$。
同理若$m^a=m \bmod q$，则或者q能整除m、或者$m^{a-1}=1 \bmod q$。
因此需要令$m^{a-1}=1$在模p乘法群$\mathbb Z_p^*$和模q乘法群$\mathbb Z_q^*$中的解尽可能少。
p和q都是素数，因此$\mathbb Z_p^*$和$\mathbb Z_q^*$事实上是阶数分别为$p-1$和$q-1$的循环群。
若$x_p,x_q$分别是群的生成元且$m=x_p^{t_p}=x_q^{t_q}$，那么$t_p$应当是$(p-1)/\gcd(p-1,a-1)$的倍数， $t_q$应当是$(q-1)/\gcd(q-1,e-1)$的倍数。
因此计入单位元，该方程在两个群中各自分别有$1+\gcd(e-1,p-1)$和$1+\gcd(e-1,q-1)$个解。
最后由中国剩余定理，可以取到上述解的合适的线性组合就可以生成$\mathbb Z_p^*$和$\mathbb Z_q^*$中的公共解，共有
$$\left(1+\gcd(e-1,p-1)\right)\times\left(1+\gcd(e-1,q-1)\right)$$
个。
遍历所有的$a$，求出上式的最小值（在本题中等于9，此时$\gcd(a-1,p-1)=\gcd(a-1,q-1)=2$）并将能取到该值的a相加即可得结果$399788195976$。
注：本题计算并不复杂，但需要有研究生水平的《抽象代数》课程知识才能分析解答。
import fractions
phi=1008*3642
m=1009*3642
r=0
p=set()
for e in range(2,phi):
if fractions.gcd(e,phi)==1:
a,b=fractions.gcd(e-1,1008),fractions.gcd(e-1,3642)
c=(1+a)*(1+b)
if c < m:
m=c
r=e
p=set([(a,b)])
elif c==m:
r+=e
p.add((a,b))
print r
|
