第7節　同余方程xn≡A的根

60

在條目31中，我們用一個特殊符號表示一次同余方程的根。接下來，我們使用另一個特殊符號來表示最簡高次同余方程的根。就如同表示方程xn＝A的根，加上模后，（mod p）就表示同余方程xn＝A（mod p）的任意根。我們將把它所能取到的對模p不同余的值稱為表達式（mod p）所取的值，因為所有對模同余的數是看作等價的（參考條目26）。顯然，如果A，B對于模p同余，則表達式（mod p）和表達式（mod p）是等價的。

現在，如果已經給定≡x（mod p），就有n·Ind x≡Ind A（mod p-1）。由上個條目的運算法則，從這個同余方程中可以推導出Ind x的值，并得到對應的x的值。不難發現，x所取的值的個數將和同余方程n·Ind x≡Ind A（mod p-1）的根的個數相同。顯然，當n與p-1互質時，只能取一個值。但是，當n，p-1有一個最大公約數δ，只要條件Ind A能夠被δ整除成立，Ind x就有δ個對模p-1不同余的值，因而有同樣多個對模p不同余的值；如果這個條件不成立，就沒有真實的值。

例：求表達式（mod 19）的值。我們必須求解同余方程15Ind≡Ind 11≡6（mod 18），求得3個值，Ind x≡4，10，16（mod 18），那么對應的x的值分別是6，9，4。

61

即使在有了必要的表格后使用這個方法有多么便捷，也不要忘了它只是間接的方法。因此，弄清楚直接方法解決這些問題有多么強大，是非常有用的。這里只討論從前幾章可以推導出的結論；需要更加深入研究的其他討論放到第8章^[1]進行。

從最簡單的情況A＝1開始討論，也就是求同余方程xn≡1（mod p）的根。在取某個原根作為基數以后，必定有n·Ind x≡0（mod p-1）。現在，如果n是與p-1互質的數，這個同余方程就只有一個根，即Ind x≡0（mod p-1）。在這種情況下，（mod p）只有一個唯一的值，即≡1。但是當數n，p-1有一個（最大）公約數δ，同余方程n·Ind x≡0（mod p-1）的完整解就是Ind x≡0（mod（p-1）/δ）（條目29），即，對于模p-1，Ind x應當與下面的數中的一個同余

也就是說，Ind x就有δ個對于模p-1不同余的值；所以，在這種情況下，x也取δ個不同的（對于模p互不同余）值。因此，我們看出表達式也有δ個不同的值，其指標恰好是上面所給出的那些值。因此，表達式（mod p）完全等價于（mod p）；也就是說，同余方程xδ≡1（mod p）與同余方程xn≡1有完全相同的根。但如果δ和n不相等，則前者的階數較低。

例（mod 9）有3個值，因為15和18的最大公約數是3；而且，它們也是表達式（mod 19）的值。這些值是1，7，11。

62

由簡化的方法可知，我們只要求解那些n是數p-1的因數的形如xn≡1的同余方程即可。后面我們會發現，盡管現在的結論還不足以證明這一點，但這種形式的同余方程可以進一步簡化，但是，當n＝2時，這種情況現在就可以處理。顯然，表達式的值只有＋1和-1，因為它的值不可能超過2個，并且除非模為2，＋1和-1總是不同余的；如果模為2，只能有1個值。可以推出，當m與（p-1）/2互質時，＋1和-1也將是表達式的值。如果所討論的模p使得（p-1）/2是質數，那么總將發生這樣的情況（如果恰有p-1＝2m，那么所有的數1，2，3，…，p-1都是根）。例如，當p＝3，5，7，11，23，47，59，83，107，…，作為推論可得，無論取哪個原根為基數，Ind（-1）≡（p-1）/2（mod p-1）。這是因為2 Ind（-1）≡0（mod p-1），所以，要么Ind（-1）≡0，要么Ind（-1）≡（p-1）/2（mod p-1）。但是，0總是＋1的指標，而＋1和-1總有不同的指標（除了p＝2的情況，這里不討論這種情況）。

63

在條目60中我們證明了表達式（mod p）要么有δ個不同的值，要么沒有任何值，其中δ表示數n和p-1的最大公約數。現在，我們已經證明當A≡1時，與是等價的，更一般地，我們證明總是可以簡化為另一個表達式，使得等價于。如果我們用x表示的某個值，則有xn≡A，進一步，令t為表達式δ/n（mod p-1）的某個值，從條目31可知，t有真實的值。現在，xtn≡At，但是xtn≡xδ，因為tn≡δ（mod p-1）。因此，xδ≡At，因此，的任何值都也是的一個值。因此，每當有真實值時，它就完全等價于。這是因為，前者不可能有和后者不一樣的值，也不可能有比后者更少的值，除了在某些情況下，可能有非真實值而有真實值。

例：如果要求表達式（mod 31）的值。數21和30的最大公約數是3，3是表達式（mod 30）的一個值。因此，如果有真實值，它就等價于表達式，或。實際上，后者的全部值2，10，19也滿足前者。

64

為避免做徒勞無功的試算，應當找出一種法則來判斷是不是有真實值。如果有指標表就很容易做到。因為，從第60條可知，如果以任意原根作為基數，A的指標能夠被δ整除，那么就有真實值；反之，就沒有真實值。然而，即便沒有這樣一張表，還是可以確定有沒有真實值。令A的指標等于k。如果k可以被δ整除，那么k（p-1）/δ就可以被p-1整除，反之亦然。但是數的指標就是k（p-1）/δ。那么，如（mod p）有真實值，就同余于1；反之就不同余于1。那么，在上一條目的例子中，我們有210＝1024≡1（mod 31），所以我們推斷（mod 31）有真實值。同理，我們發現，當p形如4m＋1時，（mod p）總有一對真實值；當p形如4m＋3時，（mod p）沒有真實值，因為（-1）2m＝1，而（-1）2m＋1＝-1。這則優美的定理通常被表述成：如果p是形如4m＋1的質數，總能找到一個平方數a2使得a2＋1被p整除；但是如果p是形如4m-1的質數，這樣的平方數就不存在。歐拉先生在Novicomm. Acad. Petrop上用這種方法證明了這則定理。在此之前的1760年，他就已經給出這則定理的另一種證明。在之前的一篇論文里，他還沒有得到這一結論。后來，在Nouv. mem. Acad. Berlin上，拉格朗日先生也給出了這則定理的證明。我們會在專門討論這個問題的下一章給出另外一種證明。

65

討論完如何將表達式（mod p）簡化為n是p-1的因數的表達式，并且找到了判別（mod p）有沒有真實值的方法之后，我們現在討論n是p-1的因數的情況。首先，我們指出這個表達式的所有不同值之間的關系，然后，我們討論求出該表達式的值的某種方法。

首先，當A≡1，且r是表達式（mod p）的任意一個值，或者說rn≡1（mod p）時，那么r的方冪也是這個表達式的值；r屬于的指數是多少，表達式就有多少個不同的值（條目48）。因此，如果r是屬于指數的一個值，r所有的方冪r，r2，r3，…，rn（1可以代替最后一個）給出了表達式（mod p）的所有的值。我們將在第8章解釋有什么樣的方法可以幫助我們求出屬于指數n的那些值。

其次，當A不同余于1，且表達式（mod p）的一個值z為已知時，按照如下方法可以求得它的其他值。令表達式的值為1，r，r2，…，rn-1（像我們已經指出的那樣），那么表達式的所有值是z，zr，zr2，…，zrn-1，事實上，所有這些值都滿足同余方程xn≡A。因為，任取其中一個值，假設它≡zrk，由于rn≡1且zn≡A，顯然，zrk的n次方冪znrnk同余于A。由條目23，容易發現這些值都是各不相同的。因此，表達式除了這n個值外，不能有其他值。那么，如果表達式的一個值是z，另外一個值就是-z。根據以上討論，必定有這樣的結論：如果沒有同時求得的所有值，是不可能求出表達式的所有值的。

66

我們準備做的第二件事，就是搞清楚什么時候表達式（mod p）的一個值可以被直接確定（當然，預先假設n是p-1的因數）。當表達式（mod p）的某個值同余于A的方冪，就會出現這種情況。這種情況經常會出現，我們應當討論一下。如果這樣的值存在，令它為z，即z≡Ak，且A≡zn（mod p）。于是有，A≡Akn，因而，如果能夠找到一個數k，使得A≡Akn，Ak就是我們要求的值。但是，這個條件等價于1≡kn（mod t），式中t是A所屬的指數（參考條目46，48）。但為了使得這個同余式成立，必須保證n和t互質。在這種情況下，我們就有k≡1/n（mod t），然而，如果t和n有最大公約數，那么就不存在同余于A的方冪的值z。

67

按照這種解法，t必須為已知條件；我們看一下t為未知的情況下如何繼續求解。首先，顯然，如果（mod p）要有真實值，t必須能夠整除，我們這里總是做這個假設。令y是這些真實值中的一個，那么我們就有yp-1≡1和yn≡A（mod p）。后者通過自乘到次冪，就得到了。所以，可以被t整除（參考條目48）。現在，如果是與n互質的數，上一條目中的同余方程kn≡1對于模可解；對于這個模，滿足同余方程的值k，顯然也滿足同余方程kn≡1（mod t），因為模t整除（條目5），那么，目的就達到了。如果不與n互質，從中消除所有那些同時整除n的質因數。那么，就得到了一個與n互質的數，這里q表示被消除的所有那些質因數的積。現在，如果上一條目的條件成立，即t是與n互質的數，那么，t就是與q互質的數，因而可以整除。因此，如果我們解同余方程kn≡1（mod）（這個方程是可解的，因為n與互質），那么，對于模t，解得的k的值就同樣滿足這個同余方程，而這正是所要求的。整個方法主要在于找到一個數來取代未知數t。然而，我們必須記住，當不與n互質時，假設上一條目中的條件成立。如果該條件不成立，那么所有的結論就都不成立。如果忽略了這一點，按照所給的步驟做下去，將得到一個值z，它的n次冪不同余于A，那么這就表明這個條件不成立，所以這個方法就完全不能使用。

68

但是，即便是在這種情況下，做所說的這些步驟也常常是有好處的，并且研究這個不正確的值與真正的那些值之間的關系也是有價值的。因此，假設我們按所說的步驟確定了k和z的值，但zn不同余于A（mod p）。那么，只要能確定表達式（mod p）的所有值，再把這些值乘以z，就求得了的所有值。因為，如果v是表達式的一個值，我們就有（vz）n≡A。但是，表達式比更簡單，因為A/zn（mod p）所屬的指數通常比A所屬的指數更小。更準確地說，如果數t，q的最大公約數是d，A/zn（mod p）就屬于指數d。下面我們來證明。如果z以它的值代入，我們得到A/zn≡1/Akn-1（mod p）。但是，kn-1可以被（p-1）/nq整除，（p-1）/n可以被t整除（參考上一條目），也就是說，（p-1）/nd可以被t/d整除。但是，t/d和q/d是互質的（根據假設），那么（p-1）/nd也可以被tq/d2整除，或（p-1）/nq被t/d整除。因而，kn-1可被t/d整除，并且（kn-1）d被t整除。由此可以得到A（kn-1）d≡1（mod p），我們可以推導出A/zn的d次冪是同余于1的。容易證明，A/zn不可能屬于比d小的指數；我們不作深入闡述，因為不需要這條結論。那么，除了t整除q，且d＝t這一特殊情況外，可以確定A/zn（mod p）所屬的指數總是比A所屬的指數小。

但是，得到了所屬的指數比A所屬的指數要小的A/zn后的優勢是什么？優勢就是，比起以A/zn的形式出現的數來說，以A的形式出現的數更多；而且，如果我們要求解形如且模都相同的眾多表達式，我們的優勢就是一次計算可以得到很多結果。因此，舉例來說，如果我們知道了表達式（mod 29）的值（它們是±12），我們總是至少能確定表達式（mod 29）的一個值。從上一條目容易看出，當t是奇數時，我們如何直接確定類似表達式的一個值，并且，當t是偶數時，d就等于2，但-1除外，沒有數屬于指數2。

例：求（mod 37）的值。這里p-1＝36，n＝3，＝12，所以q＝3。因為要使得3k≡1（mod 4），這只要取k＝3就成立。由此得z≡313（mod 37）≡6，并且，實際上我們得到63≡31（mod 37）成立。如果已知表達式（mod 37）的值，那么就能確定表達式的其余的值。（mod 37）的值是1，10，26，它們乘以6，就得到其余兩個值≡8，23。如果要求表達式（mod 37）的值，那么這里有n＝2，，所以q＝2。因為要使得2k≡1（mod 9），所以k≡5（mod 9）。進而有z≡35≡21（mod 37）。但212不同余于3，而同余于34，不過，（mod 37）≡-1并且（mod 37）≡±6。由此求得正確的值為±6×21≡±15。

關于這種表達式的計算，這些基本上就是我們所能介紹的。我們知道，直接法往往較為冗長，數論中幾乎所有的直接法都是這樣。盡管如此，我們還是要將它們的實用性演示給大家。但是，逐一解釋每種具體的技巧就不是我們此書的目的了，凡是在這個領域研究的人自然會對它們越來越熟悉。