数论：同余 \(a\equiv b(\bmod m)\)

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

同余是数论中刻画整数“等价关系”的核心工具，将整数按“模m的余数”分类，衍生出剩余系、简化剩余系等概念，最终通过欧拉函数连接到欧拉定理和费马小定理，成为解决整数整除、幂运算、素数判定的关键理论。

同余与剩余系是数论的“语言基础”，其核心逻辑链为：

1. 同余定义整数的等价关系→衍生剩余类→选代表得完全剩余系；

2. 完全剩余系中筛选与模互质的元素→得简化剩余系，其个数为欧拉函数\( \varphi(m) \)；

3. 简化剩余系的乘积性质→推导出欧拉定理→特殊化（模为素数）得费马小定理。

学习的关键在于：

熟练运用同余的运算性质（尤其是除法的限制条件）；

掌握欧拉函数的计算公式与积性；

灵活应用欧拉定理和费马小定理简化大幂模运算、判定素数、求解同余方程。

一、同余的概念

同余本质是“整数除以同一正整数m，余数相同”，是对整数的“模块化分类”，比整除更直观地反映整数间的关联。

1. 同余的定义

设\( m \)为正整数（称为“模”），\( a, b \)为整数，若\( m \mid (a - b) \)（即\( a - b \)是m的倍数），则称a与b模m同余，记为\( a \equiv b \pmod{m} \)；若\( m \nmid (a - b) \)，则称a与b模m不同余，记为\( a \not\equiv b \pmod{m} \)。

关键等价表述

\( a \equiv b \pmod{m} \iff a = b + km \)（\( k \)为整数）；

\( a \equiv b \pmod{m} \iff a \)与\( b \)除以m的余数相同（余数均在\( 0 \leq r < m \)范围内）。

例如：\( 15 \div 7 = 2 \cdots 1 \)，\( 22 \div 7 = 3 \cdots 1 \)，故\( 15 \equiv 22 \pmod{7} \)，且\( 15 - 22 = -7 = (-1) \times 7 \)，满足\( 7 \mid (15 - 22) \)。

2. 同余的性质（核心推导工具）

设\( m \)为正整数，\( a, b, c, d \)为整数，同余的性质与等式性质类似，但需注意“模的一致性”和“除法性质的限制”：

（1）基本性质（等价关系）

自反性：\( a \equiv a \pmod{m} \)（任何整数与自身模m同余）；

对称性：若\( a \equiv b \pmod{m} \)，则\( b \equiv a \pmod{m} \)；

传递性：若\( a \equiv b \pmod{m} \)且\( b \equiv c \pmod{m} \)，则\( a \equiv c \pmod{m} \)。

（这三个性质说明“模m同余”是整数集上的等价关系，可将整数分类为“剩余类”）

（2）运算性质（保持同余的运算）

加法性质：若\( a \equiv b \pmod{m} \)，则\( a + c \equiv b + c \pmod{m} \)；

减法性质：若\( a \equiv b \pmod{m} \)，则\( a - c \equiv b - c \pmod{m} \)；

乘法性质：若\( a \equiv b \pmod{m} \)，则\( a \cdot c \equiv b \cdot c \pmod{m} \)；

倍数性质：若\( a \equiv b \pmod{m} \)，则\( ka \equiv kb \pmod{m} \)（\( k \)为整数）；

幂运算性质：若\( a \equiv b \pmod{m} \)，则\( a^n \equiv b^n \pmod{m} \)（\( n \)为非负整数）；

组合运算性质：若\( a \equiv b \pmod{m} \)且\( c \equiv d \pmod{m} \)，则：

\( a + c \equiv b + d \pmod{m} \)，\( a - c \equiv b - d \pmod{m} \)，\( a \cdot c \equiv b \cdot d \pmod{m} \)。

（3）除法性质（需附加条件，区别于等式）

同余的除法不能直接进行，需满足“除数与模互质”的条件：

性质1：若\( ac \equiv bc \pmod{m} \)且\( \gcd(c, m) = 1 \)，则\( a \equiv b \pmod{m} \)（“消去律”，仅当除数与模互质时成立）；

性质2：若\( ac \equiv bc \pmod{m} \)，则\( a \equiv b \pmod{\frac{m}{\gcd(c, m)}} \)（一般情况，模需除以\( \gcd(c, m) \)）；

性质3：若\( a \equiv b \pmod{m_1} \)且\( a \equiv b \pmod{m_2} \)，则\( a \equiv b \pmod{\text{lcm}(m_1, m_2)} \)（同余于多个模，等价于同余于它们的最小公倍数）；

性质4：若\( a \equiv b \pmod{m} \)，则\( \gcd(a, m) = \gcd(b, m) \)（同余的数与模的最大公约数相等）。

二、剩余类和完全剩余系

通过“模m同余”的等价关系，可将整数集划分为“剩余类”，从每个剩余类中选一个代表组成“完全剩余系”，是简化整数问题的重要工具。

1. 剩余类（同余类）

设\( m \)为正整数，对任意整数\( r \)（\( 0 \leq r < m \)），称所有满足“\( x \equiv r \pmod{m} \)”的整数\( x \)组成的集合为模m的一个剩余类，记为\( [r]_m \)（或简记为\( [r] \)），即：

\( [r]_m = \{ x \in \mathbb{Z} \mid x = km + r, k \in \mathbb{Z} \} \)

核心性质

剩余类的个数：模m共有\( m \)个不同的剩余类，即\( [0]_m, [1]_m, \dots, [m-1]_m \)（因余数r的取值仅0到m-1）；

剩余类的不交性：任意两个不同的剩余类无公共元素（若\( [r]_m \cap [s]_m \neq \emptyset \)，则\( r \equiv s \pmod{m} \)，故\( [r]_m = [s]_m \)）；

剩余类的覆盖性：所有剩余类的并集为全体整数（任何整数除以m必有唯一余数r，故属于\( [r]_m \)）。

例如：模3的剩余类为\( [0]_3 = \{ \dots, -6, -3, 0, 3, 6, \dots \} \)，\( [1]_3 = \{ \dots, -5, -2, 1, 4, 7, \dots \} \)，\( [2]_3 = \{ \dots, -4, -1, 2, 5, 8, \dots \} \)，共3个，不交且覆盖全体整数。

2. 完全剩余系

设\( m \)为正整数，从模m的\( m \)个不同剩余类中各选一个代表元素组成的集合，称为模m的一个完全剩余系（简称“完系”）。

常见的完全剩余系

最小非负完全剩余系：\( \{ 0, 1, 2, \dots, m-1 \} \)（最常用，余数直接作为代表）；

最小正完全剩余系：\( \{ 1, 2, 3, \dots, m \} \)；

对称完全剩余系（m为奇数）：\( \left\{ -\frac{m-1}{2}, \dots, -1, 0, 1, \dots, \frac{m-1}{2} \right\} \)（如模5的对称完系为\( \{ -2, -1, 0, 1, 2 \} \)）。

完全剩余系的性质（判定与构造）

性质1（判定定理）：若\( a_1, a_2, \dots, a_m \)是m个整数，且任意两个数模m不同余，则\( \{ a_1, a_2, \dots, a_m \} \)是模m的完系；

性质2（线性构造）：若\( \{ a_1, a_2, \dots, a_m \} \)是模m的完系，且\( \gcd(k, m) = 1 \)（k与m互质），b为整数，则\( \{ k a_1 + b, k a_2 + b, \dots, k a_m + b \} \)也是模m的完系（“线性变换保完系”，k保证“不同余性”，b保证“覆盖所有剩余类”）；

性质3（组合构造）：若\( \{ a_1, \dots, a_m \} \)是模m的完系，\( \{ b_1, \dots, b_n \} \)是模n的完系，且\( \gcd(m, n) = 1 \)，则\( \{ n a_i + m b_j \mid 1 \leq i \leq m, 1 \leq j \leq n \} \)是模\( mn \)的完系（中国剩余定理的基础）；

性质4（同余不变性）：若\( f(x) \)是线性函数（\( f(x) = kx + b \)，\( \gcd(k, m) = 1 \)），则\( f(x) \)将模m的完系映射为模m的完系。

三、简化剩余系与欧拉函数

在完全剩余系中，仅保留“与模m互质”的元素，得到“简化剩余系”，而欧拉函数则是简化剩余系的“元素个数”，是连接剩余系与数论定理的核心函数。

1. 简化剩余系（缩剩余系）

设\( m \)为正整数，从模m的所有剩余类中，仅选取与m互质的剩余类（即剩余类\( [r]_m \)满足\( \gcd(r, m) = 1 \)），再从每个这样的剩余类中选一个代表元素组成的集合，称为模m的简化剩余系（简称“缩系”）。

简化剩余系的元素个数：等于“1到m中与m互质的整数个数”，即欧拉函数\( \varphi(m) \)（见下文）；

常见的简化剩余系：模m的最小正简化剩余系为\( \{ r \mid 1 \leq r \leq m, \gcd(r, m) = 1 \} \)（如模6的缩系为\( \{ 1, 5 \} \)，因\( \gcd(1,6)=1 \)，\( \gcd(5,6)=1 \)，\( \varphi(6)=2 \)）。

简化剩余系的性质

性质1（判定定理）：若\( a_1, a_2, \dots, a_{\varphi(m)} \)是\( \varphi(m) \)个整数，满足：① 每个\( a_i \)与m互质；② 任意两个\( a_i \)模m不同余，则\( \{ a_1, \dots, a_{\varphi(m)} \} \)是模m的缩系；

性质2（线性构造）：若\( \{ a_1, \dots, a_{\varphi(m)} \} \)是模m的缩系，且\( \gcd(k, m) = 1 \)，则\( \{ k a_1, k a_2, \dots, k a_{\varphi(m)} \} \)也是模m的缩系（“互质的线性变换保缩系”，k与m互质保证\( k a_i \)与m互质，且不同余）；

性质3（乘积性质）：若\( \{ a_1, \dots, a_{\varphi(m)} \} \)是模m的缩系，则\( \prod_{i=1}^{\varphi(m)} a_i \equiv \pm 1 \pmod{m} \)（威尔逊定理的推广，当m=素数p时，缩系为\( \{1,2,...,p-1\} \)，乘积为\( (p-1)! \equiv -1 \pmod{p} \)，即威尔逊定理）；

性质4（组合构造）：若\( \gcd(m, n) = 1 \)，\( \{ a_1, \dots, a_{\varphi(m)} \} \)是模m的缩系，\( \{ b_1, \dots, b_{\varphi(n)} \} \)是模n的缩系，则\( \{ n a_i + m b_j \mid 1 \leq i \leq \varphi(m), 1 \leq j \leq \varphi(n) \} \)是模\( mn \)的缩系（由此可推欧拉函数的积性）。

2. 欧拉函数\( \varphi(m) \)

设\( m \)为正整数，欧拉函数\( \varphi(m) \) 表示“1到m中与m互质的正整数的个数”，即：\( \varphi(m) = \sum_{\substack{1 \leq r \leq m \\ \gcd(r, m) = 1}} 1 \)

欧拉函数的计算公式（核心，基于算术基本定理）

设\( m \)的标准分解式为\( m = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n} \)（\( p_1 < p_2 < \dots < p_n \)为素数，\( k_1, \dots, k_n \)为正整数），则欧拉函数的计算公式为：

\( \varphi(m) = m \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \dots \cdot \left(1 - \frac{1}{p_n}\right) \)

推导思路（容斥原理）

要计算1到m中与m互质的数，需排除“被\( p_1, p_2, \dots, p_n \)整除的数”；

被\( p_i \)整除的数有\( \frac{m}{p_i} \)个，被\( p_i p_j \)整除的数有\( \frac{m}{p_i p_j} \)个，…，被\( p_1 p_2 \dots p_n \)整除的数有\( \frac{m}{p_1 p_2 \dots p_n} \)个；

由容斥原理，1到m中与m互质的数的个数为：

\( \varphi(m) = m - \sum \frac{m}{p_i} + \sum \frac{m}{p_i p_j} - \sum \frac{m}{p_i p_j p_k} + \dots + (-1)^n \frac{m}{p_1 p_2 \dots p_n} \)

因式分解后即得上述公式。

欧拉函数的性质

性质1（特殊值）：

若m=1，则\( \varphi(1) = 1 \)（1与自身互质，仅1个数）；

若p为素数，则\( \varphi(p) = p - 1 \)（1到p中仅p不与自身互质，故排除1个）；

若p为素数，k为正整数，则\( \varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1) \)（1到\( p^k \)中被p整除的数有\( p^{k-1} \)个，故排除后剩余\( p^k - p^{k-1} \)个）；

性质2（积性）：若\( \gcd(m, n) = 1 \)，则\( \varphi(mn) = \varphi(m) \cdot \varphi(n) \)（由简化剩余系的组合构造性质推导，是欧拉函数的核心性质）；

性质3（倍数和）：对任意正整数m，有\( \sum_{d \mid m} \varphi(d) = m \)（所有d是m的正约数，将1到m按“与m的最大公约数为d”分类，每类个数为\( \varphi\left( \frac{m}{d} \right) \)，求和得m）；

性质4（单调性）：欧拉函数非单调，如\( \varphi(5) = 4 \)，\( \varphi(6) = 2 \)，\( \varphi(7) = 6 \)（\( 5 < 6 < 7 \)，但\( 4 > 2 < 6 \)）；

性质5（奇偶性）：

若m > 2，则\( \varphi(m) \)为偶数（模m的缩系中，r与m - r成对出现，且r ≠ m - r，故个数为偶数）；

仅当m=1或m=2时，\( \varphi(m) = 1 \)（奇数）。

四、欧拉定理和费马小定理（核心应用定理）

欧拉定理是简化剩余系性质的直接推论，费马小定理是欧拉定理在“模为素数”时的特殊情况，两者是解决“大整数幂模运算”的核心工具。

1. 欧拉定理

设\( m \)为正整数，若\( \gcd(a, m) = 1 \)（a与m互质），则：\( a^{\varphi(m)} \equiv 1 \pmod{m} \)

证明思路（利用简化剩余系的乘积性质）

设\( \{ r_1, r_2, \dots, r_{\varphi(m)} \} \)是模m的简化剩余系；

因\( \gcd(a, m) = 1 \)，由简化剩余系的线性构造性质，\( \{ a r_1, a r_2, \dots, a r_{\varphi(m)} \} \)也是模m的简化剩余系；

两个缩系的元素模m两两不同余，故它们的乘积模m相等：

\( (a r_1)(a r_2) \dots (a r_{\varphi(m)}) \equiv r_1 r_2 \dots r_{\varphi(m)} \pmod{m} \)

提取左边的\( a^{\varphi(m)} \)，得\( a^{\varphi(m)} \cdot \prod_{i=1}^{\varphi(m)} r_i \equiv \prod_{i=1}^{\varphi(m)} r_i \pmod{m} \)；

因每个\( r_i \)与m互质，故\( \prod_{i=1}^{\varphi(m)} r_i \)与m互质，由同余的消去律，两边消去乘积得\( a^{\varphi(m)} \equiv 1 \pmod{m} \)。

2. 费马小定理

定理内容（欧拉定理的特殊情况）

设\( p \)为素数，对任意整数a，有：\( a^p \equiv a \pmod{p} \)

若\( \gcd(a, p) = 1 \)（a不被p整除），则定理可简化为：\( a^{p - 1} \equiv 1 \pmod{p} \)

证明思路

当\( \gcd(a, p) = 1 \)时，因p是素数，\( \varphi(p) = p - 1 \)，代入欧拉定理得\( a^{p - 1} \equiv 1 \pmod{p} \)，两边乘a得\( a^p \equiv a \pmod{p} \)；

当\( p \mid a \)时，a ≡ 0 mod p，故\( a^p \equiv 0^p = 0 \equiv a \pmod{p} \)；

综上，对任意整数a，\( a^p \equiv a \pmod{p} \)成立。

3. 定理的核心应用

简化大幂模运算：将指数对\( \varphi(m) \)（或\( p - 1 \)）取余，降低指数规模（如计算\( 2^{1000} \mod 7 \)，因\( \varphi(7)=6 \)，\( 1000 = 6×166 + 4 \)，故\( 2^{1000} \equiv 2^4 = 16 \equiv 2 \pmod{7} \)）；

素数判定（必要条件）：若存在a使得\( a^{n - 1} \not\equiv 1 \pmod{n} \)，则n是合数（费马小定理的逆否命题，注意：逆命题不成立，存在“卡迈克尔数”如561，满足对所有\( \gcd(a, 561)=1 \)的a，\( a^{560} \equiv 1 \pmod{561} \)，但561=3×11×17是合数）；

求解同余方程：如求解\( 3x \equiv 2 \pmod{7} \)，因\( \gcd(3,7)=1 \)，3的逆元为\( 3^{5} \equiv 5 \pmod{7} \)（由费马小定理，\( 3^6 \equiv 1 \)，故逆元为\( 3^5 \)），故x ≡ 2×5 = 10 ≡ 3 mod 7。

（一）同余的概念与性质（例题1-10）

例题1：判断下列同余是否成立（1）\( 123 \equiv 45 \pmod{13} \)；（2）\( -7 \equiv 5 \pmod{6} \)

解：同余判定核心是“\( m \mid (a - b) \)”：

（1）计算\( 123 - 45 = 78 \)，\( 78 \div 13 = 6 \)（无余数），故\( 123 \equiv 45 \pmod{13} \)成立；

（2）计算\( -7 - 5 = -12 \)，\( -12 \div 6 = -2 \)（无余数），故\( -7 \equiv 5 \pmod{6} \)成立。

例题2：求\( 2025 \mod 17 \)的值

解：用“逐步降幂”简化计算：

因\( 17×119 = 2023 \)，故\( 2025 = 17×119 + 2 \)，余数为2，即\( 2025 \mod 17 = 2 \)；

或用同余运算：\( 2025 - 17×119 = 2025 - 2023 = 2 \)，故\( 2025 \equiv 2 \pmod{17} \)。

例题3：已知\( a \equiv 3 \pmod{5} \)，\( b \equiv 4 \pmod{5} \)，求\( 2a + 3b \pmod{5} \)

解：利用同余的线性运算性质：

由\( a \equiv 3 \pmod{5} \)，得\( 2a \equiv 2×3 = 6 \equiv 1 \pmod{5} \)；

由\( b \equiv 4 \pmod{5} \)，得\( 3b \equiv 3×4 = 12 \equiv 2 \pmod{5} \)；

相加得\( 2a + 3b \equiv 1 + 2 = 3 \pmod{5} \)。

例题4：已知\( 3x \equiv 6 \pmod{9} \)，求解x的同余解

解：利用同余的除法性质（性质2）：

原方程即\( 3x \equiv 3×2 \pmod{9} \)，\( \gcd(3, 9) = 3 \)，故模需除以3，得\( x \equiv 2 \pmod{3} \)；

即x的所有解为\( x = 3k + 2 \)（k为整数），验证：当k=0时，x=2，3×2=6≡6 mod9；k=1时，x=5，3×5=15≡6 mod9，均成立。

例题5：证明对任意整数n，\( n^3 \equiv n \pmod{6} \)

解：需证明\( 6 \mid (n^3 - n) \)，即\( 2 \mid (n^3 - n) \)且\( 3 \mid (n^3 - n) \)（因\( 6=2×3 \)，且\( \gcd(2,3)=1 \)）：

模2：n为偶数时，n≡0 mod2，\( n^3≡0^3=0≡n mod2 \)；n为奇数时，n≡1 mod2，\( n^3≡1^3=1≡n mod2 \)，故\( n^3≡n mod2 \)；

模3：由费马小定理，\( n^3≡n mod3 \)（3是素数）；

由同余的性质3，\( n^3≡n mod \text{lcm}(2,3)=6 \)，即\( n^3 \equiv n \pmod{6} \)。

例题6：求\( 11^{2024} \mod 8 \)的值

解：先简化底数，再用幂运算性质：

底数简化：\( 11 \equiv 3 \pmod{8} \)，故\( 11^{2024} \equiv 3^{2024} \pmod{8} \)；

找指数周期：\( 3^1=3≡3 mod8 \)，\( 3^2=9≡1 mod8 \)，周期为2；

指数取余：\( 2024 = 2×1012 + 0 \)，故\( 3^{2024} \equiv (3^2)^{1012} \equiv 1^{1012} = 1 \pmod{8} \)；

即\( 11^{2024} \mod8 = 1 \)。

例题7：已知\( x \equiv 2 \pmod{5} \)且\( x \equiv 3 \pmod{7} \)，求解x的最小正整数解

解：用“代入法”解同余方程组：

由\( x \equiv 2 \pmod{5} \)，设\( x = 5k + 2 \)（k为整数），代入第二个同余式：

\( 5k + 2 \equiv 3 \pmod{7} \implies 5k \equiv 1 \pmod{7} \)；

找5的逆元（即满足\( 5m \equiv 1 mod7 \)的m）：\( 5×3=15≡1 mod7 \)，故逆元为3；

两边乘3得\( k \equiv 1×3 = 3 \pmod{7} \)，即\( k = 7t + 3 \)（t为整数）；

代入x的表达式：\( x = 5(7t + 3) + 2 = 35t + 17 \)；

当t=0时，x=17（最小正整数解），验证：17≡2 mod5，17≡3 mod7，成立。

例题8：证明对任意整数a，\( a^2 \equiv 0 \)或\( 1 \pmod{4} \)

解：按a的奇偶性分类：

若a为偶数，设\( a = 2k \)，则\( a^2 = 4k^2 \equiv 0 \pmod{4} \)；

若a为奇数，设\( a = 2k + 1 \)，则\( a^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1 \equiv 1 \pmod{4} \)；

综上，\( a^2 \equiv 0 \)或\( 1 \pmod{4} \)（此性质可用于判断“某数是否为平方数”，如2023≡3 mod4，故2023不是平方数）。

例题9：已知\( a \equiv b \pmod{m} \)，证明\( \gcd(a, m) = \gcd(b, m) \)

解：由同余定义，\( a = b + km \)（k为整数）；

设\( d_1 = \gcd(a, m) \)，则\( d_1 \mid a \)且\( d_1 \mid m \)，故\( d_1 \mid (a - km) = b \)，即\( d_1 \)是b和m的公约数；

设\( d_2 = \gcd(b, m) \)，则\( d_2 \mid b \)且\( d_2 \mid m \)，故\( d_2 \mid (b + km) = a \)，即\( d_2 \)是a和m的公约数；

由最大公约数的定义，\( d_1 \leq d_2 \)且\( d_2 \leq d_1 \)，故\( d_1 = d_2 \)，即\( \gcd(a, m) = \gcd(b, m) \)。

例题10：求满足\( 2x \equiv 5 \pmod{7} \)的x的最小正整数解

解：利用同余的除法性质（需找2的逆元）：

因\( \gcd(2,7)=1 \)，逆元存在，即找m使得\( 2m \equiv 1 mod7 \)；

试算得\( m=4 \)（2×4=8≡1 mod7），故逆元为4；

原方程两边乘4：\( x \equiv 5×4 = 20 \equiv 6 \pmod{7} \)；

最小正整数解为6，验证：2×6=12≡5 mod7，成立。

（二）剩余类和完全剩余系（例题11-20）

例题11：写出模5的所有剩余类，并指出每个剩余类中的3个元素

解：模5有5个剩余类，分别为：

\( [0]_5 = \{ \dots, -10, -5, 0, 5, 10, \dots \} \)（元素：-5, 0, 5）；

\( [1]_5 = \{ \dots, -9, -4, 1, 6, 11, \dots \} \)（元素：-4, 1, 6）；

\( [2]_5 = \{ \dots, -8, -3, 2, 7, 12, \dots \} \)（元素：-3, 2, 7）；

\( [3]_5 = \{ \dots, -7, -2, 3, 8, 13, \dots \} \)（元素：-2, 3, 8）；

\( [4]_5 = \{ \dots, -6, -1, 4, 9, 14, \dots \} \)（元素：-1, 4, 9）。

例题12：判断集合\( \{ 2, 5, 8, 11, 14 \} \)是否为模5的完全剩余系

解：用完全剩余系的判定定理（5个元素，且两两模5不同余）：

计算每个元素模5的余数：2 mod5=2，5 mod5=0，8 mod5=3，11 mod5=1，14 mod5=4；

余数分别为0,1,2,3,4（全不同，覆盖所有余数），故该集合是模5的完全剩余系。

例题13：已知\( \{ 0, 1, 2, 3, 4 \} \)是模5的完系，构造一个新的模5完系（用线性变换\( 3x + 2 \)）

解：利用完全剩余系的线性构造性质（\( \gcd(3,5)=1 \)，满足条件）：

对每个元素x，计算\( 3x + 2 \)：

x=0：3×0+2=2；x=1：3×1+2=5；x=2：3×2+2=8；x=3：3×3+2=11；x=4：3×4+2=14；

新集合为\( \{2,5,8,11,14\} \)，验证：各元素模5余数为2,0,3,1,4（全不同），是模5的完系。

例题14：证明：若\( \{ a_1, a_2, a_3 \} \)是模3的完系，则\( \{ a_1 + 2, a_2 + 2, a_3 + 2 \} \)也是模3的完系

解：需证明“3个元素，且两两模3不同余”：

元素个数：3个，满足完系的个数要求；

两两不同余：假设\( a_i + 2 \equiv a_j + 2 \pmod{3} \)，则\( a_i \equiv a_j \pmod{3} \)；

因\( \{ a_1, a_2, a_3 \} \)是完系，故\( a_i = a_j \)（i=j），即任意两个元素模3不同余；

综上，\( \{ a_1 + 2, a_2 + 2, a_3 + 2 \} \)是模3的完系。

例题15：求模7的最小正完全剩余系和对称完全剩余系

解：

最小正完全剩余系：1到7中各选一个代表（余数1到7），即\( \{1,2,3,4,5,6,7\} \)（或简化为\( \{1,2,3,4,5,6,0\} \)，但最小正系通常取正整数）；

对称完全剩余系：模7为奇数，取“-3到3”（中间为0），即\( \{-3,-2,-1,0,1,2,3\} \)，验证：各元素模7余数为4,5,6,0,1,2,3（覆盖所有余数），且对称。

例题16：已知\( \{ a, b, c, d \} \)是模4的完系，证明\( a + b + c + d \equiv 0 \pmod{2} \)

解：模4的完系中，元素模2的余数必为“0,0,1,1”（因模4的余数0和2对应模2的0，余数1和3对应模2的1）：

设完系中模2为0的元素和为S，模2为1的元素和为T，则S≡0+0=0 mod2，T≡1+1=2≡0 mod2；

总 sum = S + T ≡0 + 0 = 0 mod2，故\( a + b + c + d \equiv 0 \pmod{2} \)；

实例验证：取完系\( \{0,1,2,3\} \)，sum=0+1+2+3=6≡0 mod2，成立。

例题17：构造模6的一个完全剩余系，要求所有元素均为奇数

解：模6的余数为0,1,2,3,4,5，需找每个余数对应的奇数：

余数0：找奇数x≡0 mod6，无（6k为偶数），故不存在“全为奇数的模6完系”；

结论：因模6的完系需包含余数0的元素（必为偶数），故无法构造全为奇数的模6完系。

例题18：已知\( \gcd(k, 7) = 1 \)，证明\( \{ k, 2k, 3k, 4k, 5k, 6k \} \)是模7的完系

解：模7的完系需6个元素（\( \varphi(7)=6 \)，此处实际是缩系，但也是完系的一部分，需证明覆盖所有余数）：

元素个数：6个，满足完系的个数要求（模7的完系有7个元素，此处题目可能笔误，应为“缩系”，但按完系思路证明：若添加0，则\( \{0, k, 2k, ..., 6k\} \)是完系）；

两两不同余：假设\( ik \equiv jk \pmod{7} \)（i≠j），因\( \gcd(k,7)=1 \)，消去k得\( i \equiv j \pmod{7} \)，故i=j（1≤i,j≤6），即两两不同余；

覆盖余数：6个不同余数，加上0后覆盖0-6，故\( \{0, k, 2k, ..., 6k\} \)是模7的完系，原题中集合是缩系，也是完系的子集。

例题19：求模5的完系中，所有元素的和模5的值

解：取模5的最小非负完系\( \{0,1,2,3,4\} \)，和为0+1+2+3+4=10；

10 mod5=0，故所有元素的和模5=0；

推广：对任意模m，完系的和为\( 0+1+2+...+(m-1) = \frac{m(m-1)}{2} \)，当m=5时，和为10≡0 mod5，成立。

例题20：已知\( \{ a_1, a_2, ..., a_m \} \)是模m的完系，证明\( \sum_{i=1}^m a_i \equiv 0 \pmod{m} \)（m为奇数）

解：取对称完系\( \left\{ -\frac{m-1}{2}, ..., -1, 0, 1, ..., \frac{m-1}{2} \right\} \)，和为0（正负抵消）；

因任意完系与对称完系模m同余（完系的和模m不变），故\( \sum_{i=1}^m a_i \equiv 0 \pmod{m} \)；

实例：m=5（奇数），完系和为10≡0 mod5；m=7，完系和为21≡0 mod7，成立。

（三）简化剩余系与欧拉函数（例题21-30）

例题21：计算\( \varphi(12) \)和\( \varphi(17) \)的值

解：用欧拉函数公式：

\( 12 = 2^2 × 3^1 \)，故\( \varphi(12) = 12 × (1 - \frac{1}{2}) × (1 - \frac{1}{3}) = 12 × \frac{1}{2} × \frac{2}{3} = 4 \)；

验证：1到12中与12互质的数为1,5,7,11（共4个），正确；

17是素数，故\( \varphi(17) = 17 - 1 = 16 \)；

验证：1到17中与17互质的数为1-16（共16个），正确。

例题22：计算\( \varphi(72) \)的值（72的标准分解式为\( 2^3 × 3^2 \)）

解：代入欧拉函数公式：

\( \varphi(72) = 72 × (1 - \frac{1}{2}) × (1 - \frac{1}{3}) = 72 × \frac{1}{2} × \frac{2}{3} = 72 × \frac{1}{3} = 24 \)；

验证：1到72中与72互质的数需满足“不被2和3整除”，个数为72 - 36（被2整除） - 24（被3整除） + 12（被6整除）= 24，正确。

例题23：已知\( \gcd(8, 15) = 1 \)，证明\( \varphi(8×15) = \varphi(8)×\varphi(15) \)

解：计算两边值：

左边：\( 8×15=120 \)，\( 120=2^3×3×5 \)，故\( \varphi(120)=120×(1-\frac{1}{2})×(1-\frac{1}{3})×(1-\frac{1}{5})=120×\frac{1}{2}×\frac{2}{3}×\frac{4}{5}=32 \)；

右边：\( \varphi(8)=4 \)（8=2³，\( \varphi(8)=8-4=4 \)），\( \varphi(15)=15×(1-\frac{1}{3})×(1-\frac{1}{5})=8 \)，故\( \varphi(8)×\varphi(15)=4×8=32 \)；

左边=右边，故等式成立（验证欧拉函数的积性）。

例题24：写出模10的简化剩余系，并计算其元素个数（即\( \varphi(10) \)）

解：模10的剩余类中，与10互质的剩余类为\( [1]_{10}, [3]_{10}, [7]_{10}, [9]_{10} \)（因\( \gcd(1,10)=1 \)，\( \gcd(3,10)=1 \)，\( \gcd(7,10)=1 \)，\( \gcd(9,10)=1 \)）；

从每个剩余类选代表，得简化剩余系：\( \{1,3,7,9\} \)；

元素个数为4，即\( \varphi(10)=4 \)（用公式验证：10=2×5，\( \varphi(10)=10×(1-\frac{1}{2})×(1-\frac{1}{5})=4 \)，正确）。

例题25：已知\( \{1,3,7,9\} \)是模10的缩系，用线性变换\( 3x \)构造新的模10缩系

解：利用简化剩余系的线性构造性质（\( \gcd(3,10)=1 \)，满足条件）：

对每个元素x，计算\( 3x \)：

x=1：3×1=3；x=3：3×3=9；x=7：3×7=21；x=9：3×9=27；

新集合为\( \{3,9,21,27\} \)，简化模10：3 mod10=3，9 mod10=9，21 mod10=1，27 mod10=7；

简化后为\( \{1,3,7,9\} \)（与原缩系相同，因模10的缩系元素个数有限，线性变换可能映射为自身），验证：各元素与10互质，且两两不同余，是模10的缩系。

例题26：证明：若p为素数，k为正整数，则\( \varphi(p^k) = p^k - p^{k-1} \)

解：用欧拉函数的定义（1到\( p^k \)中与\( p^k \)互质的数的个数）：

1到\( p^k \)中，与\( p^k \)不互质的数必被p整除（因p是素数）；

被p整除的数为\( p, 2p, 3p, ..., p^{k-1}×p = p^k \)，共\( p^{k-1} \)个；

故与\( p^k \)互质的数的个数为\( p^k - p^{k-1} \)，即\( \varphi(p^k) = p^k - p^{k-1} \)；

实例：p=2，k=3，\( \varphi(8)=8-4=4 \)，正确。

例题27：计算\( \sum_{d \mid 12} \varphi(d) \)的值（d为12的正约数）

解：先找12的所有正约数：1,2,3,4,6,12；

计算每个约数的欧拉函数：

\( \varphi(1)=1 \)，\( \varphi(2)=1 \)，\( \varphi(3)=2 \)，\( \varphi(4)=2 \)，\( \varphi(6)=2 \)，\( \varphi(12)=4 \)；

求和：1 + 1 + 2 + 2 + 2 + 4 = 12，即\( \sum_{d \mid 12} \varphi(d) = 12 \)（验证欧拉函数的倍数和性质：\( \sum_{d \mid m} \varphi(d) = m \)，此处m=12，正确）。

例题28：证明：若m > 2，则\( \varphi(m) \)为偶数

解：按m的奇偶性分类：

若m为偶数且m > 2，则m必含素因子2（至少2²），设m=2^k × t（k≥2，t为奇数）；

由欧拉函数的积性，\( \varphi(m) = \varphi(2^k)×\varphi(t) = (2^k - 2^{k-1})×\varphi(t) = 2^{k-1}(2 - 1)×\varphi(t) = 2^{k-1}\varphi(t) \)；

因k≥2，故\( 2^{k-1} \geq 2 \)，\( \varphi(m) \)为偶数；

若m为奇数且m > 2，则m必含奇素因子p，设m=p^k × t（p为奇素数，k≥1，t为奇数）；

\( \varphi(m) = \varphi(p^k)×\varphi(t) = p^{k-1}(p - 1)×\varphi(t) \)；

因p是奇素数，p - 1为偶数，故\( \varphi(m) \)为偶数；

综上，m > 2时，\( \varphi(m) \)为偶数（实例：\( \varphi(9)=6 \)，\( \varphi(15)=8 \)，均为偶数）。

例题29：已知\( \varphi(m) = 8 \)，求所有正整数m

解：设m的标准分解式为\( m = 2^a × p_1^{b_1} × p_2^{b_2} × ... \)，分情况讨论：

情况1：m仅含素因子2（a≥1）：\( \varphi(2^a) = 2^a - 2^{a-1} = 2^{a-1} = 8 \implies a-1=3 \implies a=4 \)，故m=2^4=16；

情况2：m含素因子2和一个奇素数p（a≥0，b≥1）：

a=0（m为奇数）：\( \varphi(p^b) = p^{b-1}(p - 1) = 8 \)；

8的因数分解：8=8×1=4×2=2×4=1×8；

若p^{b-1}=1，p-1=8，则p=9（非素数，舍去）；

若p^{b-1}=2，p-1=4，则p=5（素数），b-1=1（2不是素数的幂，舍去）；

若p^{b-1}=4，p-1=2，则p=3（素数），b-1=2（4=3²不成立，舍去）；

若p^{b-1}=8，p-1=1，则p=2（偶素数，舍去）；

a=1（m=2×p^b）：\( \varphi(2×p^b) = \varphi(2)×\varphi(p^b) = 1×p^{b-1}(p - 1) = 8 \)；

同a=0，得p=5，b-1=1（p-1=4，p^{b-1}=2，舍去）；p=3，b-1=2（舍去）；p=17，p-1=16（舍去）；

a=2（m=4×p^b）：\( \varphi(4×p^b) = \varphi(4)×\varphi(p^b) = 2×p^{b-1}(p - 1) = 8 \implies p^{b-1}(p - 1)=4 \)；

4=4×1=2×2=1×4；

p^{b-1}=1，p-1=4 → p=5，b=1 → m=4×5=20；

p^{b-1}=2，p-1=2 → p=3，b=2 → m=4×9=36（\( \varphi(36)=12≠8 \)，舍去）；

p^{b-1}=4，p-1=1 → p=2，舍去；

a=3（m=8×p^b）：\( \varphi(8×p^b) = 4×p^{b-1}(p - 1)=8 \implies p^{b-1}(p - 1)=2 \)；

2=2×1=1×2；

p^{b-1}=1，p-1=2 → p=3，b=1 → m=8×3=24；

p^{b-1}=2，p-1=1 → p=2，舍去；

情况3：m含两个不同的奇素数p和q（a≥0）：\( \varphi(p×q) = (p-1)(q-1)=8 \)；

8=8×1=4×2，故：

p-1=8，q-1=1 → p=9（舍去），q=2；

p-1=4，q-1=2 → p=5，q=3 → m=5×3=15（\( \varphi(15)=8 \)，正确）；

若a=1，m=2×3×5=30（\( \varphi(30)=8 \)，正确）；

综上，m的所有解为：15, 16, 20, 24, 30。

例题30：证明模m的简化剩余系中，元素的乘积模m≡1或-1（威尔逊定理推广）

解：设缩系为\( \{ r_1, r_2, ..., r_{\varphi(m)} \} \)，对每个r_i，存在唯一的r_j使得\( r_i r_j ≡ 1 \pmod{m} \)（逆元存在）：

若r_i = r_j（即\( r_i^2 ≡ 1 \pmod{m} \)），则r_i≡1或r_i≡m-1 modm（仅当m>2时存在）；

若r_i ≠ r_j，则r_i和r_j成对出现，乘积≡1 modm；

当m=2时，缩系为\( \{1\} \)，乘积=1≡1 mod2；

当m=3时，缩系为\( \{1,2\} \)，乘积=2≡-1 mod3；

当m=4时，缩系为\( \{1,3\} \)，乘积=3≡-1 mod4；

当m=5时，缩系为\( \{1,2,3,4\} \)，乘积=24≡-1 mod5；

当m=6时，缩系为\( \{1,5\} \)，乘积=5≡-1 mod6；

当m=8时，缩系为\( \{1,3,5,7\} \)，乘积=105≡1 mod8；

综上，缩系元素的乘积模m≡1或-1，成立。

（四）欧拉定理和费马小定理（例题31-40）

例题31：用欧拉定理计算\( 5^{2024} \mod 7 \)的值

解：步骤：

1. 验证条件：\( \gcd(5,7)=1 \)，7是素数，\( \varphi(7)=6 \)；

2. 应用欧拉定理：\( 5^6 ≡ 1 \pmod{7} \)；

3. 指数取余：\( 2024 = 6×337 + 2 \)，故\( 5^{2024} = 5^{6×337 + 2} = (5^6)^{337} × 5^2 ≡ 1^{337} × 25 ≡ 25 mod7 \)；

4. 简化结果：25 mod7=4，故\( 5^{2024} mod7=4 \)。

例题32：用费马小定理计算\( 3^{100} mod 11 \)的值

解：步骤：

1. 验证条件：11是素数，\( \gcd(3,11)=1 \)，满足费马小定理；

2. 应用费马小定理：\( 3^{10} ≡ 1 \pmod{11} \)；

3. 指数取余：\( 100 = 10×10 + 0 \)，故\( 3^{100} = (3^{10})^{10} ≡ 1^{10} = 1 \pmod{11} \)；

即\( 3^{100} mod11=1 \)。

例题33：证明对任意整数a，\( a^{13} ≡ a \pmod{3×5×7} \)

解：需证明\( a^{13} ≡ a mod3 \)、\( a^{13} ≡ a mod5 \)、\( a^{13} ≡ a mod7 \)（因3,5,7两两互质，lcm=105）：

模3：3是素数，由费马小定理，\( a^3 ≡ a mod3 \)，故\( a^{13} = a^{3×4 + 1} = (a^3)^4 × a ≡ a^4 × a = a^5 = a^{3×1 + 2} ≡ a×a^2 = a^3 ≡ a mod3 \)；

模5：5是素数，\( a^5 ≡ a mod5 \)，故\( a^{13} = a^{5×2 + 3} = (a^5)^2 × a^3 ≡ a^2 × a^3 = a^5 ≡ a mod5 \)；

模7：7是素数，\( a^7 ≡ a mod7 \)，故\( a^{13} = a^{7×1 + 6} = a^7 × a^6 ≡ a×1 = a mod7 \)（由费马小定理，\( a^6 ≡1 mod7 \)）；

由同余的性质3，\( a^{13} ≡ a mod105 \)，即\( a^{13} ≡ a \pmod{3×5×7} \)。

例题34：用欧拉定理求\( 7^{2023} mod 15 \)的值

解：步骤：

1. 计算\( \varphi(15) \)：15=3×5，\( \varphi(15)=\varphi(3)×\varphi(5)=2×4=8 \)；

2. 验证条件：\( \gcd(7,15)=1 \)，应用欧拉定理：\( 7^8 ≡1 mod15 \)；

3. 指数取余：\( 2023 = 8×252 + 7 \)，故\( 7^{2023} = 7^{8×252 + 7} = (7^8)^{252} ×7^7 ≡1^{252} ×7^7 mod15 \)；

4. 计算\( 7^7 mod15 \)：\( 7^1=7 mod15 \)，\( 7^2=49≡4 mod15 \)，\( 7^4=(7^2)^2=16≡1 mod15 \)，\( 7^7=7^4×7^2×7^1=1×4×7=28≡13 mod15 \)；

即\( 7^{2023} mod15=13 \)。

例题35：判断123是否为素数（用费马小定理的必要条件）

解：步骤：

1. 假设123是素数，取a=2（\( \gcd(2,123)=1 \)），则由费马小定理，\( 2^{122} ≡1 mod123 \)；

2. 计算\( 2^{122} mod123 \)：123=3×41，分别计算模3和模41，再用中国剩余定理合并；

模3：\( 2^2≡1 mod3 \)，\( 122=2×61 \)，故\( 2^{122}≡1^{61}=1 mod3 \)；

模41：41是素数，\( 2^{40}≡1 mod41 \)，\( 122=40×3 + 2 \)，故\( 2^{122}≡(1)^3×2^2=4 mod41 \)；

3. 找x满足\( x≡1 mod3 \)且\( x≡4 mod41 \)：设x=41k+4，代入得\( 41k+4≡2k+1≡1 mod3 \implies k≡0 mod3 \)，故x=123m+4，即\( 2^{122}≡4 mod123 \)；

4. 因\( 4≠1 mod123 \)，故123不是素数（实际123=3×41）。

例题36：用费马小定理求解同余方程\( 4x ≡ 5 mod 7 \)

解：步骤：

1. 找4的逆元（模7）：因7是素数，\( \gcd(4,7)=1 \)，逆元为\( 4^{5} mod7 \)（由费马小定理，\( 4^6≡1 mod7 \)，逆元为\( 4^5 \)）；

2. 计算逆元：\( 4^1=4 mod7 \)，\( 4^2=16≡2 mod7 \)，\( 4^4=(4^2)^2=4 mod7 \)，\( 4^5=4^4×4=4×4=16≡2 mod7 \)，故逆元为2；

3. 方程两边乘逆元：\( x≡5×2=10≡3 mod7 \)；

验证：4×3=12≡5 mod7，成立。

例题37：用欧拉定理证明\( 9^{10} ≡ 1 mod 10 \)（即9的10次幂末位是1）

解：步骤：

1. 计算\( \varphi(10) \)：10=2×5，\( \varphi(10)=1×4=4 \)；

2. 验证条件：\( \gcd(9,10)=1 \)，应用欧拉定理：\( 9^4≡1 mod10 \)；

3. 计算\( 9^{10} \)：\( 10=4×2 + 2 \)，故\( 9^{10}=9^{4×2 + 2}=(9^4)^2×9^2≡1^2×81≡1 mod10 \)；

即\( 9^{10}≡1 mod10 \)，末位是1，成立。

例题38：证明\( 2^{30} ≡ 1 mod 31 \)（31是素数）

解：用费马小定理：

因31是素数，\( \gcd(2,31)=1 \)，故\( 2^{30}≡1 mod31 \)（费马小定理中，p=31，\( p-1=30 \)）；

直接验证：\( 2^5=32≡1 mod31 \)，故\( 2^{30}=(2^5)^6≡1^6=1 mod31 \)，成立。

例题39：用欧拉定理计算\( 10^{100} mod 17 \)的值

解：步骤：

1. 计算\( \varphi(17) \)：17是素数，\( \varphi(17)=16 \)；

2. 验证条件：\( \gcd(10,17)=1 \)，应用欧拉定理：\( 10^{16}≡1 mod17 \)；

3. 指数取余：\( 100=16×6 + 4 \)，故\( 10^{100}=10^{16×6 + 4}=(10^{16})^6×10^4≡1^6×10000 mod17 \)；

4. 计算\( 10000 mod17 \)：17×588=9996，故10000-9996=4，即\( 10000≡4 mod17 \)；

即\( 10^{100} mod17=4 \)。

例题40：证明对任意整数n，\( n^5 ≡ n mod 5 \)（费马小定理的直接应用）

解：分情况讨论：

若\( 5 \mid n \)，则n≡0 mod5，故\( n^5≡0^5=0≡n mod5 \)；

若\( 5 \nmid n \)，则\( \gcd(n,5)=1 \)，5是素数，由费马小定理，\( n^4≡1 mod5 \)；

两边乘n得\( n^5≡n mod5 \)；

综上，对任意整数n，\( n^5≡n mod5 \)成立（实例：n=2，\( 2^5=32≡2 mod5 \)；n=3，\( 3^5=243≡3 mod5 \)，正确）。

数学基础 : 小学数学、初中数学、高中数学、高等数学