原根

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

第三章原根和指数

原根

阶

对与 $m$ 互素的整数 $a$ ，满足 $a^n\equiv1\pmod{m}$ 的最小正整数 $n$ ，称为 $a$ 模 $m$ 的阶.

显然， $a$ 模 $m$ 的阶为 $n$ ，等价于说在乘法群 $\mathbf{Z}^{*}$ 中， $n$ 是最正整数使 $\bar{a}^n=\bar{1}$

由欧拉定理及引理1(ii) 可见，对于每个与 $m$ 互素的 $a$ ，模 $m$ 的阶数都是 $\varphi(m)$ 的某个约数，从而阶的值不超过 $\varphi(m)$ .

模 $m$ 有原根

如果存在整数 $g,\,(g,m)=1$ ，使 $g$ 模 $m$ 的阶恰是 $\varphi(m)$ ，则称模 $m$ 有原根，并称 $g$ 是模 $m$ 的一个原根. 很明显，如 $g$ 是模 $m$ 的原根，则模 $m$ 的同余类 $\bar{g}$ 中所有数均是模 $m$ 的原根.

若模 $m$ 存在原根 $g$ ，则模 $m$ 的缩系呈现特别简单的结构. 因为，由引理1(ii)推出， $g^0-1,g,\cdots,g^{\varphi(m)-1}$ 彼此模 $m$ 不同余，并且均与 $m$ 互素，从而这 $\varphi(m)$ 个成几何级数的数形成模 $m$ 的一个缩系.

换一个角度说，模 $m$ 存在原根 $g$ ，等价于乘法群

$\displaystyle\mathbf{Z}^{*}=\{\bar{1},\bar{g},\cdots,\bar{g}^{\varphi(m)-1}\},$
即 $\mathbf{Z}^{*}$ 由一个元 $\bar{g}$ “生成”. 这样的群，称为循环群，这是代数结构最为简单的一类群.

引理1

设 $(a,m)=1$ ，则
(i) 存在正整数 $n,1\leqslant n<m$ ，使 $a^n\equiv1\pmod{m}$ ;
(ii) 设 $n$ 为（i）中最小的正整数，则对整数 $k$ 和 $l$ ，同余式 $a^k\equiv a^l\pmod{m}$ 成立的充分必要条件是 $l\equiv k\pmod{n}$ . 特别地， $a^k\equiv 1\pmod{m}$ 成立的充分必要条件为 $n|k$

引理2

设 $m\not=2,\,4,\,p^l$ 或 $2p^l$ （ $p$ 是奇素数， $l\geqslant1$ ），则模 $m$ 没有原根.

定理1

对于每个奇素数 $p$ ，模 $p$ 有原根.

引理3

设 $(a,m)=1$ , $a$ 模 $m$ 的阶为 $n$ ，则 $a^k$ 模 $m$ 的阶是 $\dfrac{n}{(k,n)}$ . 特别地， $a^k$ 模 $m$ 的阶为 $n$ 的充分必要条件是 $(k,n)=1$ .

定理2

设 $p$ 是奇素数，则对 $l\geqslant2$ ，模 $p^l$ 必有原根.

定理3

设 $p$ 是奇素数，整数 $l\geqslant1$ ，则模 $2p^l$ 必有原根.

定理4

设 $m$ 为大于1的整数，则模 $m$ 有原根的充分必要条件是 $m=2,\,4,\,p^l$ 或（原书上这里用“和”，但是个人感觉不合适） $2p^l$ ，其中 $p$ 是奇素数，而 $l\geqslant1$ .

进一步，对这些 $m$ ，设正整数 $d$ 是 $\varphi(m)$ 的一个约数， $g$ 是模 $m$ 的一个原根，则模 $m$ 共有 $\varphi(d)$ 个（互不同余的）阶为 $d$ 的数，它们是
$\displaystyle\{g^{\frac{\varphi(m)}{d}k}|1\leqslant k\leqslant d,\quad(k,d)=1\}$

整数与多项式-【目录】

原根

第三章原根和指数

原根

阶

模 $m$ 有原根

引理1

引理2

定理1

引理3

定理2

定理3

定理4

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

原根

第三章 原根和指数

原根

阶

模 有原根

引理1

引理2

定理1

引理3

定理2

定理3

定理4

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第三章原根和指数

模 $m$ 有原根