原根
| 原根 | |
|---|---|
| 术语名称 | 原根 |
| 英语名称 | primitive root |
原根(primitive root)指某个模数下的特定的正整数，任意与模数互质的数都能表示为与这个数的某个幂同余。原根模 n 剩余类乘法群是循环群时才存在，且就是其生成元，表现为其乘法阶数在这个群中最大，与群的阶数，即模数的 Euler 函数值相等。
定义
对正整数 [math]\displaystyle{ n }[/math] 和整数 [math]\displaystyle{ a }[/math] ，若 [math]\displaystyle{ a }[/math] 在模 [math]\displaystyle{ n }[/math] 下的乘法阶数 [math]\displaystyle{ \operatorname{ord}_{n}(a) }[/math] 等于 [math]\displaystyle{ \varphi(n) }[/math] ，则称 [math]\displaystyle{ a }[/math] 是一个模 [math]\displaystyle{ n }[/math] 的原根(primitive root modulo [math]\displaystyle{ n }[/math])，简称 [math]\displaystyle{ n }[/math] 的原根。
性质
原根存在性定理
存在模 [math]\displaystyle{ n }[/math] 的原根，当且仅当 [math]\displaystyle{ n }[/math] 是 [math]\displaystyle{ 1, 2, 4, p^k, 2 p^k }[/math] 之一。其中 [math]\displaystyle{ p }[/math] 为奇质数， [math]\displaystyle{ k }[/math] 为正整数。
原根的性质
- [math]\displaystyle{ a }[/math] 是 [math]\displaystyle{ n }[/math] 的原根当且仅当 [math]\displaystyle{ 1, a, a^2, a^3, \dots, a^{\varphi(n)-1} }[/math] 遍历模 [math]\displaystyle{ n }[/math] 的简化剩余系。
- [math]\displaystyle{ 1, a, a^2, a^3, \dots }[/math] 以 [math]\displaystyle{ \varphi(n) }[/math] 为周期，每周期内都遍历 [math]\displaystyle{ n }[/math] 的一个最简剩余系，且周期内两两不同余。
- [math]\displaystyle{ a }[/math] 是模 [math]\displaystyle{ n }[/math] 的原根，当且仅当 [math]\displaystyle{ a^{\frac{\varphi(n)}{q_j}} \not\equiv 1 \pmod n }[/math] ，其中 [math]\displaystyle{ q_j }[/math] 是 [math]\displaystyle{ \varphi(n) }[/math] 的任意质因数。