模m的阶

定义

设\(m>1,(a,m)=1\) 则使得：

成立的最小正整数\(d_0\)称为\(a\)模\(m\)的阶
记为\(\delta_m(a)\)

性质

设\(m>1,\quad n>1,\quad(a,m)=1\)
1.若\(\delta_m(a)=n\),则\(a^k\equiv 1(mod m)\)且 \(n|k\)
2.\(a\equiv b(mod m), \delta_m(a)=\delta_m(b)\)
3\(.a,a^2,\ldots,a^{\delta_m(a)}\)模\(m\)两两不同余
4.若\(\delta_m(a)=n\),则\(a^i\equiv a^j(mod m) ; i\equiv j(mod n)\)
5.\(\delta_m(a^i)=\delta_m(a)/(\delta_m(a),i)\)如\(\delta_7(5)=6,\quad\delta_7(5^2)=6/(6,2)=3\)
6.设\(m\)为正整数，\(a,b\)为整数，\(\delta_m(a)=u,\delta_m(b)=v\),且\((u,v)=1\)，则\(\delta_m(ab)=uv\)
7.对于任意与\(n\)互素的\(a,b\)，一定存在\(c\)，使得：
\(\delta_n(c)=[\delta_n(a),\delta_n(b)]\)

与阶相关的定理

定理一：
设\(k\)为整数，\(p\)为素数，则同余方程:

的解数为\((k,p-1)\)
定理二：
设\(k\)为整数，\(p\)为素数，\(p\)不能整除\(n\),则同余方程:

的解数为\((k,p-1)\)或无解，即\(n\)为模\(m\)的\(k\)次剩余或\(n\)为模\(m\)的\(k\)次非剩余
定理三：
设\(k\)为整数，\(p\)为素数，当\(x\)遍历模\(p\)的一个缩系时，\(x^k\)取\((p-1)/(k,p-1)\)个模\(p\)不同的值
定理四：
若\(d|m\),则在\(m\)的一个剩余系中与\(m\)的最大公因子为\(d\)的元素有个\(φ( {m\over d})\)
\(m= \sum _ {d|m } φ（d）\)
定理五：
设\(t|p-1, p\)为素数，则模\(p\)的阶为\(t\)的互不同余的整数个数为\(φ(t)\)。特别有\(φ(p-1)\)个互不同余的整数模\(p\)的阶为\(p-1\)

局部要点回顾

\(①\ x^{k}\equiv 1(mod\ p)\ \text{有}(p-1,k)\ \text{个解}。\)
\(②\ x^{k}\equiv a(mod\ p)\ \text{有}0\ \text{个或}(p-1,k)\ \text{个解}。\)
\(③\ \text{模}p\ \text{的}k\ \text{次剩余有}\frac{p-1}{(p-1,k)}\ \text{个}。\)
\(④\ n=\sum_{n|d}\varphi(d)\)。
\(⑤\ \text{模}p\ \text{剩余类的阶必定是}\varphi(p)=p-1\ \text{的一个因子}。\)
\(⑥\ \text{若}d|p-1,\ \text{模}p\ \text{的剩余类中，阶为}d\ \text{的元素有}\varphi(d)\ \text{个；}\)
\(⑦\ \text{若}d\nmid p-1,\ \text{模}p\ \text{的剩余类中，阶为}d\ \text{的元素有}0\ \text{个。}\)

原根

定义: 设\(m\)为正整数，\(a\)是整数，若\(\delta_m(a)=φ(m)\)，则称\(a\)为模\(m\)的一个原根
定理：设素数\(p>2\)，则对模\(p\)必有原根存在
定理：设\(p\)为素数，\(q_1,q_2,\cdots ,q_k\)为\(p-1\)的所有不同素因子，则
\(g\)是模\(p\)的原根的充要条件是\(g^{(p-1) }\neq 1(mod p)\)
定理：若\(g\)是模\(p\)的原根，则\(g\)或\(g+p\)是模\(p^2\)的原根
定理：若\(g\)是模\(p\)（奇素数）的原根，有下述结论:
(1)如 \(g^{(p-1)}≠1(mod p^2)\) ，则\(g\)是模\(p^2\)的原根
(2)\(g^{(p-1)}=1(mod p^2)\) ，则\(g+p\)是模\(p^2\)的原根
定理3：若\(g\)是模\(p^2\)的原根，则\(g\)是模\(p^l\)的原根\((l\geq 2)\)
定理：若\(g\)是模\(p\)（奇素数）的原根，\(s≧2\)，我们有下述结论：
（1）如 \(g^{(p-1)}≠1(mod p^2)\) ，则\(g\)是模\(p^s\)的原根
（2）\(g^{(p-1)}=1(mod p^2)\) ，则\(g+p\)是模\(p^s\)的原根
定理：若\(g\)是模\(p^s\)（奇素数）的原根，则\(g\)与\(g+p^s\)中的奇数是\(2p^s\)的一个原根。
定理4：模\(m\)有原根的充分必要条件：\(m=2，4，p^l\)或\(2p^l\)