第10节　求原根的方法

73

求原根的方法大部分可以归结为试错法。如果把条目55中阐述的内容与后面关于解同余方程xn≡1的内容结合起来，那么，这基本上就是通过直接法所能完成的一切了。欧拉（参见Opuscula Analytica，第1版，152页）承认，挑选出这些数是极其困难的，它们的性质是数的性质里最神秘的。但是，通过以下的方法可以轻而易举地确定它们。熟练的数学家们知道如何通过各种手段简化繁琐的计算过程，就这一点来说，个人的经验比书本的说教更管用。

1．随意选取一个与模p（我们总是用p这个字母代表模）互质的数a。通常情况下，如果我们能够选出最小的数，就能简化计算——例如，选取数2。接下来确定它的周期（参考条目46），即，依次计算它的各次幂的最小剩余直至出现最小剩余等于1^[3]的幂at，如果t＝p-1，则a是原根。

2．然而，如果t＜p-1，那么选取另一个包含在a的周期内的数b，并且通过同样的方法找出它的周期。如果我们用u表示b所属的指数，我们发现u不可能等于t或者是t的因数；

因为，只要u等于t或者t的因数，就有bt≡1；这是不可能的，因为a的周期中已经包含了所有t次幂同余于1的数（参考条目53）。如果u＝p-1，b就是一个原根；但是，如果u≠p-1，而u是t的倍数，那么，我们就得到了一个数，它属于更大的指数，因而我们就更接近找到一个属于最大的

指数的数的目标。如果u≠p-1，u也不是t的倍数，那么，我们一定能找到一个数，它所属的指数大于t和u，即指数等于t和u的最小公倍数。令这个公倍数为y，并将y分解为两个互质的因数m和n，并使得它们中的一个整除t，另一个整除u^[4]。结果，atm≡A，bun≡B（mod p），并且乘积AB属于指数y。因为，A属于指数m，B属于指数n；且m和n互质，乘积AB就属于指数mn。我们可以用与条目55中第2部分的证明几乎同样的方法证明之。

3．如果y＝p-1，AB就是原根；如果y≠p-1，我们就像前面一样，需要再取另一个不在AB的周期中出现的数。这个数要么是原根，要么就属于一个大于y的指数，或者我们可以利用它（像之前一样）找到一个所属指数大于y的数。因为我们通过重复这样的做法所得到的这些数是属于严格递增的指数，所以我们最后一定可以找到一个属于最大指数的数。这个数就是原根。这就是需要做的。

74

举一个例子可以让上面的做法更加清楚。令p＝73，我们来求它的原根。我们首先来试验数2，它的周期是

1，2，4，8，16，32，64，55，37，1，…

0，1，3，4，5，6，7，8，9，…

因为2的9次幂同余于1，所以2不是原根。我们来试验一个不出现在这个周期里的数——比如3。它的周期是

1，3，9，27，8，24，72，70，64，46，65，49，1，…

0，1，2，3，4，5，6，7，8，9，10，11，12，…

所以3不是原根。但是2和3所属的指数（数9和12）的最小公倍数是36，按照上一条目我们将其分解为因数9和4的乘积。取2的9/9次幂，3的12/4次幂，我们得到乘积54，它属于指数36。如果我们最后计算54的周期，并尝试一个不含在这个周期中的数（例如5），我们会发现它是一个原根。