100
在我们进入难度更大的主题之前，让我们补充几点关于非质数模的讨论。
如果模是p n ，p 为质数（我们假设p 不是2） ，那么，在所有小于p n 且不能被p 整除的数中，一半是剩余，一半是非剩余，即，两者的个数都是 。
中国剩余定理
中国剩余定理，也称孙子定理，是数论中关于一元线性同余方程组的定理，阐述了一元线性同余方程组有解的准则以及求解方法。其相关问题，最早由孙子在其于南北朝时期写就的《孙子算经》中提出：“物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”图为《孙子算经》书影。
因为，如果r 是剩余，它就同余于某个不大于模的一半的数的平方 （参考条目94） 。容易看出，有 个不能被p 整除且小于模的一半的数；剩下就要证明所有这些数的平方都彼此不同余，或者说它们产生不同的二次剩余。假设两个不能被p 整除且小于模的一半的数a ，b 的平方是彼此同余的，我们就有a 2 -b 2 或（a -b ）（a ＋b ）能够被p n 整除（我们假设a ＞b ） 。但是，这是不可能的，除非以下两种情况：①数（a -b ）或者数（a ＋b ）能够被p n 整除，但这是不可能的，因为这两个数都小于p n 。②这两个数中的一个能够被p m 整除，一个能够被p n -m 整除，即它们都能被p 整除，但这也是不可能的。因为这就意味着这两个数的和与差，即2a 与2b 都能被p 整除，因此a 和b 也就都能被p 整除，这与假设矛盾。最后，在所有不能被p 整除且小于模的数中，有 个剩余，其他的数都是非剩余，个数与前者相同。证明完毕。像在条目97中一样，可以用指标来证明这则定理。
101
任何不能被p 整除的数，如果它是p 的剩余，则它也是p n 的剩余；如果它是p 的非剩余，则它也是p n 的非剩余。
定理的后半部分显然成立。因此，如果前半部分不成立，那么在所有小于p n 且不被p 整除的数中，p 的剩余要比p n 的剩余多，即，p 的剩余多于 个。但是，显然，在这些数中p 的剩余的个数就是 个。
如果我们有对于模p 同余于给定剩余的平方数，那么求对于模p n 同余于这个剩余的平方数也是很容易的。
因为，如果a 2 是对于模p μ 同余于给定剩余A 的平方数，按照如下方式，我们可以求得一个对于模p v 同余于A 的平方数（我们这里假设v 大于μ 且不大于2μ ） 。假设我们要求的平方数的根等于±a ＋xp μ 。容易看出的是，平方数的根就形如±a ＋xp μ 。并且，我们应当还有a 2 ≡±2axp μ ＋x 2 p 2μ ≡A （mod p v ）或者，因为，2μ ＞v ，A -a 2 ≡±2axp μ （mod p v ）。设A -a 2 ＝p μ d ，那么x 就是表达式 （mod p v -μ ）的值。这个表达式等价于 （mod p v ）。
因此，给定一个对于模p 同余于A 的平方数，由此我们可以推导出对于模p 2 同余于A 的平方数；再由此我们可以推导出对于模p 4 同余于A 的平方数，然后到模p 8 ，…，以此类推。
例：如果给定剩余6，它对于模5同余于1的平方，那么，我们可以求出平方数92 对于模25同余于它，进而求出162 对于模125同余于它，等等。
102
就能够被p 整除的数来说，可知它们的平方数也可以被p 2 整除，因此，所有被p 整除但不被p 2 整除的数都是p n 的非剩余。一般地，如果我们有一个给定数p k A ，A 不被p 整除，我们可以区分以下情况：
1．当k ≥n 时，我们有p k A ≡0（mod p n ），即p k A 是剩余。
2．当k ＜n 并且k 是奇数时，p k A 是非剩余。
因为，假如p k A ＝p 2x ＋1 A ≡s 2 （mod p n ），那么s 2 就能被p 2x ＋1 整除。除非s 能被p x ＋1 整除，否则这是不可能的；但这时s 2 也被p 2x ＋2 整除，并且（因为2x ＋2肯定不大于n ） p k A ，即p 2x ＋1 A 也被p 2x ＋2 整除。这就意味着p 可以整除A ，这与假设相矛盾。
3．当k ＜n 并且k 是偶数时，p k A 是p n 的剩余或非剩余取决于A 是p 的剩余或非剩余。因为，当A 是p 的剩余，A 就也是p n -k 的剩余。但是，如果我们假设A ≡a 2 （mod p n -k ），我们得到Ap k ≡a 2 p k （mod p n ）且a 2 p k 是一个平方数。另一方面，当A 是p 的非剩余时，p k A 不可能是p n 的剩余。因为，如果p k A ≡a 2 （mod p n ），a 2 就必须能够被p k 整除。所以，它们的商是一个平方数，且对于模p n -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．如果两个数的和或者差能够被2 n -1 整除，这些数的平方数就对于模2 n 同余。因为，如果其中一个数等于a ，另一个数就形如2 n -1 h ±a ，并且它的平方数就同余于a 2 （mod 2 n ）。
2．任何是模2 n 的剩余的奇数都同余于一个小于2 n -2 的奇数的平方。因为，设给定的数同余于a 2 ，并且设a ≡±α （mod 2 n -1 ），且α 不超过模的一半 （参考条目4） ，那么，a 2 ≡α 2 ，因而给定的数同余于α 2 。显然，a 和α 都是奇数，且α ＜2 n -2 。
3．所有小于2 n -2 的奇数的平方数都不与2 n 同余。假设这样的两个数分别为r 和s ，如果它们的平方数与2 n 同余，（r -s ）（r ＋s ）就能够被2 n 整除（我们假设r ＞s ） 。不难发现，数r -s 和r ＋s 不可能同时被4整除。但是，如果其中一个只能被2整除，那么，为了使得乘积能够被2 n 整除，另一个就应当能被2 n -1 整除，而这是不可能的，因为它们每个都小于2 n -2 。
4．如果这些平方数都简化为它们的最小正剩余 ，我们就有2 n -3 个小于模的不同的二次剩余 [3] ，并且它们中的每一个都有8k ＋1的形式。但是，因为在小于模的数中恰好有2 n -3 个形如8k ＋1的数，所有这些数都一定是剩余。证明完毕。
为了求出对于模2 n 同余于给定的形如8k ＋1的数的一个平方数，可以采用与条目101中类似的方法（也参考条目88 ） 。最后，关于偶数，在条目102中我们总结的所有结论都成立。
104
如果A 是p n 的剩余，关于表达式 （mod p n ）所取的不同的值（对于模不同余的值） 的个数，从前面的讨论可以推出以下结论。（像之前一样，我们假设数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个值，即，如果这些值中的一个同余于ν ，剩下的值就同余于-ν ，2 n -1 ＋ν ，2 n -1 -ν 。
2．如果A 能够被p 整除但不能被p n 整除，设整除A 的p 的最高次幂为p 2μ 。显然，V 的所有值都能被p μ 整除，并且所得的商就是表达式V ′＝a （mod p n -2μ ）的值；那么，我们只要将表达式V ′位于0到p n -μ 之间的所有的值都乘以p μ ，就可以得到V 的所有值。这样处理后，我们就得到了V 值
v 代表了V ′的不同的值，因此，对应于V ′的值的个数分别是1，2，4（见情形1） ，V 的值的个数分别是p μ ，2p μ 或4 p μ 。
3．如果A 能够被p n 整除，容易发现的是，如果对应于n 是偶数或奇数我们分别令n ＝2m 或n ＝2m -1，那么，所有能够被p m 整除的数就构成了V 的值，不会再有其他数；这些值就是0，p m ，2p m ，…，（p n -m -1）p m 。它们的个数是p n -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 ，…，分别同余于A 2 ，B 2 ，C 2 ，…。如果我们求得对于模a ，b ，c ，…分别同余于数A ，B ，C ，…的数N （参考条目32） ，那么，对于这些模n ≡N 2 ，因而，对于乘积m ，n ≡N 2 。把数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。
