模数学——简便解法（费马小定理？）

核心思路：分解模数+费马小定理+中国剩余定理 #

因为133=7×19（两个互质的质数），可以分别计算5^31 mod7和5^31 mod19，再通过中国剩余定理合并结果，比直接模幂运算更快捷。

步骤1：计算5^31 mod7

根据费马小定理，质数p下，若a与p互质，则a^(p-1)≡1 mod p：

• 7是质数，5和7互质，所以5^6≡1 mod7
• 31=6×5+1，因此5³¹⁼⁽⁵6)^5 ×5^1≡15×5=5 mod7

步骤2：计算5^31 mod19

同样用费马小定理：

• 19是质数，5和19互质，所以5^18≡1 mod19
• 31=18×1+13，因此5³¹⁼⁵18 ×5^13≡1×513 mod19
• 逐步简化5^13：
  • 5^2=25≡25-19=6 mod19
  • 5⁴⁼⁽⁵2)²⁼⁶2=36≡36-19=17≡-2 mod19
  • 5⁸⁼⁽⁵4)^2=(-2)2=4 mod19
  • 5¹³⁼⁵8 ×5^4 ×5^1=4×(-2)×5=-40≡-40+38=17 mod19

步骤3：用中国剩余定理合并结果

现在需要解同余方程组：

x≡5 mod7
x≡17 mod19

设x=19k+17，代入第一个式子：

• 19≡5 mod7，17≡3 mod7，所以5k+3≡5 mod7 →5k≡2 mod7
• 找5在mod7下的逆元：5×3=15≡1 mod7，逆元是3
• 两边乘3得：k≡2×3=6 mod7 →k=7m+6（m为整数）

代入x=19×(7m+6)+17=133m+114+17=133m+131，因此：
5^31≡131 mod133

内容的提问来源于stack exchange，提问作者user15049375