查看“︁原根”︁的源代码

[[分类:同余理论]]
{{InfoBox
|name=原根
|eng_name=primitive root
}}
'''原根'''('''primitive root''')指某个模数下的特定的正整数，任意与模数[[互质]]的数都能表示为与这个数的某个[[幂]][[同余]]。原根[[模 n 剩余类乘法群]]是[[循环群]]时才存在，且就是其生成元，表现为其[[乘法阶数]]在这个群中最大，与群的阶数，即模数的 [[Euler 函数]]值相等。

== 定义 ==

对正整数 <math>n</math> 和整数 <math>a</math> ，若 <math>a</math> 在模 <math>n</math> 下的乘法阶数 <math>\operatorname{ord}_{n}(a)</math> 等于 <math>\varphi(n)</math> ，则称 <math>a</math> 是一个模 <math>n</math> 的'''原根'''('''primitive root''' modulo <math>n</math>)，简称 <math>n</math> 的原根。

== 性质 ==

=== 原根存在性定理 ===

存在模 <math>n</math> 的原根，当且仅当 <math>n</math> 是 <math>1, 2, 4, p^k, 2 p^k</math> 之一。其中 <math>p</math> 为奇质数， <math>k</math> 为正整数。

=== 原根的性质 ===

* <math>a</math> 是 <math>n</math> 的原根当且仅当 <math>1, a, a^2, a^3, \dots, a^{\varphi(n)-1}</math> 遍历模 <math>n</math> 的[[简化剩余系]]。
* <math>1, a, a^2, a^3, \dots</math> 以 <math>\varphi(n)</math> 为周期，每周期内都遍历 <math>n</math> 的一个最简剩余系，且周期内两两不同余。
* <math>a</math> 是模 <math>n</math> 的原根，当且仅当 <math>a^{\frac{\varphi(n)}{q_j}} \not\equiv 1 \pmod n</math> ，其中 <math>q_j</math> 是 <math>\varphi(n)</math> 的任意质因数。


{{同余理论}}