模m同余理论与性质：从费马小定理到欧拉定理

"第4章 同余问题" 同余理论是数论中的一个重要分支，它在密码学、计算数学和理论计算机科学等领域有着广泛的应用。本章主要探讨了同余的概念、性质以及相关的定理。 首先，同余的定义是基于除法的余数概念。给定一个正整数m，如果两个整数a和b除以m得到相同的余数，我们就说a和b对模m同余，表示为a ≡ b (mod m)。相反，如果余数不同，它们就对模m不同余，记为a ≢ b (mod m)。例如，5 mod 6 = 21 mod 6，所以5和21对模6同余。 接着，我们引入了模m剩余类或同余类的概念，这是整数集合根据除以m的余数划分的子集。每个同余类内的任意两个元素都是模m同余的。 定理1表明，a ≡ b (mod m) 当且仅当 m 整除 (a - b)，即m | (a - b)。这意味着两个数同余意味着它们之间的差能被模数整除。 定理2进一步指出，如果a ≡ b (mod m)，那么存在整数k使得 a = b + km，这给出了同余关系的一个等价形式。 费马小定理是数论中的一个基本定理，对于质数p和任何整数a，如果a和p互质，即(a, p) = 1，那么a的p次幂除以p的余数等于a本身，即ap ≡ a (mod p)。如果a不是p的倍数，那么a的(p-1)次幂除以p的余数为1，即a^(p-1) ≡ 1 (mod p)。 欧拉定理是另一个关键定理，它扩展了费马小定理，适用于a和正整数n互质的情况。它表明，a乘以欧拉函数φ(m)的结果除以m的余数为1，即aφ(m) ≡ 1 (mod m)。欧拉函数φ(m)计算的是小于等于n且与n互质的正整数的数量。 同余还具有一系列的性质，如加法、减法和乘法的同余性。比如，如果a ≡ b (mod m) 和 x ≡ y (mod m)，那么a+x ≡ b+y (mod m)，a-x ≡ b-y (mod m)，以及ax ≡ by (mod m)。此外，如果a模p和a模q的余数相同，且p和q互质，那么a模(pq)的余数也是相同的。 最后，欧几里得算法用于计算两个非零自然数a和b的最大公约数(gcd)，其基本原理是gcd(a, b) = gcd(b, a % b)，通过不断迭代直到其中一个数变为0，可以求得最大公约数。 这些基础知识构成了同余理论的基础，它们在解决诸如解线性同余方程、简化模运算以及设计加密算法等问题时起到关键作用。在NOIP（全国青少年信息学奥林匹克竞赛）和C++编程中，理解和应用同余理论可以帮助参赛者解决复杂的数学和算法问题。