level 5
观察法只适合小的数值,一般需要使用辗转相除法(也叫大衍求一术)
如 求解 64x=1(mod105)
105=1×64+41
64=1×41+23
41=1×23+18
23=1×18+5
18=3×5+3
5=1×3+2
3=1×2+1
按此反推 1=3-1×2=3-1×(5-1×3)=2×3-1×5=2×(18-3×5)-1×5=2×18-7×5
=2×18-7×(23-18)=9×18-7×23=9×(41-23)-7×23=9×41-16×23
=9×41-16×(64-41)=25×41-16×64=25×(105-64)-16×64=25×105-41×64
因此 -41×64=1(mod 105)
因此 x=-41=105-41=64(mod 105) 验算64×64=4096=39×105+1
方程64x=1(mod105)的解为 x=64(mod105)
求解 64x=83(mod105)的解为 x=64×83=5312=62(mod105)
类似求解128x=1(mod 1001) 有解x=305(mod 1001)
因此128x=833(mod 1001) 有解x=305×833=812(mod 1001)
2021年11月06日 09点11分
