60
在条目31中，我们用一个特殊符号表示一次同余方程的根。接下来，我们使用另一个特殊符号来表示最简高次同余方程的根。就如同 表示方程x n ＝A 的根，加上模后， （mod p ）就表示同余方程x n ＝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开始讨论，也就是求同余方程x n ≡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 ）与同余方程x n ≡1有完全相同的根。但如果δ 和n 不相等，则前者的阶数较低。
例 （mod 9）有3个值，因为15和18的最大公约数是3；而且，它们也是表达式 （mod 19）的值。这些值是1，7，11。
62
由简化的方法可知，我们只要求解那些n 是数p -1的因数的形如x n ≡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 表示 的某个值，则有x n ≡A ，进一步，令t 为表达式δ /n （mod p -1）的某个值，从条目31可知，t 有真实的值。现在，x tn ≡A t ，但是x tn ≡x δ ，因为tn ≡δ （mod p -1）。因此，x δ ≡A t ，因此， 的任何值都也是 的一个值。因此，每当 有真实值时，它就完全等价于 。这是因为，前者不可能有和后者不一样的值，也不可能有比后者更少的值，除了在某些情况下， 可能有非真实值而 有真实值。
例：如果要求表达式 （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的质数，总能找到一个平方数a 2 使得a 2 ＋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 ）的任意一个值，或者说r n ≡1（mod p ）时，那么r 的方幂也是这个表达式的值；r 属于的指数是多少，表达式就有多少个不同的值（条目48） 。因此，如果r 是属于指数的一个值，r 所有的方幂r ，r 2 ，r 3 ，…，r n （1可以代替最后一个） 给出了表达式 （mod p ）的所有的值。我们将在第8章解释有什么样的方法可以帮助我们求出属于指数n 的那些值。
莱昂哈德·欧拉
莱昂哈德·欧拉（Leonhard Euler，1707—1783年），瑞士数学家、物理学家。近代数学先驱之一，也是有史以来最伟大的数学家之一，在数学的多个领域（包括微积分、数论和图论等）都做出过重大贡献。在力学、光学和天文学等学科，他也有突出贡献。
其次，当A 不同余于1，且表达式 （mod p ）的一个值z 为已知时，按照如下方法可以求得它的其他值。令表达式 的值为1，r ，r 2 ，…，r n -1 （像我们已经指出的那样） ，那么表达式 的所有值是z ，zr ，zr 2 ，…，zr n -1 ，事实上，所有这些值都满足同余方程x n ≡A 。因为，任取其中一个值，假设它≡zr k ，由于r n ≡1且z n ≡A ，显然，zr k 的n 次方幂z n r nk 同余于A 。由条目23，容易发现这些值都是各不相同的。因此，表达式 除了这n 个值外，不能有其他值。那么，如果表达式 的一个值是z ，另外一个值就是-z 。根据以上讨论，必定有这样的结论：如果没有同时求得 的所有值，是不可能求出表达式 的所有值的。
66
我们准备做的第二件事，就是搞清楚什么时候表达式 （mod p ）的一个值可以被直接确定（当然，预先假设n 是p -1的因数） 。当表达式 （mod p ）的某个值同余于A 的方幂，就会出现这种情况。这种情况经常会出现，我们应当讨论一下。如果这样的值存在，令它为z ，即z ≡A k ，且A ≡z n （mod p ）。于是有，A ≡A kn ，因而，如果能够找到一个数k ，使得A ≡A kn ，A k 就是我们要求的值。但是，这个条件等价于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 是这些真实值中的一个，那么我们就有y p -1 ≡1和y n ≡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 的值，但z n 不同余于A （mod p ）。那么，只要能确定表达式 （mod p ）的所有值，再把这些值乘以z ，就求得了 的所有值。因为，如果v 是表达式 的一个值，我们就有（vz ） n ≡A 。但是，表达式 比 更简单，因为A /z n （mod p ）所属的指数通常比A 所属的指数更小。更准确地说，如果数t ，q 的最大公约数是d ，A /z n （mod p ）就属于指数d 。下面我们来证明。如果z 以它的值代入，我们得到A /z n ≡1/A kn -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 /d 2 整除，或（p -1）/nq 被t /d 整除。因而，kn -1可被t /d 整除，并且（kn -1）d 被t 整除。由此可以得到A （kn -1）d ≡1（mod p ），我们可以推导出A /z n 的d 次幂是同余于1的。容易证明，A /z n 不可能属于比d 小的指数；我们不作深入阐述，因为不需要这条结论。那么，除了t 整除q ，且d ＝t 这一特殊情况外，可以确定A /z n （mod p ）所属的指数总是比A 所属的指数小。
但是，得到了所属的指数比A 所属的指数要小的A /z n 后的优势是什么？优势就是，比起以A /z n 的形式出现的数来说，以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。
关于这种表达式的计算，这些基本上就是我们所能介绍的。我们知道，直接法往往较为冗长，数论中几乎所有的直接法都是这样。尽管如此，我们还是要将它们的实用性演示给大家。但是，逐一解释每种具体的技巧就不是我们此书的目的了，凡是在这个领域研究的人自然会对它们越来越熟悉。
