模p乘法群 我们先从模运算的基本概念开始。模p乘法群是建立在你已了解的模运算和原根知识之上的一个重要结构。 定义 设p是一个素数。考虑集合 {1, 2, 3, ..., p-1}，即模p下所有与p互质的剩余类（因为p是素数，所以1到p-1的所有整数都与p互质）。在这个集合上定义乘法运算：对于集合中的任意两个元素a和b，它们的运算结果定义为 (a × b) mod p。 这个集合配合这个乘法运算，构成一个群。这个群就被称为 模p的乘法群 ，记作 (Z/pZ)* 或 F_ p* 。 为什么它是一个群？ 一个代数结构要成为群，需要满足四个条件。我们来逐一验证： 封闭性 ：如果a和b都是1到p-1之间的整数，那么a × b可能大于p。但经过模p运算后，结果是一个在0到p-1之间的整数。我们需要证明这个结果不会是0。因为p是素数，且a和b都不被p整除，所以a × b也不可能被p整除。因此，(a × b) mod p 的结果在1到p-1之间。封闭性成立。 结合律 ：乘法运算本身满足结合律，模运算不改变这一点。即 [ (a × b) mod p × c] mod p = [ a × (b × c) mod p ] mod p。 单位元 ：数字1就是这个群的单位元。因为对于任意元素a，都有 (a × 1) mod p = a mod p = a。 逆元 ：对于集合中的任意元素a（1 ≤ a ≤ p-1），由于a和p互质，根据你已学过的“模逆元”知识，存在唯一的整数b（1 ≤ b ≤ p-1），使得 (a × b) mod p = 1。这个b就是a在模p下的乘法逆元，记作 a⁻¹。 由于满足所有条件，所以 (Z/pZ)* 确实构成一个群。 群的阶 群的阶指的是群中元素的个数。对于模p乘法群 (Z/pZ)* ，它的元素是1, 2, ..., p-1，所以群的阶为 p-1。 循环群性质 这是模p乘法群最核心、最重要的性质之一。我们已经知道“原根”的概念：如果存在一个整数g（1 ≤ g ≤ p-1），使得集合 {g¹ mod p, g² mod p, ..., g^(p-1) mod p} 恰好就是 {1, 2, ..., p-1}，那么g就被称为模p的一个原根。 这恰恰意味着，模p乘法群 (Z/pZ)* 是一个由原根g生成的循环群。任何一个循环群都同构于整数加法群 Z_ n，其中n是群的阶（这里n=p-1）。 一个具体的例子：模7乘法群 (Z/7Z) * 设p=7。 群的集合是 {1, 2, 3, 4, 5, 6}，阶为6。 我们验证3是否是原根： 3¹ mod 7 = 3 3² mod 7 = 9 mod 7 = 2 3³ mod 7 = 27 mod 7 = 6 3⁴ mod 7 = 81 mod 7 = 4 3⁵ mod 7 = 243 mod 7 = 5 3⁶ mod 7 = 729 mod 7 = 1 生成的集合是 {3, 2, 6, 4, 5, 1}，正好是群的全部元素。所以3是模7的一个原根。 因此，(Z/7Z)* 是一个由3生成的循环群。我们可以将群中的元素表示为3的幂次（模7）： ... 3⁻², 3⁻¹, 3⁰, 3¹, 3², ... 因为3⁶ ≡ 1，所以幂次是模6循环的。 重要性及应用 模p乘法群的循环结构在数论和密码学中有着极其广泛的应用： 离散对数问题 ：在循环群中，给定生成元g和群中的一个元素h，求解整数k使得 gᵏ ≡ h (mod p) 是一个计算上困难的问题（当p很大时）。这个“离散对数问题”是许多现代公钥密码系统（如Diffie-Hellman密钥交换、ElGamal加密）的安全基础。 简化理论推导 ：因为它是循环群，所以很多关于循环群的现成定理可以直接应用，大大简化了理论分析。例如，之前学过的“二次剩余”的判断（勒让德符号）可以非常简洁地通过将数表示为原根的幂次来判定：一个元素是二次剩余当且仅当它的指数是偶数。