第5節　一些定理

38

問題

求小于給定正數A，且與A互質的正數的個數。

為了簡便，我們在給定的數前面加上前綴φ來表示與之互質且小于它的正數的個數。因此，我們求φA。

1．當A為質數，顯然所有從1到A-1的數都與A互質，那么在這種情況下

φA＝A-1

2．當A是質數冪，例如A＝pm，所有能被p整除的數都與A不互質，但是其他的數都與A互質。所以在pm-1個數中，必須摒棄這些數：p，2p，3p…（pm-1-1）p。因此剩下的數有pm-1-（pm-1-1）個，即pm-1（p-1）個。則

φA＝pm-1（p-1）

3．剩下的情況可以通過以下定理簡化為前兩種情況：如果A分解為互質的因數M，N，P，…，則

為證明之，令與M互質且小于M的數為m，m′，m″，…，所以它們的個數為φM。類似地，令分別與N，P，…互質且小于N，P，…的數為n，n′，n″，…；p，p′，p″，…；…，所以每組數的個數分別為φN，φP，…，顯然，所有與乘積A互質的數一定分別對于單獨的因數M，N，P，…互質，并且反之亦然（參見條目19）；而且，所有對于模M與m，m′，m″，…中的任何一個數同余的數都與M互質，并且反之亦然。對于N，P，…也有類似的結論。那么問題就可以簡化如下：確定有多少小于A的，且對于模M與m，m′，m″，…中的其中一個數同余，且對于模N與n，n′，n″，…中的其中一個數同余，…。但是從條目32條可知，對于模M，N，P，…中的每一個都有給定剩余的所有的數一定是對它們的乘積A同余的。因此，小于A且對于模M，N，P，…都有給定剩余的數有且只有一個。因此，我們要求的個數就等于m，m′，m″，…的各個值，n，n′，n″，…的各個值，p，p′，p″，…的全部組合個數。從組合理論，組合的個數為

或者，更優雅地表示為

例：令A＝60＝22×3×5，那么φA＝（1/2）×（2/3）×（4/5）×60＝16。與60互質的數有1，7，11，13，17，19，23，29，31，37，41，43，47，49，53，59。

這個問題的第一個解法出現在歐拉的論文Theorema arithmetica nova methodo demonstrata中。這個解法在另一篇名為Speculationes circa quasdam insignes proprietates numerorum的論文中重復出現。

39

如果我們把函數φ定義為：φA表示不大于A且與A互質的數的個數。顯然，φ1不等于0，而等于1。在其他情況下沒有任何變化。采用這個定義后，我們得到如下定理

如果a，a′，a″，…都是A的因數（包括1和A），那么φa＋φa′＋φa″＋…＝A。

例：令A＝30，那么φ1＋φ2＋φ3＋φ5＋φ6＋φ10＋φ15＋φ30＝1＋1＋2＋4＋2＋4＋8＋8＝30。

證明

將所有與a互質且不大于a的數乘以A/a；同樣地，將所有與a′互質且不大于a′的數乘以A/a′…，我們就會得到（φa＋φa′＋φa″＋…）個都不大于A的數。但是：

1．所有這些數都不相等。因為顯然由同一個除數A所生成的數都不相等。現在如果由兩個不同的除數M和N以及兩個與M和N互質的數μ和v得出兩個相等的數，即，如果（A/M）μ＝（A/N）v，就有μN＝vM。假設M＞N，因為M與μ互質，又因為M可以整除μN，所以M必須整除N，那么一個較大的數就整除一個較小的數，這是不可能的。

2．所有的數1，2，3，…A，都包含在這些數中。令t為不大于A的任意正整數，δ是A和t的最大公約數。那么A/δ就是A的除數且與t/δ互質。顯然，這個數t可以在由除數A/δ生成的數中找到。

3．由此可以推出這些數的個數為A，所以

φa＋φa′＋φa″＋…＝A

證明完畢。

40

令數A，B，C，D，…的最大公約數為μ。我們總是可以確定數a，b，c，d，…，使得：aA＋bB＋cC＋…＝μ。

證明

首先只考慮兩個數A和B，并且令它們的最大公約數為λ。那么同余方程Ax≡λ（mod B）是可解的（參考條目30）。令同余方程的根x≡α（λ-Aα）/B＝β。那么我們可以得到αA＋βB＝λ。

如果有第三個數C，令λ′是λ和C的最大公約數，并且確定數k，γ使得kλ＋γC＝λ′，那么kαA＋kβB＋γC＝λ′。

顯然，λ′是數A，B，C的公約數，實際上是它們的最大公約數，因為如果有更大的公約數θ，我們就能得到是整數，這是不可能的。

所以我們令kα＝a，kβ＝b，γ＝c，λ′＝μ就完成了證明。

如果有更多的數，我們可用同樣的方式展開。并且，如果數A，B，C， D，…沒有公約數，顯然我們能得到aA＋bB＋cC＋…＝1。

41

如果p是質數且我們有p個元素，其中可以有任意多個元素相同，但不能全部相同，那么這些元素的所有不同的排列個數可以被p整除。

例：5個元素A，A，A，B，B可以以10種不同的方式排列。

這個定理的證明可以輕松地從大家熟悉的排列理論推導出。因為，如果在這些元素中有a個元素是A，b個元素是B，c個元素是C，…（數a，b，c，…中的任何數均可為1），那么a＋b＋c＋…＝p。并且排列的個數將會是

現在可知此分數的分子可以被分母整除，因為排列數必須是整數。但是，分子能被p整除，然而由小于p的因數構成的分母不能被p整除（參考條目15）。因此，排列數可以被p整除（參考條目19）。

但是我希望仍會有些讀者歡迎下面的證明。

考慮相同元素的兩種排列。假設元素的順序的區別僅在于一個排列中第1個元素出現在另一個排列的不同的位置上，而其余所有元素仍按照相同的順序排列在它前后兩邊。進一步假設，如果我們考慮一個排列中的第1個和最后1個元素，看到這兩個元素在另外一個排列中第1個元素緊隨著最后1個元素出現，這兩種排列我們稱之為相似排列。^[4]因此，在我們的例子中，排列ABAAB和ABABA是相似排列，因為，在前一個排列中位于第1，第2，…的位置的元素，在后一個排列中占據了第3，第4，…的位置，所以

它們是按照相同的接替順序排列。現在因為任意排列包含p個元素，明顯我們能夠找到p-1個排列與其相似，只需將第1個排列中的第1的位置的元素向后移到第2，第3，…的位置。顯然，如果這些排列都不相同，排列數可以被p整除，因為排列數是所有不相似的排列的p次整數倍。假設我們有兩組排列PQ…TV…YZ；V…YZPQ…T，其中一組是通過另一組的元素向前移動得出的。進一步假設兩組排列是相同的，即P＝V，…，令前一組排列中排第1位的元素P在后一組排列中為第n＋1個。那么在后一組排列中第n＋1個元素就與前一個排列中的第1個元素相等，第n＋2個元素就與第2個相等，第2n＋1個就與第1個相等，第3n＋1個就與第1個相等，…。一般地，后一個排列的第kn＋m個元素等于前一個排列的第m個元素（前提是當kn＋m大于p，我們或者考慮排列V…YZPQ…T是不斷地從頭開始重復，或者可以把它看作從kn＋m中減去小于它且數值上是最接近它的p的倍數之差）。因此，如果確定數k使得kn≡1（mod p），這是可以做到的。因為p是質數，那么一般可以得到第m個元素與第m＋1元素相同，或每一項都與后一項相同，即，所有元素都相同，這與假設矛盾。

42

如果兩個函數形如

它們的系數A，B，C，…N；a，b，c，…n都是有理數但不都是整數，并且如果（P）和（Q）的乘積為，

那么，不是所有的系數都能為整數。

證明

將所有系數A，B，…，a，b，…用最簡分數表示，任意選擇一個質數p，它整除這些分數中的一個或多個分母。假定p能夠整除（P）中一個分數系數的分母，如果我們用（Q）除以p，可知在（Q）/p中至少有一個分數系數的分母以p作為它的因數（例如，第一項的系數1/p）。不難看出，在（P）中總是有一項的分數系數的分母含有的p的方冪大于所有在它前面的分數系數的分母所含有的p的方冪，且不小于所有在它后面的項的分數系數的分母所含有的p的方冪。令這一項為Gxg，并且令G的分母中p的方冪等于t。在（Q）/p中可以找到相似的一項。令這一項為Γxy，并且令Γ的分母中p的方冪等于τ。顯然，t＋τ的值至少等于2。現在我們證明在（P）和（Q）的乘積中的項xg＋y的系數是分數，分母含p的t＋τ-1次冪。

令（P）中在Gxg前面的項分別為′ Gxg＋1，″ Gxg＋2，…，在Gxg后面的項分別為G′xg-1，G″xg-2，…；類似地，令Γxy前面的項為′Γxy＋1，″Γxy＋2，…，在Γxy后面的項為Γ′xy-1，Γ″xy-2，…。顯然，在（P）和（Q）/p的乘積中，項xg＋y的系數為GΓ＋′GΓ′＋″GΓ″＋…＋′ΓG′＋″ΓG″＋…

項GΓ是一個分數，如果用最簡分數的形式表達，它的分母中會含有p的t＋τ次冪。如果其他任意一項為分數，那么，它的最簡形式中的分母一定只能含有較低次的p的冪。因為，這些分母中的每一項都是兩個因數的乘積，而這兩個因數，要么是其中的一個含有的p的方冪不大于t，而另一個含有的p的方冪則小于τ；要么是其中的一個含有的p的方冪不大于τ，而另一個含有的p的方冪則小于t。因此，GΓ可表示為e/（fpt＋τ），而其他所有的項都可以表示為e′/（f′pt＋τ-δ），式中δ是正數，e，f，f′都不含因數p，這些項的和式為

它的分子不能被p整除，所以這個分數不可能經過簡化使其分母所含的p的方冪比t＋τ低。因此，在（P）和（Q）的乘積中，項xg＋y的系數為

即，這是一個分母含有p的t＋τ-1次冪的分數。證明完畢。

43

m次同余方程Axm＋Bxm-1＋Cxm-2＋…＋Mx＋N≡0，它的模是不能整除A的質數p，不能有多于m種不同的解法，即，它不能有多于m個對于p不同余的根（參考條目25和26）。

假如這條定理不成立，那么我們就有不同次數m，n，…的同余方程分別有多于m，n，…個根。設其中最低的次數是m，那么所有類似的較低次的同余方程都符合我們的定理。因為我們已經討論過一次同余方程（參考條目26），這里的m會大于或等于2。令同余方程

Axm＋Bxm-1＋Cxm-2＋…＋Mx＋N≡0

至少有m＋1個根x＝α，x＝β，x＝γ，…。我們假定（這是合理的）所有的數α，β，γ，…都是正的且小于p，并且α是其中最小的。現在在這個同余方程中令y＋α替換x，結果就是

A′ym＋B′ym-1＋C′ym-2＋…＋M′y＋N′≡0

顯然，如果y≡0，y≡β-α或y≡γ-α，…都能滿足同余方程，那么，所有這些根都各不相同，它們的個數為m＋1。但是因為y≡0是方程的根，N′能夠被p整除。因此，m個值β-α，γ-α，…中的每一個都將滿足同余方程

y（A′ym-1＋B′ym-2＋…＋M′）≡0（mod p）

由于這m個值都大于0小于p，所以它們也都將滿足

A′ym-1＋B′ym-2＋…＋M′≡0（mod p）（參考條目22）

即m-1次同余方程有m個根。而這與我們的定理矛盾（顯然A′＝A，所以滿足不能被p整除的要求），因為，我們已經假定對所有次數小于m的這樣的同余方程定理是成立的。

44

我們這里假定模p不能整除最高次項的系數，但定理并不限于這種情況。因為，如果首項系數，或者還有其他項的系數被p整除，可以安全地忽略這些項，原先的同余方程簡化為較低次的同余方程，除非這個同余方程的全部原系數均被p整除，否則首項系數將不被p整除，這同余方程就將是一個恒等的同余式，其未知數的值則完全不確定。

這個定理首先由拉格朗日提出和證明（Hist. Acad. Berlin，1768，第192頁）。此定理也出現在勒讓德的論文Recherches d，Analyse indeterminée中。在Novi comm. Acad. Petrop中，歐拉證明了同余方程xn-1≡0不存在多于n的不同的根。盡管這只是一種特例，但這位著名數學家使用的方法可以很容易應用于所有同余方程。他之前在Novi comm. acad. Petrop.上解決了一個更加特殊的情形，但這種方法不能應用于一般情形。在第8章^[5]，我們會演示證明這則定理的另一種方法。盡管乍一看來這些方法似乎不同，想要對這些方法做比較的專家會發現它們的原理都是一樣的；但是，因為這則定理在這里僅僅是作為一個引理來討論，并且對其完整闡述與本章的關系不大，因此我們不會停下來專門討論合數模。

---

[1] 這種關系可以更加普遍地討論，我們可能在其他情況下討論。這里我們只給出兩種對目前的探討有用的命題：
　　1）［α，β，γ，…，λ，μ］·［β，γ，…，λ］-［α，β，γ，…，λ］·［β，γ，…，λ，μ］＝±1，其中α，β，γ，…，λ，μ的項數為偶數時取＋號，項數為奇數時取-號。
　　2）數的順序可以顛倒：［α，β，γ，…，λ，μ］＝［μ，λ，…，γ，β，α］。證明簡單，這里略去。

[2] 它同樣可以表示為（mod 12）。

[3] 這條結論需要證明，但我們這里沒有給出。從我們的分析只能得出未知數x，y，…，的其他值一定不能解這個同余方程組，但我們并沒有證明這些值能夠滿足方程，因為這組方程可能是無解的。在處理線性方程組時也常出現類似錯誤。

[4] 如果把相似排列設想為表示在一個圓周上，使得最后一個元素與第一個元素相連，那么這些排列就完全一樣了，因為在圓周上沒有什么位置可以成為第一個或者最后一個。

[5] 第8章沒有發表。