第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章没有发表。