孙子剩余定理的乘法方法

注意:

n除以m和r，记为n = = r mod m。

n和l除以m有相同的余数，称为同余，记为n = = l mod m。

x==2模3

==3 mod 5

==2 mod 7

这在数论中称为同余方程组，简称同余群。

中国的余数定理(孙子定理)是求解同余组的手段之一(注意不是唯一的方法)。它的想法是这样的:

下面是为了解释方便，用我介绍的向量记号(我最近发现网上有些作者也有类似的记号)，可以这样写:

x==(2，3，2) mod (3，5，7)

制造

x1==(1，0，0)；即x1 = = 1mod3，x1 = = (0，0) mod (5，7)，即x1能被5，7整除。

x2==(0，1，0)；

x3==(0，0，1)

如此令人向往

x==2x1+3x2+2x3

求解x1时，由于x1可被(5*7)整除，我们可以设x 1 = 5 * 7 * k 1；

X1==1 mod 3，即5*7*k1==1 mod 3。

很明显，你可以取k1=2。这就是为什么提问者会问“为什么一定要把70乘以2？”其实可以走-1。

这个问题其实有一个更简单的解决方法，看我的另一个回答:

/question/106204827.html？si=1

K1这里当然好找；但是对于复杂的情况，比如

377873k的乘法率k≡1(mod499067)(见/userdir/longintmpq/upload/file/633303024867526250167 . pdf。

而洪博阳先生在《算法》中介绍:

见:/wsktuuytyh/blog/item/bfb 0 c 64 c 5580 fafcd 72 afcb 9 . html。

还有、先生的余数乘法和吴先生的序法，都可以解决这类问题。

下面是另一个相关回答，请参考:

/question/111491960 . html