知识点

阶

• 定义：由欧拉定理可知，对\(a\in \mathbb{Z},m\in\mathbb{N^* }\)，若\(gcd(a,m)=1\) ，则 \(a^{\varphi(m)}\equiv 1\pmod m\)
  因此满足同余式\(a^n\equiv 1\pmod m\)的最小正整数\(n\)存在，这个\(n\)称作\(a\)模\(m\)的阶，记作\(\delta_m(a)\)

• 性质：

1. \(a^1,a^2,...,a^{\delta_m(a)}\)模\(m\)两两不同余

2. 若\(a^n\equiv 1\pmod m\),则\(\delta_m(a)\mid n\)
   推论1:若\(a^p\equiv a^q\),则有\(p\equiv q \pmod{\delta_m(a)}\)
   推论2:若\(gcd(a,m)=1\),\(\delta_m(a)\mid\varphi(m)\)

3. 设\(m\in\mathbb{N^* },a,b\in\mathbb{Z},gcd(a,m)=gcd(b,m)=1\),则\(\delta_m(a\cdot b)=\delta_m(a)\cdot \delta_m(b)\) 的充分条件是\(gcd(\delta_m(a),\delta_m(b))=1\)

4. 设\(k\in\mathbb{N},m\in\mathbb{N^* },a\in\mathbb{Z},gcd(a,m)=1\)，则\(\delta_m(a^k)=\frac{\delta_m(a)}{gcd(\delta_m(a),k)}\)

5. 若\(p\) 为素数，则\(\delta_p(g^i)=\delta_p(g)\)的充要条件为\(gcd(\delta_p(g),i)=1 (g\in\mathbb{N^* })\)。\(\\g^i\)也可以表示为\(g^{gcd(\delta_p(g),i)\cdot r} (r\in\mathbb{N^* })\)

原根

• 定义：设\(m\in\mathbb{N^* },a\in\mathbb{Z}\),若\(gcd(a,m)=1\),且\(\delta_m(a)=\varphi(m)\),则称\(a\)为\(m\)的原根

• 定理：

1. 原根判定定理：设\(m\geqslant3,gcd(a,m)=1\)，则\(a\)是模\(m\)的原根的充要条件是，对于\(\varphi(m)\)的每个素因数\(p\)，都有
   $a^{\frac{\varphi(m)}{p}}\not\equiv1\pmod m $

2. 原根个数：若一个数\(m\)有原根，则它原根的个数为\(\varphi(\varphi(m))\)

3. 原根存在定理：
   引理1：设\(a\)与\(b\)是与\(p\)互素的两个整数，则存在\(c\in\mathbb{Z}\)使得\(\delta_p(c)=lcm(\delta_p(a),\delta_p(b))\)
   定理1：一个数\(m\)存在原根当且仅当\(m=2,4,p^\alpha,2\cdot p^\alpha\)，其中\(p\)为奇素数，\(\alpha\in\mathbb{N^* }\)
   引理2：存在模\(p\)的原根\(g\)，使得\(g^{p-1}\not\equiv1\pmod{p^2}\)
   定理2：对于奇素数\(p,\alpha\in\mathbb{N^* }\)，\(p^\alpha\) 有原根
   定理3：对于奇素数\(p,\alpha\in\mathbb{N^* }\),\(2\cdot p^\alpha\) 的原根存在
   定理4：对于\(m\ne2,4\)，且不存在奇素数\(p\)及\(\alpha\in\mathbb{N^* }\)使得\(m=p^\alpha,2\cdot p^\alpha\)，模\(m\)的原根不存在

4. 若\(gcd(g,n)\)且(n>0)，则\(g\)为\(n\)的一个原根的充要条件为\(S=\{g^1,g^2...g^{\varphi(n)}\}\)为\(n\)的一组简化剩余系

5. 若奇素数\(p\)的原根\(g\)满足\(g^{p-1}\not\equiv1\pmod {p^2}\)，则对于每一个\(a\geqslant2\)，有\(g^{\varphi(p^{a-1})}\not\equiv1\pmod {p^a}\)

6. 若\(p\)为素数，\(a\)为整数且\(p\nmid a\)，则在一个模\(p\)的完全剩余系中恰有\(\varphi(\delta_p(a))\)个数模\(p\)的阶为\(\delta_p(a)\)

7. 对于任意整数\(h\)使得\(\delta_p(h)=\delta_p(a)\)，定存在\(a^{d_i} (i\in[1,\varphi(\delta_p(a))\cap\mathbb{Z}])\)在模\(p\)意义下与\(h\)同余

8. 若\(p\)为整数且有一个原根\(g\)，则\(p\)恰有\(\varphi(\varphi(p))\)个在模\(p\)意义下不同余的原根，它们由集合\(S=\{g^i|1\leqslant i\leqslant\varphi(p),gcd(p,i)=1\}\)中的数给出