同余定理
数学上，两个整数除以同一个整数，若得相同余数，则二整数同余（英文：Modular arithmetic，德文：Kongruenz）。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性的问题是很简便的。同余是数学竞赛的重要组成部分。
公元972年，在一份阿拉伯手稿中，提出了这样一个问题：一个正整数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猜想的线索。同余符号两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。
记作：
，读作：a同余于b模m，或读作a与b对模m同余，例如
。定义设m是大于1的正整数，a、b是整数，如果
，则称a与b关于模m同余，记作，读作a与b对模m同余。显然，有如下事实
（1）若
，则；（2）
等价于a与b分别用m去除，余数相同。证明充分性：
。
设
，，且
，∵
，又
。∴必有常数n使得
。则有
。∵
∴
，∴
即
=，故。必要性：
。
设a,b用m去除余数为r，
即
,。∵
，∴
。性质1.反身性：
；2.对称性：若
3.传递性：若
；4.同余式相加：若
则；5.同余式相乘：若
。证明：
∵
,∴
故
.6.线性运算：如果
，那么(1)
；(2)
。证明：
(1)∵
,∴
同理
∴
∴
∴
(2)∵
又
∴
∴
7.除法：若
，则，其中表示c和m的最大公约数，特殊地，则；8.幂运算：如果
，那么；9.若
，，则；10.若
，() 则，其中 表示的最小公倍数。定理1.欧拉定理：设
，则，(注：
指模m的简系个数，，如果m是素数；2.费马小定理: 若p为质数，则 即（但是当时不等价）。3.中国剩余定理（孙子定理）：
设整数
两两互素，令（的连乘）。则对于任意的j在(1,n)整数，下列联立的同余式有解：令x为从1到n，
的和，则x适合下列联立同余式，另：求自然数a的个位数字，就是求a与哪一个一位数对于模10同余。一次同余式和孙子定理同余式的求解中，一次同余式是最基本的。设整系数n次(
)多项式，(1)m是一个正整数且不能整除αn，则 叫做模m的n次同余式。如果整数α是(1)的解且，那么α也是(1)的解，因此(1)的不同解是指满足(1)的模 m互不同余的数。对于一次同余式 有解的充分必要条件是，若有解则有()个解。一次同余式组是指。 (2)在中国古代《孙子算经》中，对某些具体的一次同余式组已有解法，把这一解法加以推广，就是著名的孙子剩余定理：设是k个两两互素的正整数，则同余式组(2)的解是。式中，孙子剩余定理又被称之为中国剩余定理，是数论中一个重要的定理，除了数论本身，数学的许多其他分支以及一些应用学科都要用到它。例如，设 两两互素，利用孙子剩余定理可将同余式(1)的求解问题化为同余式组 的求解问题，于是就只需要研究(1)中m是素数方幂的情形了。又如，可将中的一切整数表示，这叫做模系数记数法，这里两两互素，而x表示x模mi的最小非负剩余。如果已知x的模系数记数法，就可用孙子定理找出x。这个记数法的优点是加法和乘法无须进位，它在计算机方面有应用。
素数为模的同余式关于素数为模的同余式，1770年，J.-L.拉格朗日证明了如下定理：设p是素数，那么模 p的n次同余式的解数不大于 n（重解也计算在内）。人们称之为拉格朗日定理。由此立即可以得威尔森定理：如果 p是素数，那么
。因为个解故由拉格朗日定理可得将代入上式得,这就证明了威尔森定理。威尔森定理的逆定理也是成立的，可用反证法简单证出。用拉格朗日定理还可证明：当是一个素数时，则有同余。这个定理是1862年，由J.沃斯顿霍姆证明的。设
是n元整系数多项式,p是一个奇素数，对于同余式的解的个数N的研究，是数论的重要课题之一。早在1801年，C.F.高斯就研究了同余式
的解的个数，这里和同余式的解的个数，这里。设?(x)模 p无重因式，1924年，E.阿廷猜想同余式
，在?(x)的次数为3和4时，N分别满，1936年，H.哈塞证明了这一猜想，并且还证明了对于一般含q个元的有限域，把以上两式中p换成q，也是对的。1948年，韦伊对于一般的在有限域上得到类似的结果，他猜想对于也有类似的结果。1973年，P.德利涅证明了韦伊猜想。他的杰出工作获得了1978年的国际数学家会议的费尔兹奖。