指数

作者: 洛玖言 | 来源:发表于2019-11-03 22:15 被阅读0次

第三章原根和指数

指数

模 $m$ 的指数

设模 $m$ 有原根 $g$ ，则 $1,g,\cdots,g^{\varphi(m)-1}$ 为模 $m$ 的缩系，所以对每个与 $m$ 互素的整数 $a$ ，必存在唯一的整数 $k,\,0\leqslant k\leqslant\varphi(m)-1$ ，使得
$a\equiv g^k\pmod{m}$

上诉的 $k$ 称为 $a$ 对于原根 $g$ 模 $m$ 的指数，记作 $k=\text{ind}_g\;a$ ，在不引起混淆时，可以简记为 $\text{ind}\;a$ .

模 $m$ 的 $k$ 次剩余

同余方程
$x^k\equiv a\pmod{m}\quad(1)$
其中 $k\geqslant2,\,(a.m)=1$ . 如果同余方程 (1) 有解，则称 $a$ 是模 $m$ 的 $k$ 次剩余，否则称 $a$ 是模 $m$ 的 $k$ 次非剩余.

定理1

设 $g$ 是模 $m$ 的原根， $(a,m)=(b,m)=1$ . 则

(i) $\text{ind}\;1=0$ 及 $\text{ind}\;g=1$
(ii) $\text{ind}\;(ab)\equiv\text{ind}\;a+\text{ind}\;b \pmod{\varphi(m)}$
(iii) $\text{ind}\;a^n\equiv n\;\text{ind}\;a\pmod{\varphi(m)}$ ，其中 $n\geqslant1$
(iv) 如果 $g_1$ 也是模 $\mod{m}$ 的原根，则
$\text{ind}_g\;a\equiv\text{ind}_{g_1}\;a\cdot\text{ind}_g\;g_1\pmod{\varphi(m)}$ ;
(v) $a\equiv b\pmod{m}$ 的充分必要条件是 $\text{ind}\;a=\text{ind}\;b$

定理2

设模 $m$ 存在原根， $k\geqslant2,\,(a,m)=1,\,d=(k,\varphi(m))$ . 则
(i) 同余方程 $x^k\equiv a\pmod{m}$ 有解的充分必要条件是 $d|\text{ind}_g\;a$ 其中 $g$ 是模 $m$ 的一个原根；这等价于
$\displaystyle a^{\frac{\varphi(m)}{d}}\equiv1\pmod{m}$
(ii) 在 (i) 中条件满足时，同余方程 $x^k\equiv a\pmod{m}$ 模 $m$ 共有 $d$ 个解.
(iii) 模 $m$ 的缩系中恰有 $\dfrac{\varphi(m)}{d}$ 个 $k$ 次剩余.

整数与多项式-【目录】

指数

第三章原根和指数

指数

模 $m$ 的指数

模 $m$ 的 $k$ 次剩余

定理1

定理2

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

指数

第三章 原根和指数

指数

模 的指数

模 的 次剩余

定理1

定理2

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第三章原根和指数

模 $m$ 的指数

模 $m$ 的 $k$ 次剩余