中国剩余定理与拉格朗日插值

中国剩余定理

中国剩余定理(孙子定理,Chinese Remainder Theorem),是数论中关于一元线性同余方程组的一个定理。

形式描述

CRT给出了如下一元线性同余方程组:

(S):\begin{cases}x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \\ \vdots \\ x\equiv a_n\pmod{m_n} \\ \end{cases}

有解的判定条件,并用构造法给出了通解的具体形式。
中国剩余定理说明:若m_1,m_2,…,m_n其中任意两数互质,则对于任意的整数a_1,a_2,…,a_n,方程组(S)有解,并且通解可以通过如下方式构造得到:

  • M=\prod\limits_{i=1}^n m_iM_i=\frac {M} {m_i}=\prod\limits_{j\not=i}m_j.
  • t_i=M_i^{-1}\pmod{m_i},方程组(S)的通解形式为x=\sum\limits_{i=1}^n a_it_iM_i+kMk\in \Bbb{Z}. 在模M意义下,方程组(S)只有一个解x=\sum\limits_{i=1}^n a_it_iM_i.

证明

由假设的条件可知,对任意i\not=j(m_i,m_j)=1,所以(m_i,M_i)=1t_i存在。
则对于a_it_iM_i,有:

  • a_it_iM_i\equiv a_i\cdot 1\equiv a_i\pmod{m_i}
  • \forall j\not=ia_it_iM_i\equiv 0\pmod{m_j}

所以x=\sum\limits_{i=1}^n a_it_iM_i满足:

  • \forall ix\equiv a_it_iM_i+\sum\limits_{j\not=i}a_jt_jM_j\equiv a_i+0\equiv a_i\pmod{m_i}

这样就完成了对一个解的构造。
并且,若x_1,x_2都是(S)的解,则对\forall i,都有x_1-x_2\equiv 0\pmod{m_i}. 因为m_1,m_2,…,m_n两两互质,所以M\mid x_1-x_2. 这就说明了通解的形式为:

x=\sum\limits_{i=1}^n a_it_iM_i+kM,\space k\in \Bbb{Z}

所以方程组(S)的解集:

\Big\lbrace \sum\limits_{i=1}^n a_it_iM_i+kM\mid k\in\Bbb{Z}\Big\rbrace

韩信带1500名兵士打仗,战死四五百人,站3人一排,多出2人;站5人一排,多出4人;站7人一排,多出6人。问还剩几人?
解:
设还剩x人,由题意得:

(S):\begin{cases}x\equiv 2\pmod{3}\\ x\equiv 4\pmod{5}\\ x\equiv 6\pmod{7}\\ \end{cases}

M=3\cdot 5\cdot 7=105M_1=\frac {105} {3}=35M_2=\frac {105} {5}=21M_3=\frac {105} {7}=15t_1=2t_2=1t_3=1. 所以x=2\cdot 2\cdot 35+4\cdot 1\cdot 21+6\cdot 1\cdot 15+105k=314+105k,\space k\in \Bbb{Z}. 由于战死四五百人,因此答案就是1049.

补充说明

另外,对于存在不互质的同余方程组,可以先化成两两互质的同余组,再运用定理计算。
若化出的同余组存在矛盾,则必无解。


事实上,CRT和拉格朗日插值法构造的时候是较为类似。这种构造思想非常通用。
那么我们接下来就来讲一讲拉格朗日插值法。


拉格朗日插值法

定义

对某个多项式函数,已知有给定的k+1个取值点:

(x_0,y_0),…,(x_k,y_k)

其中x_j对应着自变量的位置,而y_j对应着函数在这个位置的取值。
假设任意两个不同的x_j都互不相同,那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为:

L(x):=\sum\limits_{j=0}^ky_j\ell_j(x)

其中每个 \ell _{j}(x)拉格朗日基本多项式(或称插值基函数),其表达式为:

\ell_j(x):=\prod\limits_{i=0,i\not=j}^k\frac {x-x_i} {x_j-x_i}=\frac {x-x_0} {x_j-x_0}\cdot …\cdot \frac {x-x_{j-1}} {x_j-x_{j-1}}\cdot \frac {x-x_{j+1}} {x_j-x_{j+1}}\cdot …\cdot \frac {x-x_k} {x_j-x_k}

拉格朗日基本多项式\ell_j(x)的特点是在x_j上取值为1,在其它的点x_i,i\not=j上取值为0.
利用这个方法我们可以较快地导出一个多项式。(如自然数幂和之类的)

证明

拉格朗日基本多项式的存在性由定义显然。
下面证明唯一性,即次数不超过k的拉格朗日多项式至多只有一个。
对任意两个不超过k的拉格朗日多项式P_1P_2,它们的差P_1-P_2x_0,x_1,…,x_k这所有k+1个点上的取值都是0,因此它必是多项式(x-x_0)(x-x_1)…(x-x_k)的倍数。所以,若P_1-P_2\not=0,次数就一定不小于k+1;若P_1-P_2是两个次数不超过k的多项式的差,则它的次数也不超过k,因此P_1-P_2=0,即P_1=P_2.这也就证明了唯一性。

求2次幂和公式。
解:
f(x)=\sum\limits_{i=1}^xi^2,易知f(x)是3次多项式。取x=1,2,3,4带入,得:

x=1f(x)=1x=2f(x)=5x=3f(x)=14x=4f(x)=30.

\ell_1(x)=\frac {x-2} {1-2}\cdot\frac {x-3} {1-3}\cdot\frac {x-4} {1-4}\ell_2(x)=\frac {x-1} {2-1}\cdot\frac {x-3} {2-3}\cdot\frac {x-4} {2-4}\ell_3(x)=\frac {x-1} {3-1}\cdot\frac {x-2} {3-2}\cdot\frac {x-4} {3-4}\ell_4(x)=\frac {x-1} {4-1}\cdot\frac {x-2} {4-2}\cdot\frac {x-3} {4-3}.

所以f(x)=\ell_1(x)+5\ell_2(x)+14\ell_3(x)+30\ell_4(x)=\frac {1} {6}x(x+1)(2x+1).


参考资料

About The Author

发表评论

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