乘法阶数
| 乘法阶数 | |
|---|---|
| 术语名称 | 乘法阶数 |
| 英语名称 | multiplicative order |
| 别名 | 乘法阶, 指数 |
乘法阶数/乘法阶(multiplicative order)指对一个整数，使其幂与 1 同余的最小次数。可以看作模 n 剩余类乘法群中元素的阶。
定义
| 乘法阶数 | |
|---|---|
| 运算名称 | 乘法阶数 |
| 运算符号 | [math]\displaystyle{ \operatorname{ord}_\bullet(\bullet) }[/math],[math]\displaystyle{ \delta_\bullet(\bullet) }[/math] |
| Latex | \operatorname{ord} , \delta
|
| 运算对象 | 互质, 整数 |
| 运算元数 | 2 |
| 运算结果 | 正整数
|
对整数 [math]\displaystyle{ a }[/math] ，模数 [math]\displaystyle{ n }[/math] 且 [math]\displaystyle{ \operatorname{gcd}(a, n) = 1 }[/math] ，称满足 [math]\displaystyle{ a^k \equiv 1 \pmod n }[/math] 的最小正整数 [math]\displaystyle{ k }[/math] 为整数 [math]\displaystyle{ a }[/math] 在模 [math]\displaystyle{ n }[/math] 下的乘法阶数/乘法阶(multiplicative order of [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math] )，记作 [math]\displaystyle{ \operatorname{ord}_n(a) }[/math] 或 [math]\displaystyle{ \delta_n(a) }[/math] 。
性质
- [math]\displaystyle{ b \equiv a \pmod n \Rightarrow \operatorname{ord}_n(a) = \operatorname{ord}_n(b) }[/math]
- [math]\displaystyle{ a^h \equiv 1 \pmod n \Rightarrow \operatorname{ord}_n(a) \mid h }[/math]
- [math]\displaystyle{ \delta_n(a) \mid \phi(n) }[/math] 、 [math]\displaystyle{ \delta_{2^l}(a) \mid 2^{l-2}, l\geq 3 }[/math]
- [math]\displaystyle{ \operatorname{gcd}(a, n) = 1 \land a^h \equiv a^k \pmod n \Rightarrow k \equiv h \pmod{\operatorname{ord}_n(a)} }[/math]
- [math]\displaystyle{ \operatorname{gcd}(a, n) = 1 }[/math] 时， [math]\displaystyle{ a^0, a^1, a^2, \dots, a^{\operatorname{ord}_n(a)-1} }[/math] 在模 [math]\displaystyle{ n }[/math] 下两两不同余。
- [math]\displaystyle{ b \equiv a^{-1} \pmod n \Rightarrow \operatorname{ord}_n(b) = \operatorname{ord}_n(a) }[/math]
- 对非负整数 [math]\displaystyle{ k }[/math] ，有 [math]\displaystyle{ \operatorname{ord}_n(a^k) = \frac{\operatorname{ord}_n(a)}{\operatorname{gcd}(\operatorname{ord}_n(a), k)} }[/math]
- 完全乘性，[math]\displaystyle{ \operatorname{ord}_n(1) = 1 }[/math] 且 [math]\displaystyle{ \operatorname{ord}_n(ab) = \operatorname{ord}_n(a)\operatorname{ord}_n(b) \Leftrightarrow \operatorname{gcd}(a,b)=1 }[/math]
- [math]\displaystyle{ n \mid m \Rightarrow \operatorname{ord}_n(a) = \operatorname{ord}_m(a) }[/math]
- [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ a }[/math] 不直接是 [math]\displaystyle{ a_1 a_2 }[/math] ，而是遵循中国剩余映射下的对应关系。
- [math]\displaystyle{ \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]\displaystyle{ a }[/math] 不直接是 [math]\displaystyle{ a_1 a_2 }[/math] ，而是遵循中国剩余映射下的对应关系。
- [math]\displaystyle{ (\forall a_1, a_2)(\exists a) (\operatorname{ord}_{n}(a) = \operatorname{lcm}(\operatorname{ord}_n(a_1),\operatorname{ord}_n(a_2)) }[/math]