孙子定理
孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题,原文如下:
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。《孙子算经》中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。
基本信息
- 中文名
孙子定理
- 外文名
Chinese remainder theorem(CRT)
- 分类
数学
- 提出
孙子
- 问题
一元线性同余方程组
- 又名
余数定理
公式
用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组:
有解的判定条件,并用构造法给出了在有解情况下解的具体形式。
中国剩余定理说明:假设整数m1,m2, ... ,mn两两互质,则对任意的整数:a1,a2, ... ,an,方程组
有解,并且通解可以用如下方式构造得到:
设
是整数m1,m2, ... ,mn的乘积,并设
是除了mi以外的n- 1个整数的乘积。
设
为
模
的数论倒数(
为
模
意义下的逆元)![]()
方程组
的通解形式为![]()
在模
的意义下,方程组
只有一个解:
证明1:
从假设可知,对任何
,由于
,所以
这说明存在整数
使得
这样的
叫做
模
的数论倒数。考察乘积
可知:
![]()
![]()
所以
满足:![]()
这说明
就是方程组
的一个解。
另外,假设
和
都是方程组
的解,那么:
![]()
而
两两互质,这说明
整除
. 所以方程组
的任何两个解之间必然相差
的整数倍。而另一方面,
是一个解,同时所有形式为:![]()
的整数也是方程组
的解。所以方程组所有的解的集合就是:![]()