• 1.摘要
  • 2.基本信息
  • 3.公式
  • 4.文献
  • 5.交换环上推广
  • 5.1.主理想整环
  • 5.2.一般的交换环
  • 6.数论相关
  • 7.例题解析
  • 8.参考资料

孙子定理

孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题,原文如下:

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。《孙子算经》中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。

基本信息

  • 中文名

    孙子定理

  • 外文名

    Chinese remainder theorem(CRT)

  • 分类

    数学

  • 提出

    孙子

  • 问题

    一元线性同余方程组

  • 又名

    余数定理

公式

用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组:

有解的判定条件,并用构造法给出了在有解情况下解的具体形式。

中国剩余定理说明:假设整数m1,m2, ... ,mn两两互质,则对任意的整数:a1,a2, ... ,an,方程组image有解,并且通解可以用如下方式构造得到:

image是整数m1,m2, ... ,mn的乘积,并设image是除了mi以外的n- 1个整数的乘积。

imageimageimage的数论倒数(imageimageimage意义下的逆元)image

方程组image的通解形式为image

在模image的意义下,方程组image只有一个解:image

证明1

从假设可知,对任何image,由于image,所以image这说明存在整数image使得image这样的image叫做imageimage的数论倒数。考察乘积image可知:

image

image

所以image满足:image

这说明image就是方程组image的一个解。

另外,假设imageimage都是方程组image的解,那么:

image

image两两互质,这说明image整除image. 所以方程组image的任何两个解之间必然相差image的整数倍。而另一方面,image是一个解,同时所有形式为:image

的整数也是方程组image的解。所以方程组所有的解的集合就是:image