下载掌阅APP，畅读海量书库
立即打开
什么样的正整数具有原根？
设 a 和 m 是互素的正整数，考虑 a 的所有方幂 a ， a 2 ， a 3 ，…除以 m 后所得的余数。因为一个数除以 m 所得的余数只能是0，1，…， m -1中之一，故存在两个不同的方幂 a i 和 a j 。不妨设 i < j ，使得 m 整除 a j - a i = a i （ a j - i -1）。根据 m 和 a 互素的假定，可知 m 整除 a j - i -1。由此证明了只要 a 和 m 互素，就存在一个正整数 k 使得 a k ≡1（mod m ）。把这个最小的 k 称为 a 模 m 的阶，或者称为 a 关于 m 的指数。
a 模 m 的阶 k 应该是什么样子的呢？假如还有 a n ≡1（mod m ）。设 n 除以 k 的余数为 r ，即可令 n = kq + r ，其中0≤ r < k ，则
a r = a n - kq = a n a - kq ≡1（mod m ）。
根据 k 的极小性推出 r =0，表明 k 整除 n 。这实际上给出了阶的一个刻画，即 k 为 a 模 m 的阶当且仅当 a k ≡1（mod m ），以及对任意 a n ≡1（mod m ），总有 k 整除 n 。
特别地，根据问题016中提及的欧拉定理，当 a 和 m 为互素的正整数时，总有 m 整除 a φ （ m ） -1，写成同余式即为 a φ （ m ） ≡1（mod m ），其中 φ （ m ）为欧拉函数。由此表明 a 模 m 的阶必然整除 φ （ m ），亦即为 φ （ m ）的一个因子。从此引出一个最为基本的问题：在什么条件下 a 模 m 的阶恰好等于 φ （ m ）呢？
如果 a 模 m 的阶恰好等于 φ （ m ），则称 a 为 m 的一个原根。现在的问题是：什么样的正整数 m 有原根，以及在原根存在的情形下如何求出其所有的原根。这个问题之所以特别重要，原因在于对具有原根为 a 的正整数 m 而言， a 的 φ （ m ）个方幂 a ， a 2 ，…， a φ （ m ） 除以 m 所得的余数恰好就是小于 m 且与 m 互素的全部正整数。换句话说，那些与 m 互素的每个正整数必然与 a ， a 2 ，…， a φ （ m ） 中的某一个模 m 同余，这在整除理论中当然是一种理想情形。
并不是每个正整数都有原根。例如，取 m =8，直接计算可知3，5，7分别模8的阶都是2，而 φ （8）=4，表明8没有原根。
然而，欧拉在1773年首先证明了每个素数 p 都有原根。为了介绍欧拉的这个证明，需要下述两个基本结论。在给出这两个基本结论之前，有必要介绍同余方程解的一个性质。如果 x 是同余方程 f （ x ）≡0（mod m ）的一个解，且 x 除以 m 后所得的余数为 r ，亦即存在 k 使得 x = km + r （0≤ r < m ），根据二项展开公式显然有 f （ km + r ）≡ f （ r ）（mod m ），从而 f （ r ）≡0（mod m ），这表明 r 也是同余方程 f （ x ）≡0（mod m ）的解。基于同余方程解的这一性质，在讨论同余方程 f （ x ）≡0（mod m ）的解时，可以把解局限在模 m 的简化剩余系中，亦即在模 m 所得的全部余数0，1，…， m -1中，谈论解的存在性以及解的个数等问题。
（1）设 f （ x ）为 n 次整系数多项式，则同余方程
f （ x ）≡0（mod p ）
至多有 n 个解。
此即所谓的拉格朗日定理，是拉格朗日在1770年首先证明的。现在，对多项式的次数作归纳来证明该结论。令
f （ x ）= a n x n + a n -1 x n -1 +…+ a 0
为整系数多项式，不妨设
a
n
0（mod
p
）。当
n
=1时，从（
a
1
，
p
）=1即知一次同余方程
a
1
x
+
a
0
≡0（mod
p
）只有一个解。假定该结论对
n
-1次多项式成立，考虑
n
次多项式
f
（
x
）。如果
f
（
x
）≡0（mod
p
）无解，则结论自然成立。如果
f
（
x
）≡0（mod
p
）有一个解
r
，即
f
（
r
）≡0（mod
p
），此时用
x
-
r
去除
f
（
x
）所得的余式恰为
f
（
r
），亦即存在整系数多项式
g
（
x
）满足
f （ x ）=（ x - r ） g （ x ）+ f （ r ）。
显然 f （ x ）≡（ x - r ） g （ x ）（mod p ），且 g （ x ）的次数是 n -1。因为 p 是素数，所以 f （ x ）≡0（mod p ）的全部解即为 r 和 g （ x ）≡0（mod p ）的所有解组成。根据归纳假设 g （ x ）≡0（mod p ）至多有 n -1个解，从而 f （ x ）≡0（mod p ）的解最多有 n 个。
（2）如果 d 是 p -1的一个因子，则 x d ≡1（mod p ）恰有 d 个解。
事实上，根据费马小定理可知对每个与 p 互素的正整数 a ，均有 p 整除 a p -1 -1，即同余方程 x p -1 ≡1（mod p ）恰有 p -1个解1，2，…， p -1。从条件 d 整除 p -1不难看出 x d -1也整除 x p -1 -1，故可令
x p -1 -1=（ x d -1） h （ x ）。
根据上述结论（1），同余方程 h （ x ）≡0（mod p ）最多有 p -1- d 个解。因此 x d ≡1（mod p ）至少也有 d 个解，再从结论（1）可知其恰好有 d 个解。
有了以上的准备工作，就可证明每个素数 p 均有原根。注意到
1，2，…， p -1
中的每个数模 p 的阶都整除 φ （ p ）= p -1，对 p -1的每个因子 d ，用 ψ （ d ）表示该 p -1个数中模 p 的阶等于 d 的那些数的个数，则有
现在比较
φ
（
d
）和
ψ
（
d
）的大小。对
p
-1的每个因子
d
，如果
ψ
（
d
）=0，则
ψ
（
d
）<
φ
（
d
）。如果
ψ
（
d
）
0，则存在一个模
p
的阶为
d
的正整数，设为
a
。显然阶为
d
的所有数都是同余方程
x d ≡1（mod p ）
的解，根据结论（2）知该方程恰好有 d 个解。因 a ， a 2 ，…， a d 模 p 两两不同，故为上述方程的全部解。由此表明凡阶为 d 的正整数均可写成 a 的方幂形式，易知 a k 的阶为 d 当且仅当（ d ， k ）=1，从而有 φ （ d ）个阶为 d 的方幂，所以 ψ （ d ）= φ （ d ）。总之，一般地证明了 ψ （ d ）≤ φ （ d ）。再根据欧拉函数的性质，有
所以，对每个
p
-1的因子
d
，均有
ψ
（
d
）=
φ
（
d
）。特别地，
ψ
（
p
-1）=
φ
（
p
-1）
0，这说明存在模
p
的阶为
p
-1的正整数，亦即
p
有原根。
一般地，高斯在1801年证明了一个正整数具有原根，当且仅当它形如？
1，2，4， pe ，2 pe ，
这里 p 为任意奇素数，而 e 为任意正整数。虽然高斯的这个证明同样初等且巧妙，但篇幅所限，就不再介绍了。
最后，关于原根问题提及一个著名的猜想。1927年，奥地利大数学家阿廷猜测：对每个不等于1、 p -1以及完全平方的正整数 a ，均存在无穷多个素数 p 以 a 为原根。这一猜想至今尚未得到证明。