第14節(jié)　模為2的方冪

90

如果取2的高于二次的某個方冪2n作為模，則任意奇數(shù)的2n-2次冪就同余于1。

例如，38＝6561≡1（mod 32）。

因為，任意奇數(shù)都形如1＋4h或者形如-1＋4h，于是可以立刻推出這個命題（條目86中的定理）。

因此，由于奇數(shù)對于模2n所屬的指數(shù)一定是2n-2的除數(shù)，容易判斷這個奇數(shù)屬于指數(shù)1，2，4，8，…2n-2中的哪一個。假如所給的數(shù)為4h±1，整除h的2的最高次冪的指數(shù)為m（m可以等于0，因為h可以是奇數(shù)）；那么，當(dāng)n＞m＋2時，所給的數(shù)所屬的指數(shù)就為2n-m-2；但是，當(dāng)n等于或小于m＋2時，則所給的這個數(shù)同余于±1，因而，它所屬的指數(shù)就是1或2。從條目86容易推出，形如±1＋2m＋2k的數(shù)（它等價于4h±1的形式），如果自乘到2n-m-2次冪，對于模2n同余于1；如果自乘到2的較低次冪，它就不同余于1。因此，任何形如8k＋3或8k＋5的數(shù)就屬于指數(shù)2n-2。

91

由此可以推出，在這種情況下，不存在上文定義下的原根；即，不存在這樣的數(shù)，使得其周期中包含了所有小于模且與模互質(zhì)的數(shù)。可以發(fā)現(xiàn)，對于形如8k＋3的數(shù)，其奇數(shù)次冪也是形如8k＋3的數(shù)，其偶數(shù)次冪是形如8k＋1的數(shù)；不存在形如8k＋5或8k＋7的方冪。因為，對于形如8k＋3的數(shù)，它的周期是由不同的2n-2項形如8k＋3或8k＋1的數(shù)組成，小于模的這樣的數(shù)也不會超過2n-2個。顯然，任何形如8k＋1或8k＋3的數(shù)都對于模2n同余于形如8k＋3的一個數(shù)的方冪。通過類似的方法我們可以證明，一個形如8k＋5的數(shù)的周期包含了所有形如8k＋1和8k＋5的數(shù)。因此，如果取一個形如8k＋5的數(shù)作為基數(shù)，將所有形如8k＋1和8k＋5的數(shù)取正號，并且將所有形如8k＋3和8k＋7的數(shù)取負(fù)號后，我們都可以求得它們真實的指標(biāo)。而且，我們必須將對于模2n-2同余的指標(biāo)視為等價的指標(biāo)。表1應(yīng)當(dāng)從這個角度來理解，在表1中對于模16，32和64，總是取5作為基數(shù)（對于模8不需要表）。例如，數(shù)19是形如8n＋3的數(shù)，因而我們必須對其取負(fù)號；對于模64，它的指標(biāo)是7。這就意味著57≡-19（mod 64）。如果我們對形如8n＋1和8n＋5的數(shù)取負(fù)號，并且對形如8n＋3和8n＋7的數(shù)取正號，那么，我們就要給它們賦予所謂的虛指標(biāo)。如果我們這樣做，指標(biāo)的計算法則就可以得到簡化。但是，如果我們極其嚴(yán)格地討論這一點，就會跑題；所以，我們把這一點放在其他場合——當(dāng)我們或許能夠更深入地討論虛量理論的時候再來討論。在我們看來，到目前為止還沒有人明確地提出了關(guān)于這一點的處理方法。有經(jīng)驗的數(shù)學(xué)家會發(fā)現(xiàn)開發(fā)算法很容易。對于經(jīng)驗較少的人，只要他們掌握好上文中討論的原理，可以利用我們的表格。這就類似于對于當(dāng)代虛對數(shù)的研究一無所知的人可以運用對數(shù)運算一樣。

92

對于由若干個質(zhì)數(shù)合成的模，幾乎所有關(guān)于冪剩余的結(jié)論都可由一般的同余理論來推出。我們后面會更加詳細(xì)地討論如何將對于若干個質(zhì)數(shù)合成的模的同余式簡化為對于模為質(zhì)數(shù)或者質(zhì)數(shù)冪的同余式。因此，關(guān)于這個話題我們不再作更多討論。我們這里只是指出一個對于質(zhì)數(shù)或質(zhì)數(shù)冪的模有而對于其他模沒有的一個優(yōu)雅的性質(zhì)：我們總是可以找到這樣一個數(shù)，它的周期中包含所有與模互質(zhì)的數(shù)。但是，有一種情況除外，即使在這里我們也能求得一個數(shù)。這種情況出現(xiàn)在當(dāng)模是質(zhì)數(shù)的兩倍，或者是質(zhì)數(shù)的冪的兩倍之時。因為，如果模m可以簡化為AaBbCc…的形式，其中A，B，C，…是各不相同的質(zhì)數(shù)，如果我們用α代表Aa-1（A-1），用β代表Bb-1（B-1），…，然后選擇一個與m互質(zhì)的數(shù)z，我們得到zα≡1（mod Aa），zβ≡1（mod Bb），…。并且，如果μ是數(shù)α，β，γ，…的最小公倍數(shù)，那么對于所有的模Aa，Bb，…，我們有zμ≡1；因而對于它們的乘積m也成立。但是，m是質(zhì)數(shù)的兩倍或者質(zhì)數(shù)冪的兩倍的情況除外，此時數(shù)α，β，γ，…的最小公倍數(shù)總是小于它們的乘積（因為數(shù)α，β，γ，…不可能互質(zhì)，它們有公約數(shù)2）。因此，不存在這樣的周期，它包含的項數(shù)同與模互質(zhì)且小于模的數(shù)的個數(shù)一樣多，因為后者的個數(shù)等于數(shù)α，β，γ，…的乘積。例如，對m＝1001，每一個與m互質(zhì)的數(shù)的60次冪必同余于1，因為數(shù)6，10，12的最小公倍數(shù)是60。在模是兩倍的質(zhì)數(shù)或兩倍的質(zhì)數(shù)冪的情況完全與模是質(zhì)數(shù)或質(zhì)數(shù)冪的情況相同。

93

我們已經(jīng)提到了其他數(shù)學(xué)家關(guān)于本章相同主題的著作。對于想要對本主題有更加詳細(xì)的討論的讀者，我們推薦下列歐拉的論文，這些論文的清晰度和洞察力都使得這位偉大的數(shù)學(xué)家領(lǐng)先于其他評論者：

Theoremata circa residua ex divisione potestatum relica，見Novi. comm. acad. Petrop，7［1758-1759］，1761，49-82。

Demonstrationes circa residua ex divisione potestatum per numeros primos resultantia，ibid.，18［1773］，1774，85-135。

此外，還有他的著作Opuscula Analytica的論文5，第152頁；論文8，第242頁。

---

[1] 第8章未發(fā)表，見作者自序。

[2] 但是，它們的不同之處在于，對于對數(shù)來說，不同的系統(tǒng)有無限個，而這里系統(tǒng)的個數(shù)就等于原根的個數(shù)。因為，顯然，相互同余的基數(shù)產(chǎn)生的系統(tǒng)也是相同的。

[3] 沒有必要知道這些方冪本身的值，因為每一個方冪的最小剩余可以輕易地通過前一個方冪的最小剩余來得到。

[4] 由條目18，我們能看出如何輕松地做到這一點。把y分解為因數(shù)不同的質(zhì)數(shù)或質(zhì)數(shù)的方冪的乘積。每一個因數(shù)將整除t或者u（或者同時整除兩者）。考察這些因數(shù)是整除t還是整除u，來指定它們分別屬于哪一個；如果同時整除兩者，則可任意指定。令所有指定屬于t的因數(shù)的乘積為m，其他因數(shù)的乘積等于n，顯然，m整除t，n整除u，且mn＝y。

[5] 拉格朗日參考的是1770年第1版的第218頁。

[6] 第125頁。

[7] 這樣確定數(shù)a，b，c，…，使得a≡1（mod aα）且a≡0（mod bβcγ…）；b≡1（mod bβ）且b≡0（mod aαcγ…）；…（參考條目32）。因而，a-b＋c≡1（mod p-1）（參考條目19）。現(xiàn)在，如果任意原根r表示為乘積ABC…的形式，我們就有A≡ra，B≡rb，C≡rc，…；并且A就屬于aα的指數(shù)，B屬于bβ的指數(shù)，…，那么，A，B，C…的乘積就同余于r（mod p）；顯然，A，B，C，…不能用任何其他方式來確定。