中国剩余定理

线性同余方程组

形如\( x_1\equiv a_1(mod\ m_1) \)的多个同余方程所构成的方程组.古代有民谣:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?这转化成数学语言就是一个典型的同余方程组.

公式

所谓线性同余方程组给定的也就是形如下文的式子.

\[ \begin{cases} x_1\equiv a_1(mod\ m_1)\\x_2\equiv a_2(mod\ m_2) \\……\\x_n\equiv a_n(mod\ m_n)\end{cases} \]

中国剩余定理讲的是对于这类线性同余方程,如果存在\(m_1,m_2…m_n\)这些数字两两互质,那么一定可以得到方程的通解,并且可以通过以下公式构造.

设\( M=\prod_1^nm_i,M_i=M/m_i,\forall i\in{1,2,3…n},inv_i=M_i^{-1},M_i*inv_i\equiv1\ mod\ m_i,\forall i\in{1,2,3…n} \)

则方程通解形式为\(x=a_1inv_1M_1+a_1inv_1M_2+···+a_ninv_nM_n+KM <=>\sum_{i=1}^na_iinv_iM_i+KM,K\in Z \)

在模\(M\)意义下解只有\(\sum_{i=1}^na_iinv_iM_i\).


举个栗子:

问题:

一堆物品

3个3个分剩2个

5个5个分剩3个

7个7个分剩2个

问这个物品有多少个

解这题,我们需要构造一个答案

我们需要构造这个答案

5*7*inv(5*7, 3) % 3 = 1

3*7*inv(3*7, 5) % 5 = 1

3*5*inv(3*5, 7) % 7 = 1

然后两边同乘你需要的数

2 * 5*7*inv(5*7, 3) % 3 = 2

3 * 3*7*inv(3*7, 5) % 5 = 3

2 * 3*5*inv(3*5, 7) % 7 = 2

a = 2 * 5*7*inv(5*7, 3)

b = 3 * 3*7*inv(3*7, 5)

c = 2 * 3*5*inv(3*5, 7)

那么

a % 3 = 2

b % 5 = 3

c % 7 = 2

其实答案就是a+b+c

因为

a%5 = a%7 = 0 因为a是5的倍数,也是7的倍数

b%3 = b%7 = 0 因为b是3的倍数,也是7的倍数

c%3 = c%5 = 0 因为c是3的倍数,也是5的倍数

所以

(a + b + c) % 3 = (a % 3) + (b % 3) + (c % 3) = 2 + 0 + 0 = 2

(a + b + c) % 5 = (a % 5) + (b % 5) + (c % 5) = 0 + 3 + 0 = 3

(a + b + c) % 7 = (a % 7) + (b % 7) + (c % 7) = 0 + 0 + 2 = 2

你看你看,答案是不是a+b+c(。・ω・)ノ゙,完全满足题意

但是答案,不只一个,有无穷个,每105个就是一个答案(105 = 3 * 5 * 7)

根据计算,答案等于233,233%105 = 23

如果题目问你最小的那个答案,那就是23了


证明

首先,方程组在模M的意义下有且仅有一组解.M意义同上

令\(n_i\)满足\( n_i\%\frac{M}{m_i}=0,n_i\%m_i=1 \).那么\( N=\sum_{i=1}^nn_i*a_i \)便是方程的一个解.(其实就是把所有乘到一起)

根据上面的式子可以得出\( n_i=\frac{M}{m_i}x,n_i=m_iy+1 \)(也就是上面\(n_i\)满足的两个式子转化一下)

两式相等则\( \frac{M}{m_i}x=m_iy+1 \),且\(m_i\)相互两两互质.

所以可得\( gcd(\frac{M}{m_i},m_i)==1 \),令\(a=\frac{M}{m_i},b=m_i=>ax-by=1\)

有没有发现这个就是我们说的丢番图方程扩欧的基本形式.

因为\( N=\sum_{i=1}^nn_i*a_i \)是方程的一个解.而\( n_i=\frac{M}{m_i}x,n_i=m_iy+1 \)所以任取一个求出\(n_i\)就好了.

右边的可以去shi了不太懂的看代码实现.

代码实现


拓展

​ 我们知道前面那个答案是当且仅当\(n\)个模数互质的时候.如果不互质的时候呢?我们需要更加牛逼的证明和构造答案的公式.

给定两个方程

\(x\equiv a_1(mod\ m_1)\)

\(x\equiv a_2(mod\ m_2\)

考虑将这两个式子合并.由裴蜀定理可知\((m1,m2)|(c2−c1)\)

\(m=\frac{(m_1,m_2)}{(m_1,m_2)}\)
\( c=(inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})∗\frac{(c_2−c_1)}{(m_1,m_2)})\%\frac{m_2}{(m_1,m_2)}∗m_1+c_1 \)

最终得出一个式子\( x\equiv c(mod\ m_1) \)
\(x=c\%m\)即为原问题的一个解

证明

将两个方程写成\(x=m_1k_1+c_1,x=m_2k_2+c_2\),两式联立得\(m_1k_1+c_1=m_2k_2+c_2\),移项\(m_1k_1=c_2−c_1+m_2k_2\)

将等式两边同除\((m1,m2)\)得\( \frac{m_1}{(m_1,m_2)}∗k_1=\frac{(c2−c1)}{(m_1,m_2)}+\frac{m_2}{(m_1,m_2)}∗k_2<=>\frac{m_1}{(m_1,m_2)}k_1\equiv\frac{(c_2−c_1)}{(m_1,m_2)}(mod\ \frac{m_2}{(m_1,m_2)}) \)

进一步化简

\( k_1\equiv inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})∗\frac{(c_2−c_1)}{(m_1,m_2)}(mod\ \frac{m_2}{(m_1,m_2)}) \)

\( k_1=inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2))}∗\frac{(c_2−c_1)}{(m_1,m_2)}+y\frac{m_2}{(m_1,m_2)} \)

将其回代\( x=m_1k_1+c_1=>x=inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})∗\frac{(c_2−c_1)}{(m_1,m_2)}∗m_1+y\frac{m_1m_2}{(m_1,m_2)}+c_1 \).

即\( x\equiv inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})∗\frac{(c_2−c_1)}{(m_1,m_2)}∗m_1+c_1(mod\ \frac{m_1m_2}{(m_1,m_2)}) \)
至此我们又将其化简成了\(x\equiv c(mod\ m)\)的形式,

其中\( m=\frac{m_1m_2}{(m_1,m_2)},c=(inv(\frac{m_1}{(m_1,m_2)},\frac{m_2}{(m_1,m_2)})∗\frac{(c_2−c_1)}{(m_1,m_2)})\%\frac{m_2}{(m_1,m_2)}∗m_1+c_1 \)

发表评论

电子邮件地址不会被公开。 必填项已用*标注