氢原子百科 
同余（英文：Congruence[2]）是数论中的基本概念之一，其定义为：给定一个正整数m，把它叫作模，如果用m去除任意两个整数a与b所得的余数相同，则称a,b关于模m同余。[1]
同余理论的历史源远流长。公元400年左右，中国成书的《孙子算经》一书中所记载的“今有物不知其数”是关于同余式理论可能的最早论述。[6]公元1247年，数学家秦九韶在《数学九章》中进一步发展了孙子算法，给出了同余式的一般解法，称为大衍求一术。[4]德国数学家卡尔·弗里德里希·高斯（Carl Friedrich Gauss）被称为同余理论的创始人，[14]1801年，他在著作《算术研究》中首次引入了同余符号，并给出了最早的初等同余定理。[10]高斯在书中第一节定义了有理整数模一个自然同余的概念，并证明了同余的基本性质。之后在第二节中，他给出了一类同余方程的求解算法。[3]20世纪以来，数论中的同余概念得到了进一步发展。1927年，德国数学家阿廷（E.Artin）提出了一个关于模的原根的重要猜想，随后，霍勒（C.Hooley）等学者对其证明进行了尝试，但未能成功。[5]至21世纪初，阿廷猜想仍未得到完美解决。[2]
同余具有一些性质，如同余关系是一种等价关系，[1]它具有反身性、对称性和传递性等性质，由同余可衍生出同余类、剩余系的概念。[12]数论中的同余与其他数学分支有关，如同余数是一个三条边都是有理数的直角三角形的面积。[15]此外，在现实世界中，该概念具备广泛的应用价值，如在计算机科学中，同余检索方法的速度较快，可以改善检索效率和内存浪费。[9]
定义
同余：给定一个正整数，把它叫作模，如果用去除任意两个整数与所得的余数相同，则称关于模同余，记作
；
否则称关于模不同余，记作
。[1]
符号称为同余号，读作“同余于”，带同余号的表达式称为同余式，同余式的运算称为“模算术”。[11]
举例：。[11]
早期研究
同余理论是整除性理论的拓广与发展，[1]早在公元前3世纪，古希腊数学家欧几里得（Euclid）在著作《几何原本》中已有辗转相除法的相关陈述，[16]欧几里得的辗转相除法与成书于公元一世纪的中国《九章算术》中“以少减多，更相减损”的基本思想，在后来求解一次同余组等问题上有着重要应用。[17]公元400年左右，中国成书的《孙子算经》一书中所记载的“今有物不知其数”是关于同余式理论可能的最早论述。[6]公元1247年，数学家秦九韶在《数学九章》中进一步地发展了孙子算法，给出了同余式的一般解法，称为大衍求一术。[4]
后续发展
1640年，法国数学家费马（P.de Fermat）在一封写给德·贝西（B.F.de Bessy）的信中给出了费马小定理，[18]后来，瑞士数学家欧拉（L.Euler）在1736年正式发表了关于费马小定理的证明，并于1760年引进欧拉函数，推广了费马小定理，后称之为欧拉定理。[19]1771年，法国数学家拉格朗日（J.L.Lagrange）证明了威尔逊定理，[2]此外，他还给出了关于次整系数高次多项式同余方程有个解的充要条件，即拉格朗日定理。[20]德国数学家卡尔·弗里德里希·高斯（Carl Friedrich Gauss）被称为同余理论的创始人，[14]1801年，他在著作《算术研究》中首次引入了同余符号，并给出了最早的初等同余定理。[10]高斯在书中第一节定义了有理整数模一个自然同余的概念，并证明了同余的基本性质。之后在第二节中，他给出了一类同余方程的求解算法。[3]
20世纪以来，数论中的同余概念得到了进一步发展。1927年，德国数学家阿廷（E.Artin）提出了一个关于模的原根的重要猜想，即对于任意不等于，及完全平方的正整数，必定存在无穷多个素数，以为原根，特别是存在无穷多个素数，以为原根。1967年，霍勒（C.Hooley）在某种黎曼猜测成立的假定之下，证明了该猜想，并得到了以为原根的适合于的素数个数的渐近表达式。[5]至21世纪初，阿廷猜想仍未得到完美解决。[2]
基本性质
（1）充要条件：的充要条件是或。[1]
证明：（必要性）设，即，则故。[1]
（充分性）当时，设。若，则，因此。[1]
（2）同余关系是等价关系，[1]即有
反身性：；
对称性：；
传递性：。[12]
证明传递性：由条件可知，，则有，即，所以，证毕。[21]
（3）同余于模的充分必要条件是和被除后所得的最小非负余数相等，即若
，
，
则。[12]
运算性质
（1）可加性，即若有
，
则
。[12]
证明：由条件可知，，则有，所以，证毕。[12]
（2）可乘性，即若式成立，则有
。[12]
（3）如果，那么对于任意整数，有。[22]
证明：由条件可知，，两式相乘则有，所以，证毕。[12]
（4）可约性
若，则。[13]若，则。[13]若，则。[13]若，则。[13]
（5），其中，称为的最小公倍数。[23]
特别地，。[23]
（6）。[23]
（7）对任意整数，必存在不大于的自然数，使。[23]
同余数
定义：同余数是一个自然数，它是一个三条边都是有理数的直角三角形的面积，[15]用数学语言可表述为：设为正整数，若存在三个正有理数，满足和，则称为同余数。[24]
研究进展：公元10世纪，波斯的穆斯林数学家凯拉吉（Karaji）第一次提出同余数的概念。1225年，意大利数学家斐波那契（Fibonacci）指出和是同余数，但没有给出证明。后来，1659年，法国数学家费马（Fermat）完成了和是同余数的论证。从那之后，直到1915年，数学界大约确定了不到个的同余数。1952年，德国学者库尔特·翰哥纳（Kurt Heegner）证明等差数列中的所有素数都是同余数。在此基础上，到1980年，确定的同余数升至将近个。[25]
同余类
由同余的基本性质（1）可知，对给定的模，整数的同余关系是一个等价关系，因此全体整数可由等价关系分为两两不相交的类。于是可引入以下同余类的概念。[12]
定义：把全体整数由等价关系分为两两不相交的类，使得在同一个集合中的任意两个数对模一定同余，而属于不同集合中的两个数对模一定不同余。每一个集合称为模的同余类或模的剩余类。以表示所属的模的同余类。[12]同余类中的任一个数叫作该类的剩余或代表元。[26]
剩余系
剩余系：一组数，如果对任意的有且仅有一个是对模的剩余，即同余于模，称为模的完全剩余系，简称为模的剩余系。[12]例如，集合是模的一个完全剩余系。[27]
简化剩余系：与模互素的剩余类有[注1]个，从每类中各取一个数构成的集合，叫作模的一个简化剩余系；在模的最小非负完全剩余系中取得的简化剩余系，叫作模的最小正简化剩余系。[13]例如，集合是模的最小正简化剩余系。[13]
同余方程
定义：若是关于的整系数多项式，是大于的整数，且，则形如
的同余式叫做含有未知数的关于模的次同余方程，简称次同余方程。若是使成立的一个整数，则叫做同余方程的一个解。[28]
类型：（1）一次同余方程：若都是整数，是正整数，当时，把称为模的一元一次同余方程，又称线性同余方程。[16]对于一元一次同余方程，若，则方程有且仅有一个解；若，则方程无解。[29]
（2）一次同余方程组：形如的同余方程构成的方程组，称为一次同余方程组。是最简单的一次同余方程组，即
[16]
剩余：（1）二次剩余：设为整数，为素数，并且，如果同余方程有解，则称是模的二次剩余，否则便称是模的二次非剩余。[30]
（2）次剩余：设为任一正整数，如果同余方程有解，则叫做对模的一个次剩余；若该同余方程无解，则叫做对模的次非剩余。[31]
模逆元
定义：设和都是正整数，若存在一个使得同余式或者，则称为的模的逆元。[32]
一般情况下，如果和是互素的，那么存在，使得成立；而如果和不是互素的，那么不存在，使得成立。如果是一个素数，那么从到的每一个数与都是互素的，在这个范围内恰好有一个逆元。[32]
原根
模的指数：设，则使
成立的最小的正整数，称为对模的指数，记为。[33]
由欧拉定理可知，当时式成立，因此，恒有。若，则显然有。[注2][33]
原根：若，则称是模的原根。[33]
举例：当时，因为
，
所以，。又因为
，
所以，是模的原根。[33]
中国剩余定理
内容：设整数两两互素，则对任意整数，一次同余式组
总有整数解，且解集是恰为模的一个同余类。[11]
费马小定理
内容：设为整数，为素数，若，则。[13]
欧拉定理
拉格朗日定理
内容：假定是素数，那么同余方程
的解数，重解也计算在内。其中都是整数且。[34]
威尔逊定理
内容：如果为素数，那么。[2]
该定理的逆命题也是正确的，从而有：大于的自然数为素数的充分必要条件为。[2]
沃尔斯滕霍尔姆定理
内容：设素数，以表示满足
的一个整数，则
。[35]
卢卡斯定理
卡迈克尔函数
内容：为的卡迈克尔函数，[37]它表示满足
的最小的整数，其中是与互素的任意整数。[4]
递降阶乘幂
组合数最小周期
内容：设是任意素数，和是任意正整数，且有周期长度，其中。于是有
。[39]
应用例题
例1 试求使得为的倍数的所有正整数。[40]
解：因为，所以对按模进行分类讨论：
（1）当时，
；
（2）当时，
；
（3）当时，
。
综上，当正整数是的倍数时，才是的倍数。[40]
例2 试证：相邻四个整数的次幂的和不可能是另一个整数的次幂。[40]
证明：显然对任一奇数，都有
对任一偶数，都有
而相邻四个整数中必定有两个奇数和两个偶数，故
于是不可能是一个整数的次幂。证毕。[40]
例3 求证：对任意自然数，的个位数只能是或。[23]
解：易知，。
由带余除法，。
所以，。
而。
故的个位数只能是或。[23]
工程学
在高原地区，时差会影响旅客列车合理开行时间范围，因此，对于铁路的旅客列车合理开行时间范围的制定，应在满足行车组织要求的情况下，考虑高原时差和民族出行习惯等因素。在考虑高原时差的前提下可应用同余定理，通过研究分析兼顾沿途高原车站、客车车底折返和民族地区出行习惯等因素，可确定高原铁路的旅客列车合理开行时间范围，为合理制定旅客列车开行时间范围的列车运行图的铺画提供一定参考。[7]
密码学
代码混淆是一种抗软件逆向分析的方法，它能对拟发布的应用程序进行保持语义的变换，使得变换后的程序与原来的程序在功能上相同或相近，但更难被理解和反编译，从而保护软件知识产权。混淆变换的安全性基于不透明谓词，在代码混淆技术和中国剩余定理的基础上，可应用密钥和若干组同余方程解的状态来构造参数化的不透明谓词，所构造的不透明谓词具有较强的密码安全性，能抵抗静态和动态攻击，并有着较高的强度和较好的隐蔽性，能满足受保护程序对混淆变换的性能要求。[8]
计算机科学
在现实计算机工作中，常要检索一些编号大，但总体个数不多的信息，如学校检索学生证的号码、公安局检索市区丢失的自行车的号码等。传统的检索方法比较耗时耗力，且会浪费很多的计算机内存。为改善检索效率和内存浪费，可使用同余检索方法，该方法通过将检索号码的字长位数分区储存，在检索时先寻找区指针所示的区首址，找到后再与区内数据项进行逐一比较，能有效地增加检索速度，并节省计算机内存。[9]
参考资料 40
- 参考 1
- 参考 2
- 参考 3
- 参考 4
- 参考 5
- 参考 6
- 参考 7
- 参考 8
- 参考 9
- 参考 10
- 参考 11
- 参考 12
- 参考 13
- 参考 14
- 参考 15
- 参考 16
- 参考 17
- 参考 18
- 参考 19
- 参考 20
- 参考 21
- 参考 22
- 参考 23
- 参考 24
- 参考 25
- 参考 26
- 参考 27
- 参考 28
- 参考 29
- 参考 30
- 参考 31
- 参考 32
- 参考 33
- 参考 34
- 参考 35
- 参考 36
- 参考 37
- 参考 38
- 参考 39
- 参考 40
注释
- φ(m)称为欧拉函数，表示不超过正整数m又与m互素的正整数的个数。
- 欧拉定理：如果a与m互素，则aφ(m)-1可以被m整除。