同余定理

播报讨论上传视频

数学术语

查看我的收藏

0有用+1

同义词同余（同余）一般指同余定理

本词条由“科普中国”科学百科词条编写与应用工作项目审核。

数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。^[1]

中文名: 同余定理
外文名: Congruence theorem
属性: 数学概念

记法: a≡b(mod d)
性质: 反身性、对称性、传递性等
相关定理: 欧拉定理、费马小定理、孙子定理

理论背景

播报

编辑

数学上，两个整数除以同一个整数，若得相同余数，则二整数同余（英文：Modular arithmetic，德文：Kongruenz）。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性的问题是很简便的。同余是数学竞赛的重要组成部分。

公元972年，在一份阿拉伯手稿中，提出了这样一个问题：一个正整数n何时能成为一个由三个有理平方数形成的等差数列的公差，也就是说x-n，x，x+n都是平方数。十三世纪，意大利数学家斐波那契指出5和7是同余数，他也猜想1、2、3不是同余数，但未能给出证明。直到1659年，法国大数学家费尔马运用他自己发明的无穷下降法证明了1、2、3不是同余数。十八世纪，大数学家欧拉首次证明了7是同余数。1952年，Heegner证明了任意模8余5、7的素数和任意模4余3的素数的两倍均为同余数。2000年，美国克雷数学研究所公布了千禧年七大数学难题，每破解其中一个难题者将获得100万美元的奖金。其中就有著名的BSD猜想（全称Birch and Swinnerton-Dyer猜想），而这个猜想与同余数问题有紧密的联系。2012年，田野证明了存在无穷多个具有任意指定素因子个数的同余数，这是在同余数问题上的一个根本性突破，也首次给出了解决BSD猜想的线索。^[2]

同余符号

播报

编辑

两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。

记作：a≡b (mod m)，

读作：a同余于b模m，或读作a与b对模m同余，例如26≡2(mod 12)。

定义

设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)，读作a与b对模m同余。

显然,有如下事实

（1）若a≡0(mod m)，则m|a；

（2）a≡b(mod m)等价于a与b分别用m去除，余数相同。

证明

充分性：

设a=mq1+r1,b=mq2+r2,0<=r1,r2<m

∵ m|(a-b),a-b=m(q1-q2)+(r1-r2).

则有m|(r1-r2).

∵0<=r1,r2<m

∴0<=|r1-r2|<m

又∵m|(r1-r2)

即r1-r2=0

∴r1=r2.

性质

播报

编辑

1.反身性：a≡a (mod m)；

2.对称性：若a≡b(mod m)，则b≡a (mod m)；

3.传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；

4.同余式相加：若a≡b(mod m)，c≡d(mod m)，则a

c≡b

d(mod m)；

5.同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。

证明：

∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),

∴m|[(a-b)+(b-c)]∴m|(a-c).

故a≡c(mod m).

6.线性运算：如果a ≡ b (mod m)，c ≡ d (mod m)，那么

(1)a ± c ≡ b ± d (mod m)；

(2)a * c ≡ b * d (mod m)。

证明：

(1)∵a≡b(mod m),

∴m|(a-b)

同理 m|(c-d)

∴m|[(a-b)±(c-d)]

∴m|[(a±c)-(b±d)]

∴a ± c ≡ b ± d (mod m)

(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)

又 m|(a-b) , m|(c-d)

∴m|(ac-bd)

∴a * c ≡ b * d (mod m)

7.除法：若

，则

，其中gcd(c,m)表示c和m的最大公约数，

特殊地，

则

；

8.幂运算：如果

，那么

；

9.若

，n=m，则

；

10.若

，(i=1,2...n) 则

，其中

表示m1,m2,...mn的最小公倍数。

相关定理

播报

编辑

1.欧拉定理：设a,m∈N，(a,m)=1，则

，

(注：φ(m)指模m的简系个数， φ(m)=m-1，如果m是素数；

2.费马小定理: 若p为质数，则

即

（但是当p|a时不等价）。

3.中国剩余定理（孙子定理）：

设整数

两两互素，令

（mi的连乘）。则对于任意的j在(1,n)整数，下列联立的同余式有解：

令x为从1到n，ajxj的和，则x适合下列联立同余式，

另：求自然数a的个位数字，就是求a与哪一个一位数对于模10同余。

一次同余式和孙子定理同余式的求解中，一次同余式是最基本的。设整系数n次(n>0)多项式

，(1)m是一个正整数且不能整除αn，则

叫做模m的n次同余式。如果整数α是(1)的解且

，那么α也是(1)的解，因此(1)的不同解是指满足(1)的模 m互不同余的数。对于一次同余式

有解的充分必要条件是(α,m)│b)，若有解则有(α,m)个解。一次同余式组是指

。 (2)

在中国古代《孙子算经》中，对某些具体的一次同余式组已有解法，把这一解法加以推广，就是著名的孙子剩余定理：设m1, m2,…, mk是k个两两互素的正整数

，则同余式组(2)的解是。式中，孙子剩余定理又被称之为中国剩余定理，是数论中一个重要的定理，除了数论本身，数学的许多其他分支以及一些应用学科都要用到它。例如,设

两两互素，利用孙子剩余定理可将同余式(1)的求解问题化为同余式组

的求解问题，于是就只需要研究(1)中m是素数方幂的情形了。又如,可将0≤x

两两互素，而x表示x模mi的最小非负剩余。

如果已知x的模系数记数法，就可用孙子定理找出x。这个记数法的优点是加法和乘法无须进位，它在计算机方面有应用。

素数为模的同余式关于素数为模的同余式，1770年，J.-L.拉格朗日证明了如下定理：设p是素数，那么模 p的n次同余式的解数不大于 n（重解也计算在内）。人们称之为拉格朗日定理。由此立即可以得威尔森定理：如果 p是素数，那么(p-1)!+1≡0(mod p)。因为x-1≡0(mod p)有p-1个解1,…,p-1，故由拉格朗日定理可得