1 基本定义
整数同余类是数论中描述“按模分类”的基本对象。它把所有整数按照某个模数下的余数结构分组，使原本无穷多个整数在研究时可以被压缩为有限个类别。借助这一概念，许多关于整除、余数和周期性的讨论都能以更简洁的方式表达。
1.1 同余关系
设 \(a,b,m\) 为整数，且 \(m>0\)。如果 \(a-b\) 能被 \(m\) 整除，就称 \(a\) 与 \(b\) 模 \(m\) 同余，记作 \[ a \equiv b \pmod m. \] 这表示二者在除以 \(m\) 后得到相同的余数。比如，\(17 \equiv 2 \pmod 5\)，因为 \(17-2=15\) 是 5 的倍数。
1.2 同余类的定义
在模 \(m\) 的意义下，所有与某个整数 \(a\) 同余的整数构成一个集合，称为 \(a\) 的同余类。这个集合可写作 \[ [a]=\{x\in \mathbb Z \mid x\equiv a \pmod m\}. \] 例如，在模 4 下，整数 1 的同余类包含 \(\ldots,-7,-3,1,5,9,\ldots\)。同余类并不只代表一个数，而是一整组具有相同余数特征的整数。
1.3 模数与余数
模数 \(m\) 是定义同余关系时所依据的正整数。它决定了同余类的划分方式，也决定了余数的取值范围。对于任意整数 \(a\)，除以 \(m\) 后都能得到唯一余数 \(r\)，满足 \[ a=qm+r,\quad 0\le r<m. \] 这个余数 \(r\) 决定了 \(a\) 所属的同余类。不同模数会给出不同的分类结果，因此模数是同余理论中的核心参数。
1.4 代表元与标准表示
同余类中的每个整数都可作为该类的代表元，但通常会选取一个最方便的数作为“标准表示”。最常见的做法是取最小非负余数，即 \(0,1,\dots,m-1\) 中的某一个。这样处理后，同余类可以用有限个代表元来描述，便于计算和比较。
2 代数性质
同余类不仅是集合意义上的分类结果，还具有稳定的代数性质。它们在加法、减法和乘法下都能保持一致的模结构，因此可以建立起完善的算术体系。
2.1 等价关系性质
模 \(m\) 同余关系是一种等价关系。也就是说，它满足自反性、对称性和传递性。这一特征保证了整数可以被清晰地划分为若干互不重叠的同余类。
2.1.1 自反性
任意整数 \(a\) 都满足 \(a-a=0\)，而 0 显然能被任何正整数整除，因此 \[ a\equiv a\pmod m. \] 这说明每个整数都与自身同余。
2.1.2 对称性
如果 \(a\equiv b\pmod m\)，则 \(a-b\) 可被 \(m\) 整除。于是 \(b-a=-(a-b)\) 也可被 \(m\) 整除，所以 \[ b\equiv a\pmod m. \] 同余关系因此具有双向性。
2.1.3 传递性
若 \(a\equiv b\pmod m\) 且 \(b\equiv c\pmod m\)，则 \(a-b\) 与 \(b-c\) 都是 \(m\) 的倍数。两式相加得 \(a-c\) 也是 \(m\) 的倍数，于是 \[ a\equiv c\pmod m. \] 这使得同余类的划分具有一致性。
2.2 同余类的运算
在同一模数下，同余类之间可以进行运算，且结果仍落在同余类中。这种运算规则与普通整数运算相似，但最终只保留模 \(m\) 的结果。
2.2.1 加法
若 \(a\equiv b\pmod m\) 且 \(c\equiv d\pmod m\)，则 \[ a+c\equiv b+d\pmod m. \] 因此，同余类可以按加法相加，所得结果只与各自的类有关，而与代表元的具体选取无关。
2.2.2 减法
同样地，若 \(a\equiv b\pmod m\) 且 \(c\equiv d\pmod m\)，则 \[ a-c\equiv b-d\pmod m. \] 这说明同余关系对减法也保持稳定，便于处理差值和方程。
2.2.3 乘法
若 \(a\equiv b\pmod m\) 且 \(c\equiv d\pmod m\)，则 \[ ac\equiv bd\pmod m. \] 乘法同余是模运算中最常用的规则之一，许多幂运算与快速算法都建立在这一性质之上。
2.3 逆元与单位元
在模运算中，并非所有元素都能像普通整数那样自由地进行除法运算。只有在满足一定条件时，某个元素才存在逆元。
2.3.1 加法逆元
对于任意同余类 \([a]\)，都存在加法逆元 \([-a]\)，使得 \[ [a]+[-a]=[0]. \] 也就是说，每个类都能找到一个相反数，使两者相加后回到零类。
2.3.2 乘法逆元
若某个数 \(a\) 与模数 \(m\) 互素，则它在模 \(m\) 下常具有乘法逆元，即存在 \(x\) 使 \[ ax\equiv 1\pmod m. \] 这类元素称为可逆元。乘法逆元并不总是存在，这也正是模运算与实数除法的重要差别。
2.4 封闭性与结合律
同余类在加法和乘法下都具有封闭性：两个同余类运算后仍得到同一模数下的同余类。此外，这些运算继承了整数运算的结合律和交换律，使得模算术可以像普通代数一样进行形式化处理。正因为如此，同余类能够构成严谨的代数系统。
3 同余类的结构
同余类不仅是计算工具，也具有明确的集合与代数结构。它们把整数按照模数划分为有限多个部分，并由此引出商集、商环以及循环群等概念。
3.1 模 n 的剩余类
对固定模数 \(n\)，整数集合被分成 \(n\) 个基本剩余类，通常记为 \[ [0],[1],\dots,[n-1]. \] 每个整数都恰好属于其中一个类。这个分解揭示了整数在模 \(n\) 意义下的完整余数图景。
3.2 完全剩余系
完全剩余系是指模 \(n\) 下各个不同同余类各取一个代表元所组成的集合。它能完整覆盖所有模 \(n\) 的类别，因此是模运算中的常用表示方式。
3.2.1 最小非负剩余系
最小非负剩余系取 \(0\) 到 \(n-1\) 之间的整数作为代表元。这种表示最直观，也最常用于计算机和初等数论中。它的优点在于唯一且便于比较。
3.2.2 对称剩余系
对称剩余系则倾向于选择围绕 0 对称的一组代表元，例如在模 7 下可取 \[ -3,-2,-1,0,1,2,3. \] 这种表示在某些证明和手算中更方便，尤其适合处理正负数的平衡形式。
3.3 商集与商环
同余类从抽象代数角度看，可以组成一个商集；若进一步考虑加法和乘法结构，则能形成商环。这是模算术得以系统化的重要基础。
3.3.1 等价类的划分
同余关系将整数集合分成若干互不相交的等价类，每个整数只属于一个类。这种划分方式保证了分类的完整性与唯一性，是商结构的基本前提。
3.3.2 环结构的建立
将所有模 \(n\) 的同余类作为对象，并定义相应的加法与乘法后，可以得到整数模 \(n\) 的商环，常记为 \(\mathbb Z/n\mathbb Z\)。在这个结构中，运算规则与普通整数相似，但结果始终回到有限集合中，因此便于分析周期性和可逆性。
3.4 循环群视角
从加法角度看，模 \(n\) 的同余类形成一个循环群。其元素可由一个生成元反复相加得到，结构紧凑而规整。这个视角有助于理解模运算的周期特征，也说明同余类在群论中占有自然位置。
4 计算与判定
同余类不仅是理论对象，也常用于实际判断和计算。通过若干简单规则，可以快速判定两个整数是否同余，或将复杂表达式化简到较小范围内。
4.1 同余判断方法
判断同余的核心，是检查两数之差是否能被模数整除，或直接比较它们在除法中的余数。
4.1.1 直接整除检验
若要判断 \(a\equiv b\pmod m\)，只需看 \(a-b\) 是否是 \(m\) 的倍数。这种方法最直接，尤其适用于数值较小或因式结构明显的情况。
4.1.2 余数计算法
另一种做法是分别求 \(a\) 与 \(b\) 除以 \(m\) 的余数。若余数相同，则二者同余。这种方法在实际算题中非常常见，也最符合“余数分类”的直观含义。
4.2 常用运算规则
同余运算的基本规则使复杂表达式可以逐步替换为等价的更简形式。
4.2.1 加法同余
若 \(a\equiv b\pmod m\) 与 \(c\equiv d\pmod m\)，则可直接推出 \[ a+c\equiv b+d\pmod m. \] 因此，运算过程中可先分别化简再相加，效率较高。
4.2.2 乘法同余
若两个因子分别同余，则它们的乘积也同余。这个规则常用于把大数乘积拆分后逐步取模，以避免中间结果过大。
4.2.3 幂的同余
如果底数同余，则其任意正整数次幂也同余。即若 \(a\equiv b\pmod m\)，那么 \[ a^k\equiv b^k\pmod m. \] 这一性质在快速幂和周期计算中尤为重要。
4.3 模运算中的化简技巧
模运算常借助“先化后算”或“边算边取模”的方式简化。例如，可以把大整数先替换为同余较小的代表元，再进行运算。对于幂、乘积或重复加法，这种处理能够显著降低计算量，也能减少错误。
5 典型定理与性质
同余类是许多数论经典定理的语言基础。许多重要结论都可以通过模视角得到更清楚的表述，并在实际问题中发挥作用。
5.1 整除与同余的关系
整除与同余之间关系紧密。若 \(m\mid(a-b)\)，则 \(a\equiv b\pmod m\)；反之，若 \(a\equiv b\pmod m\)，则 \(m\mid(a-b)\)。因此，同余其实就是“差可被整除”的另一种表达方式。
5.2 中国剩余定理
中国剩余定理研究多个模数同时成立的同余方程组。若这些模数两两互素，则方程组通常有唯一解模它们的乘积。该定理把多个模条件整合为一个整体，在分解问题和构造解法时非常有用。
5.3 欧拉定理
若 \(a\) 与 \(n\) 互素，则 \[ a^{\varphi(n)}\equiv 1\pmod n, \] 其中 \(\varphi(n)\) 为欧拉函数。欧拉定理说明，某些幂在模 \(n\) 下会回到 1，是分析周期和计算高次幂的重要工具。
5.4 费马小定理
当模数是素数 \(p\)，且 \(a\) 不被 \(p\) 整除时，有 \[ a^{p-1}\equiv 1\pmod p. \] 这一定理是欧拉定理在素数模下的特殊情形，形式简洁，应用广泛，尤其常见于模逆元和快速幂问题中。
5.5 威尔逊定理
对于素数 \(p\)，有 \[ (p-1)!\equiv -1\pmod p. \] 威尔逊定理为素数的判定提供了一个经典而精确的等价条件，虽然在计算上不一定高效，但在理论上很有代表性。
5.6 同余方程基础
同余方程是未知数满足某种模条件的方程，例如 \[ ax\equiv b\pmod m. \] 求解这类方程通常需要利用最大公因数、可逆性以及同余类分解等方法。它们是模算术中连接理论与应用的核心内容之一。
6 应用
同余类在多个领域都有直接用途，尤其适合处理周期性、离散结构和重复计算问题。
6.1 数论问题求解
在数论中，同余类常用于研究整除性、素数分布、方程可解性以及余数性质。很多看似复杂的整数问题，换到模意义下后会变得更容易分析。
6.2 计算机算法中的模运算
程序设计中经常需要进行取模运算，例如数组循环访问、哈希映射、时间周期处理等。由于机器整数范围有限，模运算还能帮助控制数值大小，并提高算法效率。
6.3 密码学基础
现代密码体系常借助模运算和同余方程构造加密与解密流程。因为模结构既规则又难以反向求解，适合用作构造安全机制的数学基础。相关方法通常依赖大整数运算和可逆元性质。
6.4 伪随机数与周期性分析
许多伪随机数生成方法都包含取模步骤。通过同余类可以分析数列是否会重复、周期多长，以及分布是否均匀。这在模拟、抽样和随机测试中都很常见。
6.5 编码与校验
在编码理论和数据校验中，模运算常被用于检查信息是否被破坏。例如，利用余数一致性可以设计简单的校验规则，从而快速发现输入或传输中的错误。
7 相关概念
同余类与若干基础概念关系密切，这些概念共同构成了模运算与整除理论的知识框架。
7.1 同余方程
同余方程是以同余关系表示的方程，未知数通常位于模运算环境中。它是同余类在求解问题中的直接体现。
7.2 模运算
模运算指在某个模数下进行加、减、乘以及幂等计算，并在每步或最终结果中保留余数。它是同余类最常见的操作方式。
7.3 余数类环
余数类环是将整数按模 \(n\) 的同余类组成的代数结构，包含加法和乘法运算。它是研究有限环和离散代数的重要例子。
7.4 可逆元与单位群
可逆元是在模运算中具有乘法逆元的元素。所有可逆元在乘法下构成单位群，这一结构在代数和密码学中都有重要地位。
7.5 整除理论
整除理论研究整数之间的倍数关系、最大公因数、最小公倍数及相关性质。同余类与整除理论紧密相连，是其在模意义下的自然延伸。