第三章 原根和指数

原根

阶

对与 互素的整数 ，满足 的最小正整数 ，称为 模 的阶.

显然， 模 的阶为 ，等价于说在乘法群 中， 是最正整数使

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

模 有原根

如果存在整数 ，使 模 的阶恰是 ，则称模 有原根，并称 是模 的一个原根. 很明显，如 是模 的原根，则模 的同余类 中所有数均是模 的原根.

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

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

即 由一个元 “生成”. 这样的群，称为循环群，这是代数结构最为简单的一类群.

引理1

设 ，则
(i) 存在正整数 ，使 ;
(ii) 设 为（i）中最小的正整数，则对整数 和 ，同余式 成立的充分必要条件是 . 特别地， 成立的充分必要条件为

引理2

设 或 （ 是奇素数，），则模 没有原根.

定理1

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

引理3

设 , 模 的阶为 ，则 模 的阶是 . 特别地， 模 的阶为 的充分必要条件是 .

定理2

设 是奇素数，则对 ，模 必有原根.

定理3

设 是奇素数，整数 ，则模 必有原根.

定理4

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

进一步，对这些 ，设正整数 是 的一个约数， 是模 的一个原根，则模 共有 个（互不同余的）阶为 的数，它们是

整数与多项式-【目录】