【acm】【数论】阶和原根
阶
定义
设\(m > 1\) 且 \((a, m) = 1\)，则使得
\[a^t \equiv 1 \pmod m\]
成立的最小的正整数\(t\)称为 \(a\)对模\(m\)的阶，记为\(\delta_m(a)\)。
定理
定理1 若\(m>1\)且\((a, m) = 1\)，且\(a^n \equiv 1 \pmod m\), n > 0，则有
\[\delta_m(a)\,|\, n\]
定理2 由定理1和欧拉定理易知
\[\delta_m(a)\,|\, \phi(m)\]
推论
推论1 若\(p\)和\(q\)为奇素数，且\(q\,|\,(a^p-1)\)，则或有\(q\,|\,(a-1)\)，或有\(q = 2kp+1\), 其中k为某整数。
推论2 \(2^p-1\)的任何因子必取\(2kp+1\)的形式。
原根
定义
如果\(a\)的阶(mod m)为\(\phi(m)\)，则称\(a\)为\(m\)的一个原根。 即若\(\delta_m(a)=\phi(m)\)，则称\(a\)为\(m\)的一个原根。
定理
定理1 若\(g\)是\(m\)的一个原根，则 \[g, g^2, \cdots, g^{\phi(m)}\] 各数对模m的最小剩余，恰是小于\(m\)且与\(m\)互素的\(\phi(m)\)个正整数的一个排列。
定理2 每一个素数\(p\)都有\(\phi(p-1)\)个原根。事实上，每一个数\(m\)都有\(\phi(\phi(m))\)个原根(如果有的话)。
定理3 一个数\(m\)有原根的充要条件是\(m = 1, 2, 4, p^e, 2p^e\), 其中\(p\)为奇素数， \(e\)为正整数。
推论
推论1 若\(d\,|\,(p-1)\)，则\(x^d \equiv 1 \pmod p\)恰有\(d\)个解。
推论2 若\(p\)为素数，\(d\,|\,(p-1)\)，则阶为\(d\)的最小剩余(mod p)的个数为\(\phi(d)\)。
原根的求法
求一个数\(m\)的原根，先求\(\phi(m)\)的素幂分解式，即
\[\phi(m)= p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}\]
然后枚举\(g\)，若\(g\)满足恒有
\[g^{\frac{\phi(m)}{p_i}} \not = 1 \pmod m,\qquad i = 1, 2, \cdots, k\]
则\(g\)为\(m\)的一个原根。
tips
数据不大的时候枚举所有\(\phi(m)\)的因子(除本身)也可。