索引
- 传送门
- 定义1 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0有原根, a ∈ Z a\in \mathbb{Z} a∈Z, gcd ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1, n ∈ Z > 0 n\in { {\mathbb{Z}}_{>0}} n∈Z>0. 若 x n ≡ a m o d m { {x}^{n}}\equiv a\text{ }\bmod m xn≡a modm有解, 则称 a a a为模 m m m的 n n n次剩余; 若 x n ≡ a m o d m { {x}^{n}}\equiv a\text{ }\bmod m xn≡a modm无解, 则称 a a a为模 m m m的 n n n次非剩余.
- 定理2 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0有原根 r r r, a ∈ Z a\in \mathbb{Z} a∈Z, gcd ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1, 则成立等价关系 a 是 模 m 的 n 次 剩 余 . ⇔ gcd ( n , φ ( m ) ) ∣ in d r ( a ) . ⇔ a φ ( m ) gcd ( n , φ ( m ) ) ≡ 1 m o d m . a是模m的n次剩余.\text{ }\Leftrightarrow \text{ }\left. \gcd \left( n,\varphi \left( m \right) \right) \right|\text{in}{ {\text{d}}_{r}}\left( a \right)\text{. }\Leftrightarrow \text{ }{ {a}^{\frac{\varphi \left( m \right)}{\gcd \left( n,\varphi \left( m \right) \right)}}}\equiv 1\text{ }\bmod m. a是模m的n次剩余. ⇔ gcd(n,φ(m))∣indr(a). ⇔ agcd(n,φ(m))φ(m)≡1 modm.
- 推论3 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0, 在模 m m m的一个既约剩余系中, 有 φ ( m ) gcd ( n , φ ( m ) ) \frac{\varphi \left( m \right)}{\gcd \left( n,\varphi \left( m \right) \right)} gcd(n,φ(m))φ(m)个 n n n次剩余 (针对 n n n次剩余的个数).
- 推论4 p p p是奇素数, 则在模 p p p的一个既约剩余系中有 p − 1 2 \frac{p-1}{2} 2p−1个 2 2 2次剩余.
- 定理5 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0, a ∈ Z a\in \mathbb{Z} a∈Z, gcd ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1, 若 a a a是模 m m m的 n n n次剩余, 则 x n ≡ a m o d m { {x}^{n}}\equiv a\text{ }\bmod m xn≡a modm有 gcd ( n , φ ( m ) ) \gcd \left( n,\varphi \left( m \right) \right) gcd(n,φ(m))个解 (针对方程解的个数).
- 定理6 (指数公式) 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0有原根 r r r, a ∈ Z a\in \mathbb{Z} a∈Z, gcd ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1, 则 a a a对模 m m m的指数为 φ ( m ) gcd ( in d r ( a ) , φ ( m ) ) . \frac{\varphi \left( m \right)}{\gcd \left( \text{in}{ {\text{d}}_{r}}\left( a \right),\varphi \left( m \right) \right)}. gcd(indr(a),φ(m))φ(m).
- 推论7 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0有原根 r r r, a ∈ Z a\in \mathbb{Z} a∈Z, gcd ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1, 则 a a a是模 m m m的原根当且仅当 gcd ( in d r ( a ) , φ ( m ) ) = 1. \gcd \left( \text{in}{ {\text{d}}_{r}}\left( a \right),\varphi \left( m \right) \right)=1. gcd(indr(a),φ(m))=1.
- 定理8 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0有原根, δ ∈ Z > 0 \delta \in { {\mathbb{Z}}_{>0}} δ∈Z>0且 δ ∣ φ ( m ) \left. \delta \right|\varphi \left( m \right) δ∣φ(m), 则成立 ∣ { a ∈ Z : 1 ≤ a < m , gcd ( a , m ) = 1 , a 对 模 m 的 指 数 = δ } ∣ = φ ( δ ) . \left| \left\{ a\in \mathbb{Z}:\text{ }1\le a<m,\text{ }\gcd \left( a,m \right)=1,\text{ }a对模m的指数=\delta \right\} \right|=\varphi \left( \delta \right). ∣{ a∈Z: 1≤a<m, gcd(a,m)=1, a对模m的指数=δ}∣=φ(δ).
- 推论9 设 m ∈ Z > 0 m\in { {\mathbb{Z}}_{>0}} m∈Z>0有原根, 则 m m m的原根有 φ ( φ ( m ) ) \varphi \left( \varphi \left( m \right) \right) φ(φ(m))个.
- 定理10 设 q 1 , q 2 , ⋯ , q s { {q}_{1}},{ {q}_{2}},\cdots ,{ {q}_{s}} q1,q2,⋯,qs是 φ ( m ) \varphi \left( m \right) φ(m)的一切不同的素因数, 则 g g g是模 m m m的一个原根的充分必要条件是 g g g是对模 m m m的 q i ( i = 1 , 2 , ⋯ , s ) { {q}_{i}}\left( i=1,2,\cdots ,s \right) qi(i=1,2,⋯,s)次非剩余.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/34999.html