模m的n次剩余与非剩余

阅读量：

索引

传送门
- 定义1 设 $m\in {{\mathbb{Z}}_{>0}}$ 存在原根, $a\in \mathbb{Z}$ , $\gcd \left( a,m \right)=1$ , $n\in {{\mathbb{Z}}_{>0}}$ . 若方程 ${{x}^{n}}\equiv a\text{ }\bmod m$ 具有解, 则称 $a$ 为模 $m$ 的 $n$ 次剩余; 若该方程无解, 则称 $a$ 为模 $m$ 的 $n$ 次非剩余.
- 定理2 设 $m\in {{\mathbb{Z}}_{>0}}$ 存在原根 $r$ , $a\in \mathbb{Z}$ , $\gcd \left( a,m \right)=1$ , 则成立等价关系：若 $a是模m的n次剩余$ , 等价于 $\gcd \left( n,\varphi \left( m \right) \right)$ 整除 $\text{in}{{\text{d}}_{r}}\left( a \right)$ , 等价于 ${{a}^{\frac{\varphi \left( m \right)}{\gcd \left( n,\varphi \left( m \right) \right)}}}\equiv 1\text{ }\bmod m.$
- 推论3 设 $m\in {{\mathbb{Z}}_{>0}}$ , 在模 $m$ 的一个既约剩余

还没有任何评论哟~