版权归原作者所有,如有侵权,请联系我们

[科普中国]-整数模n乘法群

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

在同余理论中,模 n 的互质同余类组成一个乘法群,称为整数模 n 乘法群,也称为模 n 既约剩余类。在环理论中,一个抽象代数的分支,也称这个群为整数模 n 的环的单位群(单位是指乘法可逆元)。

这个群是数论的基石,在密码学、整数分解和素性测试均有运用。例如,关于这个群的阶(即群的“大小”),我们可以确定如果 n 是质数当且仅当阶数为 n-1。

群公理容易验证模n互质同余类在乘法运算下满足阿贝尔群的公理。1

恒同: 1 是恒同;

闭:如果a和b都与n互质,那么ab也是;

逆:找x满足ax≡ 1 (modn) 等价于解ax+ny= 1,可用欧几里得算法求出;

结合性和交换性:由整数的相应事实以及模n运算是一个环同态推出。

记法整数模n环记作(即整数环模去理想nZ= (n) ,由n的倍数组成)或因作者所喜,它的单位群可能记为或类似的记号。

结构2 的幂次模 2 只有一个互质同余类 1,所以 平凡。2

模 4 有两个互质同余类,1 和 3,所以两元循环群。

模 8 有四个互质同余类,1, 3, 5 和 7,每个平方都是 1,所以Klein 四元群。

模 16 有八个互质同余类,1, 3, 5, 7, 9, 11, 13 和 15。为 2-扭子群(即每个元素的平方为 1),所以不是循环群。3的幂次:1,3,9,11 是一个 4 阶子群,5 的幂次也是,1,5,9,13。所以

奇质数的幂对奇质数的幂p,此群是循环群:

一般合数中国剩余定理说明如果那么环 每个质数幂因子相应的环的直积:

类似地,的单位群是每个质数幂因子相应群的直积:

阶数群的阶数由欧拉函数给出:(OEIS中的数列A000010) 这是直积中各循环阶数的乘积。

指数指数为卡迈克尔函数,(OEIS中的数列A002322),即这些循环群的阶数的最小公倍数。这意味着如果a和n互质,

生成元是循环群当且仅当。这在n为奇质数的幂次、奇质数幂次 2 倍、2 和 4 成立,此时也称一个生成元为模 n 的原根

因为所有n= 1, 2, ..., 7 是循环群,上述结论的另一种说法是:如果n 有原根;如果n≥ 8,且不能被 4 或者两个不同的奇质数整除,有原根。( A033948= 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, ... )

一般情形每个直积因子循环有一个生成元。

本词条内容贡献者为:

胡建平 - 副教授 - 西北工业大学