第三章 原根和指数
原根
阶
对与 
互素的整数 
，满足 
的最小正整数 
，称为 模 的阶.
显然， 模 的阶为 ，等价于说在乘法群 
中， 是最正整数使 
由欧拉定理及引理1(ii) 可见，对于每个与 互素的 ，模 的阶数都是 )
的某个约数，从而阶的值不超过 .
模 有原根
如果存在整数 %3D1)
，使 
模 的阶恰是 ，则称模 有原根，并称 是模 的一个原根. 很明显，如 是模 的原根，则模 的同余类 
中所有数均是模 的原根.
若模 存在原根 ，则模 的缩系呈现特别简单的结构. 因为，由引理1(ii)推出，-1%7D)
彼此模 不同余，并且均与 互素，从而这 个成几何级数的数形成模 的一个缩系.
换一个角度说，模 存在原根 ，等价于乘法群
-1%7D%5C%7D%2C)
即 由一个元 “生成”. 这样的群，称为循环群，这是代数结构最为简单的一类群.
引理1
设 %3D1)
，则
(i) 存在正整数 
，使 ;
(ii) 设 为（i）中最小的正整数，则对整数 
和 
，同余式 
成立的充分必要条件是 
. 特别地，
成立的充分必要条件为 
引理2
设 
或 
（
是奇素数，
），则模 没有原根.
定理1
对于每个奇素数 ，模 有原根.
引理3
设 , 模 的阶为 ，则 
模 的阶是 %7D)
. 特别地， 模 的阶为 的充分必要条件是 %3D1)
.
定理2
设 是奇素数，则对 
，模 
必有原根.
定理3
设 是奇素数，整数 ，则模 必有原根.
定理4
设 为大于1的整数，则模 有原根的充分必要条件是 
或（原书上这里用“和”，但是个人感觉不合适） ，其中 是奇素数，而 .
进一步，对这些 ，设正整数 
是 的一个约数， 是模 的一个原根，则模 共有 )
个（互不同余的）阶为 的数，它们是
%7D%7Bd%7Dk%7D%7C1%5Cleqslant%20k%5Cleqslant%20d%2C%5Cquad(k%2Cd)%3D1%5C%7D)
整数与多项式-【目录】
