第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。

关于这种表达式的计算，这些基本上就是我们所能介绍的。我们知道，直接法往往较为冗长，数论中几乎所有的直接法都是这样。尽管如此，我们还是要将它们的实用性演示给大家。但是，逐一解释每种具体的技巧就不是我们此书的目的了，凡是在这个领域研究的人自然会对它们越来越熟悉。