第4节　合数模

100

在我们进入难度更大的主题之前，让我们补充几点关于非质数模的讨论。

如果模是pn，p为质数（我们假设p不是2），那么，在所有小于pn且不能被p整除的数中，一半是剩余，一半是非剩余，即，两者的个数都是。

因为，如果r是剩余，它就同余于某个不大于模的一半的数的平方（参考条目94）。容易看出，有个不能被p整除且小于模的一半的数；剩下就要证明所有这些数的平方都彼此不同余，或者说它们产生不同的二次剩余。假设两个不能被p整除且小于模的一半的数a，b的平方是彼此同余的，我们就有a2-b2或（a-b）（a＋b）能够被pn整除（我们假设a＞b）。但是，这是不可能的，除非以下两种情况：①数（a-b）或者数（a＋b）能够被pn整除，但这是不可能的，因为这两个数都小于pn。②这两个数中的一个能够被pm整除，一个能够被pn-m整除，即它们都能被p整除，但这也是不可能的。因为这就意味着这两个数的和与差，即2a与2b都能被p整除，因此a和b也就都能被p整除，这与假设矛盾。最后，在所有不能被p整除且小于模的数中，有个剩余，其他的数都是非剩余，个数与前者相同。证明完毕。像在条目97中一样，可以用指标来证明这则定理。

101

任何不能被p整除的数，如果它是p的剩余，则它也是pn的剩余；如果它是p的非剩余，则它也是pn的非剩余。

定理的后半部分显然成立。因此，如果前半部分不成立，那么在所有小于pn且不被p整除的数中，p的剩余要比pn的剩余多，即，p的剩余多于个。但是，显然，在这些数中p的剩余的个数就是个。

如果我们有对于模p同余于给定剩余的平方数，那么求对于模pn同余于这个剩余的平方数也是很容易的。

因为，如果a2是对于模pμ同余于给定剩余A的平方数，按照如下方式，我们可以求得一个对于模pv同余于A的平方数（我们这里假设v大于μ且不大于2μ）。假设我们要求的平方数的根等于±a＋xpμ。容易看出的是，平方数的根就形如±a＋xpμ。并且，我们应当还有a2≡±2axpμ＋x2p2μ≡A（mod pv）或者，因为，2μ＞v，A-a2≡±2axpμ（mod pv）。设A-a2＝pμd，那么x就是表达式（mod pv-μ）的值。这个表达式等价于（mod pv）。

因此，给定一个对于模p同余于A的平方数，由此我们可以推导出对于模p2同余于A的平方数；再由此我们可以推导出对于模p4同余于A的平方数，然后到模p8，…，以此类推。

例：如果给定剩余6，它对于模5同余于1的平方，那么，我们可以求出平方数92对于模25同余于它，进而求出162对于模125同余于它，等等。

102

就能够被p整除的数来说，可知它们的平方数也可以被p2整除，因此，所有被p整除但不被p2整除的数都是pn的非剩余。一般地，如果我们有一个给定数pkA，A不被p整除，我们可以区分以下情况：

1．当k≥n时，我们有pkA≡0（mod pn），即pkA是剩余。

2．当k＜n并且k是奇数时，pkA是非剩余。

因为，假如pkA＝p2x＋1A≡s2（mod pn），那么s2就能被p2x＋1整除。除非s能被px＋1整除，否则这是不可能的；但这时s2也被p2x＋2整除，并且（因为2x＋2肯定不大于n）pkA，即p2x＋1A也被p2x＋2整除。这就意味着p可以整除A，这与假设相矛盾。

3．当k＜n并且k是偶数时，pkA是pn的剩余或非剩余取决于A是p的剩余或非剩余。因为，当A是p的剩余，A就也是pn-k的剩余。但是，如果我们假设A≡a2（mod pn-k），我们得到Apk≡a2pk（mod pn）且a2pk是一个平方数。另一方面，当A是p的非剩余时，pkA不可能是pn的剩余。因为，如果pkA≡a2（mod pn），a2就必须能够被pk整除。所以，它们的商是一个平方数，且对于模pn-k与A同余；即，A是p的二次剩余，这与假设矛盾。

103

因为我们在上文中排除了p＝2的情况，我们这里应当对其稍微讨论一下。当模是2时，那么每个数都是剩余，不存在非剩余。当模是4时，所有形如4k＋1的奇数都是剩余，所有形如4k＋3的数都是非剩余。当模是8或者2的更高次幂时，那么所有形如8k＋1的奇数都是剩余，所有其他的形如8k＋3，8k＋5，8k＋7的数都是非剩余。这定理的后半部分从下面的事实可以明显得到，即任何奇数，不论是形如4k＋1或者是4k-1，它的平方数都形如8k＋1。我们按下述方式证明定理的前半部分。

1．如果两个数的和或者差能够被2n-1整除，这些数的平方数就对于模2n同余。因为，如果其中一个数等于a，另一个数就形如2n-1h±a，并且它的平方数就同余于a2（mod 2n）。

2．任何是模2n的剩余的奇数都同余于一个小于2n-2的奇数的平方。因为，设给定的数同余于a2，并且设a≡±α（mod 2n-1），且α不超过模的一半（参考条目4），那么，a2≡α2，因而给定的数同余于α2。显然，a和α都是奇数，且α＜2n-2。

3．所有小于2n-2的奇数的平方数都不与2n同余。假设这样的两个数分别为r和s，如果它们的平方数与2n同余，（r-s）（r＋s）就能够被2n整除（我们假设r＞s）。不难发现，数r-s和r＋s不可能同时被4整除。但是，如果其中一个只能被2整除，那么，为了使得乘积能够被2n整除，另一个就应当能被2n-1整除，而这是不可能的，因为它们每个都小于2n-2。

4．如果这些平方数都简化为它们的最小正剩余，我们就有2n-3个小于模的不同的二次剩余^[3]，并且它们中的每一个都有8k＋1的形式。但是，因为在小于模的数中恰好有2n-3个形如8k＋1的数，所有这些数都一定是剩余。证明完毕。

为了求出对于模2n同余于给定的形如8k＋1的数的一个平方数，可以采用与条目101中类似的方法（也参考条目88）。最后，关于偶数，在条目102中我们总结的所有结论都成立。

104

如果A是pn的剩余，关于表达式（mod pn）所取的不同的值（对于模不同余的值）的个数，从前面的讨论可以推出以下结论。（像之前一样，我们假设数p是质数；为了简洁，我们将n＝1的情况包括在内。）

1．如果A不能被p整除，那么，当p＝2，n＝1时，V有一个值，即V＝1；当p是奇数，且p＝2，n＝2时，V有2个值，即，如果其中一个值同余于ν，另一个值就同余于-ν；当p＝2，n＞2时，V有4个值，即，如果这些值中的一个同余于ν，剩下的值就同余于-ν，2n-1＋ν，2n-1-ν。

2．如果A能够被p整除但不能被pn整除，设整除A的p的最高次幂为p2μ。显然，V的所有值都能被pμ整除，并且所得的商就是表达式V′＝a（mod pn-2μ）的值；那么，我们只要将表达式V′位于0到pn-μ之间的所有的值都乘以pμ，就可以得到V的所有值。这样处理后，我们就得到了V值

v代表了V′的不同的值，因此，对应于V′的值的个数分别是1，2，4（见情形1），V的值的个数分别是pμ，2pμ或4 pμ。

3．如果A能够被pn整除，容易发现的是，如果对应于n是偶数或奇数我们分别令n＝2m或n＝2m-1，那么，所有能够被pm整除的数就构成了V的值，不会再有其他数；这些值就是0，pm，2pm，…，（pn-m-1）pm。它们的个数是pn-m。

105

剩下还要考虑当模m由若干个质数合成的情况。令m＝abc…，其中，a，b，c，…是不同的质数或不同的质数的幂。那么，立刻可知的是，如果n是模m的剩余，那么，它也是所有的模a，b，c，…的剩余；并且，如果它是数a，b，c，…中任意一个的非剩余，它就是m的非剩余。反过来，如果n是所有数a，b，c，…的剩余，那么，它也是数a，b，c，…乘积m的剩余。假设n对于模a，b，c，…，分别同余于A2，B2，C2，…。如果我们求得对于模a，b，c，…分别同余于数A，B，C，…的数N（参考条目32），那么，对于这些模n≡N2，因而，对于乘积m，n≡N2。把数A，即表达式（mod a）的每一个值，与数B的每一个值，与数C的每一个值，…相组合，我们就得到了数N，即表达式（mod m）的一个值。从不同的组合可以得到不同的N值，从所有组合可以得到N所有的值。因此，N的所有不同的值的个数就等于数A，B，C，…的值的个数的乘积，在上一条目中我们已经演示了如何确定这个个数。显然，如果表达式（mod m）或N的一个值已知，那么，它也是所有A，B，C…的一个值；因为，从上一条目知道如何从这个值推出这些数的剩余的值；由此可知，知道了N的一个值，可以得到剩下所有的值。

例：设模是315，我们判断46是剩余还是非剩余。315的质除数是3，5，7，并且数46是它们每个数的剩余，因此，它也是315的一个剩余。而且，因为46≡1并且46≡64（mod 9）；46≡1并且46≡16（mod 5）；46≡4并且46≡25（mod 7），所以，对于模315同余于46的所有的平方数的根是19，26，44，89，226，271，289，296。