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