同余

两个整数除以同一正整数可得到相同的余数
image
同余（英文：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]

定义

同余：给定一个正整数
，把它叫作模，如果用
去除任意两个整数
与
所得的余数相同，则称
关于模
同余，记作