剩余类（同余类）

一、定义

剩余类，亦称同余类，是一种数学的用语，为数论的基本概念之一。

一个整数被正整数n除后，余数有n种情形：0，1，2，3，…，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。我们把（所有）对模n同余的整数构成的一个集合叫做模n的一个剩余类。

设模为n，则根据余数可将所有的整数分为n类，把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类，记作[a]，即[a]={m|m∈Z,m≡a(mod n)}。把a叫作剩余类[a]的一个代表元。

由带余除法，任一整数必与0，1，…，m-1中的一个模m同余，而(0，1，…m=1彼此模m不同余。因此，模m恰有m个不同的同余类，它们是0，1,⋯，m−1。我们用Z_m表示这m个类的集合。

TIPS：其他相关概念

1.缩同余类定义

如果一个同余类中所有数和n互质（互素），那么这个同余类就是一个缩同余类。

‌缩同余类和同余类的主要区别在于它们与模数的互质关系。‌ 缩同余类中的所有数都与模数互质，而同余类中的数不一定与模数互质。

同余类是指具有相同模数的所有整数的集合，这些整数除以该模数后余数相等。例如，在模5的情况下，同余类‌1表示所有除以5余2的整数，包括2, 7, 12, 17, ...‌23。同余类中的每个元素都可以代表该同余类，称为该同余类的代表数‌2。

缩同余类则是从同余类中进一步筛选出的与模数互质的数组成的集合。例如，在模5的情况下，缩同余类中的数都是与5互质的数，包括1, 2, 3, 4‌1。缩同余类的数量由欧拉函数φ(n)决定，其中φ(n)表示小于或等于n的正整数中与n互质的数的数目‌1。

2.完全剩余系定义

任取n，这n个数0，1，…，n-1称为模n的一个完全剩余系。每个数称为相应类的代表元。最常用的完全剩余系是{0，1，…，n-1}。

完系：m个整数c₁，⋯c_m称为模m的完全剩余系，简称为模m的完系，是指c₁，…， c_m彼此模m不同余。数0，1，…，m-1则称为模m的最小非负完系。

‌剩余类和完全剩余系的区别‌
剩余类是由关于模m同余的数的集合，每一个集合叫做关于模m同余的剩余类。例如，模5的一个剩余类是{0, 5, 10, 15...}。

而完全剩余系是从每个剩余类中各取一个数得到的集合，例如模5的一个完全剩余系是{0, 1, 2, 3, 4}。

3.缩剩余系

模n意义下φ(n)个缩同余类中个取一个代表组成的集合。

缩系：φ(m)个整数r₁，…，T_φ(m)称为模m的缩剩余系，简称为缩系，是指它们彼此模m不同余，且均与m互素。不超过m且与m互素的φ(m)个正整数则叫作模m的最小正缩系。

完全剩余系和缩剩余系关系：

设(a,m)=1，b是任意整数，

若c1，…，cm是模m的完系，则ac1+b，…acm+b也是模m的完系；

若r1，…，rφ(m)是模m的缩系.则ar1，…，arφ(m)也是模m的缩系；

存在x使ax≡b(mod m)成立，所有这样的x形成模m的一个同余类。

4.数论倒数(逆元)

数论倒数是指在模m的情况下，两个数a和b的乘积关于模m余1，即满足条件a * b ≡ 1 (mod m)。这种情况下，我们称a和b互为关于模m的数论倒数。

若(a,m)=1,则存在x使ax≡1(mod m)，我们将这样的x称为a对模m的逆，记作a⁻¹(mod m)或a−1.它们形成模m的一个同余类。

设(a,m)=(b,m)=1，则：

(ab)^⁻¹≡a^⁻¹⋅b^⁻¹(mod m)

a^⁻¹≡b^⁻¹(mod m)的充分必要条件是a≡b(mod m)

如果r₁,⋯,r_φ(m)是模m的任一缩系，则它们的逆r₁⁻¹,⋯,r_φ(m)⁻¹也是模m的一个缩系。

二、性质

模 m 的剩余类具有性质：

1、每一个整数恰包含在某一个类 C_j 里(0≤j≤m-1)；

2、两个整数 x，y属于同一类的充分必要条件是 x≡y(mod m)。

三、其他性质

1‌‌.欧拉函数‌（Euler's totient function），也称为‌φ函数，是‌数论中的一个重要函数。

对于任意正整数n，欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的数目。‌

‌欧拉函数的定义‌：对于任意正整数n，φ(n)表示在1到n之间与n互质的数的数量。

‌欧拉函数的性质‌：欧拉函数的值与n的质因子的指数无关，即如果p是n的一个质因子，那么φ(n) = p * φ(n/p)。此外，φ(n)总是等于n的一个真因数。

欧拉函数: 我们用Zm表示模m的缩同余类组成的集合，其元素个数记作φ(m)，称为欧拉函数。

显然，φ(1)=1,而对m>1,φ(m)即为1，2，…，m-1中与m互素的数的个数。

例如，φ(8) = 4，因为在1到8之间与8互质的数有1、3、5、7。

‌欧拉函数的计算公式‌：欧拉函数可以通过‌质因数分解来计算。

1000以内的质数可以点下面链接查看:

1000以内的质数有哪些?分别是什么?

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

孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。