第10節(jié)　求原根的方法

73

求原根的方法大部分可以歸結(jié)為試錯(cuò)法。如果把條目55中闡述的內(nèi)容與后面關(guān)于解同余方程xn≡1的內(nèi)容結(jié)合起來(lái)，那么，這基本上就是通過(guò)直接法所能完成的一切了。歐拉（參見(jiàn)Opuscula Analytica，第1版，152頁(yè)）承認(rèn)，挑選出這些數(shù)是極其困難的，它們的性質(zhì)是數(shù)的性質(zhì)里最神秘的。但是，通過(guò)以下的方法可以輕而易舉地確定它們。熟練的數(shù)學(xué)家們知道如何通過(guò)各種手段簡(jiǎn)化繁瑣的計(jì)算過(guò)程，就這一點(diǎn)來(lái)說(shuō)，個(gè)人的經(jīng)驗(yàn)比書本的說(shuō)教更管用。

1．隨意選取一個(gè)與模p（我們總是用p這個(gè)字母代表模）互質(zhì)的數(shù)a。通常情況下，如果我們能夠選出最小的數(shù)，就能簡(jiǎn)化計(jì)算——例如，選取數(shù)2。接下來(lái)確定它的周期（參考條目46），即，依次計(jì)算它的各次冪的最小剩余直至出現(xiàn)最小剩余等于1^[3]的冪at，如果t＝p-1，則a是原根。

2．然而，如果t＜p-1，那么選取另一個(gè)包含在a的周期內(nèi)的數(shù)b，并且通過(guò)同樣的方法找出它的周期。如果我們用u表示b所屬的指數(shù)，我們發(fā)現(xiàn)u不可能等于t或者是t的因數(shù)；

因?yàn)椋灰?span id="ld9vh5i" class="kindle-cn-italic">u等于t或者t的因數(shù)，就有bt≡1；這是不可能的，因?yàn)?span id="ngq8f6c" class="kindle-cn-italic">a的周期中已經(jīng)包含了所有t次冪同余于1的數(shù)（參考條目53）。如果u＝p-1，b就是一個(gè)原根；但是，如果u≠p-1，而u是t的倍數(shù)，那么，我們就得到了一個(gè)數(shù)，它屬于更大的指數(shù)，因而我們就更接近找到一個(gè)屬于最大的

指數(shù)的數(shù)的目標(biāo)。如果u≠p-1，u也不是t的倍數(shù)，那么，我們一定能找到一個(gè)數(shù)，它所屬的指數(shù)大于t和u，即指數(shù)等于t和u的最小公倍數(shù)。令這個(gè)公倍數(shù)為y，并將y分解為兩個(gè)互質(zhì)的因數(shù)m和n，并使得它們中的一個(gè)整除t，另一個(gè)整除u^[4]。結(jié)果，atm≡A，bun≡B（mod p），并且乘積AB屬于指數(shù)y。因?yàn)椋?span id="qq0r9kk" class="kindle-cn-italic">A屬于指數(shù)m，B屬于指數(shù)n；且m和n互質(zhì)，乘積AB就屬于指數(shù)mn。我們可以用與條目55中第2部分的證明幾乎同樣的方法證明之。

3．如果y＝p-1，AB就是原根；如果y≠p-1，我們就像前面一樣，需要再取另一個(gè)不在AB的周期中出現(xiàn)的數(shù)。這個(gè)數(shù)要么是原根，要么就屬于一個(gè)大于y的指數(shù)，或者我們可以利用它（像之前一樣）找到一個(gè)所屬指數(shù)大于y的數(shù)。因?yàn)槲覀兺ㄟ^(guò)重復(fù)這樣的做法所得到的這些數(shù)是屬于嚴(yán)格遞增的指數(shù)，所以我們最后一定可以找到一個(gè)屬于最大指數(shù)的數(shù)。這個(gè)數(shù)就是原根。這就是需要做的。

74

舉一個(gè)例子可以讓上面的做法更加清楚。令p＝73，我們來(lái)求它的原根。我們首先來(lái)試驗(yàn)數(shù)2，它的周期是

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

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

因?yàn)?的9次冪同余于1，所以2不是原根。我們來(lái)試驗(yàn)一個(gè)不出現(xiàn)在這個(gè)周期里的數(shù)——比如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所屬的指數(shù)（數(shù)9和12）的最小公倍數(shù)是36，按照上一條目我們將其分解為因數(shù)9和4的乘積。取2的9/9次冪，3的12/4次冪，我們得到乘積54，它屬于指數(shù)36。如果我們最后計(jì)算54的周期，并嘗試一個(gè)不含在這個(gè)周期中的數(shù)（例如5），我們會(huì)發(fā)現(xiàn)它是一個(gè)原根。