查看“︁乘法阶数”︁的源代码

[[分类:同余理论]]
{{InfoBox
|name=乘法阶数
|eng_name=multiplicative order
|aliases=乘法阶,指数
}}
'''乘法阶数'''/'''乘法阶'''('''multiplicative order''')指对一个整数，使其[[幂]]与 1 [[同余]]的最小次数。可以看作[[模 n 剩余类乘法群]]中元素的[[阶（群）|阶]]。

== 定义 ==

{{Operation
|name=乘法阶数
|symbol=<math>\operatorname{ord}_\bullet(\bullet)</math>,<math>\delta_\bullet(\bullet)</math>
|latex=\operatorname{ord},\delta
|operand=互质,整数
|result=正整数
}}
对整数 <math>a</math> ，模数 <math>n</math> 且 <math>\operatorname{gcd}(a, n) = 1</math> ，称满足 <math>a^k \equiv 1 \pmod n</math> 的最小正整数 <math>k</math> 为整数 <math>a</math> 在模 <math>n</math> 下的'''乘法阶数'''/'''乘法阶'''('''multiplicative order''' of <math>a</math> modulo <math>n</math> )，记作 <math>\operatorname{ord}_n(a)</math> 或 <math>\delta_n(a)</math> 。

== 性质 ==

* <math>b \equiv a \pmod n \Rightarrow \operatorname{ord}_n(a) = \operatorname{ord}_n(b)</math>
* <math>a^h \equiv 1 \pmod n \Rightarrow \operatorname{ord}_n(a) \mid h</math>
* <math>\delta_n(a) \mid \phi(n)</math> 、 <math>\delta_{2^l}(a) \mid 2^{l-2}, l\geq 3</math>
* <math>\operatorname{gcd}(a, n) = 1 \land a^h \equiv a^k \pmod n \Rightarrow k \equiv h \pmod{\operatorname{ord}_n(a)}</math>
* <math>\operatorname{gcd}(a, n) = 1</math> 时， <math>a^0, a^1, a^2, \dots, a^{\operatorname{ord}_n(a)-1}</math> 在模 <math>n</math> 下两两不同余。
* <math>b \equiv a^{-1} \pmod n \Rightarrow \operatorname{ord}_n(b) = \operatorname{ord}_n(a)</math>
* 对非负整数 <math>k</math> ，有 <math>\operatorname{ord}_n(a^k) = \frac{\operatorname{ord}_n(a)}{\operatorname{gcd}(\operatorname{ord}_n(a), k)}</math>
* [[完全乘性函数|完全乘性]]，<math>\operatorname{ord}_n(1) = 1</math> 且 <math>\operatorname{ord}_n(ab) = \operatorname{ord}_n(a)\operatorname{ord}_n(b) \Leftrightarrow \operatorname{gcd}(a,b)=1</math>
* <math>n \mid m \Rightarrow \operatorname{ord}_n(a) = \operatorname{ord}_m(a)</math>
* <math>\operatorname{gcd}(m,n)=1 \Rightarrow \operatorname{ord}_{mn}(a) = \operatorname{lcm}(\operatorname{ord}_m(a),\operatorname{ord}_n(a)) = \frac{\operatorname{ord}_m(a)\operatorname{ord}_n(a)}{\operatorname{gcd}(\operatorname{ord}_m(a),\operatorname{ord}_n(a))}</math> ，此式可推广到多个数两两[[互质]]的情况。
* <math>\operatorname{gcd}(m,n)=1 \Rightarrow (\forall a_1, a_2)(\exists a) (\operatorname{ord}_{mn}(a) = \operatorname{lcm}(\operatorname{ord}_m(a_1),\operatorname{ord}_n(a_2)) \Leftrightarrow </math> ，但这里 <math>a</math> 不直接是 <math>a_1 a_2</math> ，而是遵循[[中国剩余映射]]下的对应关系。
* <math>\operatorname{gcd}(m,n)=1 \Rightarrow (\forall a_1, a_2)(\exists a) (\operatorname{ord}_{mn}(a) = \operatorname{lcm}(\operatorname{ord}_m(a_1),\operatorname{ord}_n(a_2)) \Leftrightarrow </math> ，但这里 <math>a</math> 不直接是 <math>a_1 a_2</math> ，而是遵循[[中国剩余映射]]下的对应关系。
* <math>(\forall a_1, a_2)(\exists a) (\operatorname{ord}_{n}(a) = \operatorname{lcm}(\operatorname{ord}_n(a_1),\operatorname{ord}_n(a_2))</math>


{{同余理论}}