在同余理论中，模 的互质同余类构成一个乘法群，称为整数模 n 乘法群（multiplicative group of integers modulo n）。这个群是数论的基石，在密码学、整数分解和素性测试中均有运用。

整数模 n 乘法群用符号表示为 ，或者 、、。

整数模 n 乘法群的元素

是一个有限群。其集合中每个元素不是一个单一整数，而是一个同余类，整数 模 的同余类表示为 或者 。

如果 ，那么 。也就是说一个数 如果与 互质，那么 里面所有的数都与 互质。因此我们可以从 中的每个同余类里面抽出一个数来代表对应的同余类。例如 ，我们可以将 写成下面任意一种形式



通常我们用每个同余类中最小的正整数来表示那个类，这样形成的集合也叫做最小简约余数系。上面提到的 就是这样一个例子。

后面我们都用模 的最小简约余数系来代表群 的集合。

证明

要证明 是一个群，只需要证明它满足群的四大公理即可。

封闭性：如果 和 ，那么 ，因此封闭性成立。

结合性：由于整数乘法的属性，群的结合性自然成立。

存在单位元：1 与任何数互质， 总是包含 1 的同余类，因此 1 的同余类为单位元。

存在逆元：整数模 乘法群的逆元定义为对于给定集合中的整数 ，逆元 满足 。找出逆元 等价于求解方程 。根据裴蜀定理，因为，所以一定存在， 使改方程成立。且 与 互质，所以 的逆元 也属于该群。

当 为循环群

不一定是循环群。 为循环群的条件为： 等于 、、、 或者 ，其中 是奇质数， 为正整数。

当 为循环群时，其生成元的个数为 ，也就是说模 的本原根的个数为 。

证明：

在前一篇文章中我们证明了，有限循环群 中的任一元素 的阶可表示为

因此要使 为生成元，必须满足 。因此 中生成元的个数为 。

欧拉函数 给出了小于 且与 互质的数的个数。因此可知 的阶就为 。由此可以得到 生成元的个数为 。

当 n 为质数

当 为质数时，我们通常用 来表示 。可以证明 总是循环群。其生成元的个数为 。

如果 能整除 ，那么 中存在 个 阶的生成器。

例子：当 时。

当 时，我们可以求出 的阶为 。

由于 的阶 ，因此能整除 12 的数有：1，2，3，4，6，12。 一定存在子群的阶等于这些数，而且 子群的阶只可能是这些数中的一个。我们可以计算出对于每个阶的子群，其生成元的个数：

  • 1 阶：，有 1 个。
  • 2 阶：，有 1 个。
  • 3 阶：，有 2 个。
  • 4 阶：，有 2 个。
  • 6 阶：，有 2 个。
  • 12 阶：，有 4 个。

其中 为 生成元的个数。

把各阶子群的生成元个数加起来， 正好等于 。这是因为 中每个元素的阶是唯一的，因此每个子群的生成元个数加起来恰好等于 元素的个数。这也从侧面证明了欧拉函数的一个性质：所有能整除 的数的欧拉函数和为 。表示为：

其中 为所有能整除 的数。

为了验证我们的结果，下面给出了 中每个元素生成的子群和阶：
1 { 1 } 1
2 { 2,4,8,3,6,12,11,9,5,10,7,1 } 12
3 { 3,9,1 } 3
4 { 4,3,12,9,10,1 } 6
5 { 5,12,8,1 } 4
6 { 6,10,8,9,2,12,7,3,5,4,11,1 } 12
7 { 7,10,5,9,11,12,6,3,8,4,2,1 } 12
8 { 8,12,5,1 } 4
9 { 9,3,1 } 3
10 { 10,9,12,3,4,1 } 6
11 { 11,4,5,3,7,12,2,9,8,10,6,1} 12
12 { 12,1 } 2

另外可以看到一个有意思的性质：元素 的阶始终为 2。这是因为 。

由于质数 的群 在密码学中更为常用，因此我们后面着重讨论这个群。

寻找生成元

通过上述分析，给我们寻找 的生成元一些启发。一个简单的想法是，从 开始，到 结束，对每个数 ，测试对于每个小于且能整除 的数 ，如果都满足 ，那么就认为这个数 是生成元。

但是这种方法中找出每个小于且能整除 的数 比较麻烦，需要先将 做质因数分解，再将这些质因数排列组合求乘积，还要考虑去重复。

有一个更简单的方式是将 做质因数分解得到 ，其中 是 的所有不同质因数。对于元素 ，我们只需要测试

，其中

如果对于每个不同质因数 都满足上述条件的话，元素 就是生成元。虽然这个算法，对每个数的测试次数变少了。但是这个算法的难点在于对于一个很大的数 ，分解 的质因数将会非常困难。

如何挑选数来测试

如果我们的任务是只需要找到一个生成元，那么该如何从 挑选数来做上面提到的测试呢。一个简单的办法是从 2 开始，一个一个测试，直到找到一个为止。

还有一种方法是随机从 里面挑选一个。那么随机挑中一个的概率有多大呢？我们知道生成元的个数为 ，而 元素的总个数为 。因此选中的概率为：

设 做质因数分解得到 ，根据欧拉函数的乘法公式得到：

从上述公式可以观察到，如果 的质因数 越大，那么随机选中生成元的概率就越大。

例如 ，，因此随机挑选到生成元的概率为 。

找到余下的生成元

只要找到一个生成元，我们可以通过另一种方法来找到剩下的生成元。假如我们找到 为生成元，根据循环群的性质，其它的生成元一定可以表示为 ，根据前面的公式我们可以得到 的阶为

因此 要想为生成元，它的阶 必须等于 ，那么 与 必须互质，也就是 。

对于 的例子来说，当我们测试得到 2 为生成元后，我们找出所有与 12 互质的数为：5、7、11，由此可以求出其它 3 个生成元：



虽然这个方法看起来很简单，但是找出所有小于且与 互质的数还是很困难。

参考文献

[1] The multiplicative group modulo p: https://www.di-mgt.com.au/multiplicative-group-mod-p.html
[2] CYCLICITY OF : https://kconrad.math.uconn.edu/blurbs/grouptheory/cyclicmodp.pdf