38
问题
求小于给定正数A ，且与A 互质的正数的个数。
为了简便，我们在给定的数前面加上前缀φ 来表示与之互质且小于它的正数的个数。因此，我们求φA 。
1．当A 为质数，显然所有从1到A -1的数都与A 互质，那么在这种情况下
φA ＝A -1
2．当A 是质数幂，例如A ＝p m ，所有能被p 整除的数都与A 不互质，但是其他的数都与A 互质。所以在p m -1个数中，必须摒弃这些数：p ，2p ，3p …（p m -1 -1）p 。因此剩下的数有p m -1-（p m -1 -1）个，即p m -1 （p -1）个。则
φA ＝p m -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 的方幂。令这一项为Gx g ，并且令G 的分母中p 的方幂等于t 。在（Q ）/p 中可以找到相似的一项。令这一项为Γx y ，并且令Γ 的分母中p 的方幂等于τ 。显然，t ＋τ 的值至少等于2。现在我们证明在（P ）和（Q ）的乘积中的项x g ＋y 的系数是分数，分母含p 的t ＋τ -1次幂。
令（P ）中在Gx g 前面的项分别为′ Gx g ＋1 ，″ Gx g ＋2 ，…，在Gx g 后面的项分别为G ′x g -1 ，G ″x g -2 ，…；类似地，令Γx y 前面的项为′Γx y ＋1 ，″Γx y ＋2 ，…，在Γx y 后面的项为Γ ′x y -1 ，Γ ″x y -2 ，…。显然，在（P ）和（Q ）/p 的乘积中，项x g ＋y 的系数为GΓ ＋′GΓ ′＋″GΓ ″＋…＋′ΓG ′＋″ΓG ″＋…
项GΓ 是一个分数，如果用最简分数的形式表达，它的分母中会含有p 的t ＋τ 次幂。如果其他任意一项为分数，那么，它的最简形式中的分母一定只能含有较低次的p 的幂。因为，这些分母中的每一项都是两个因数的乘积，而这两个因数，要么是其中的一个含有的p 的方幂不大于t ，而另一个含有的p 的方幂则小于τ ；要么是其中的一个含有的p 的方幂不大于τ ，而另一个含有的p 的方幂则小于t 。因此，GΓ 可表示为e /（fp t ＋τ ），而其他所有的项都可以表示为e ′/（f ′p t ＋τ -δ ），式中δ 是正数，e ，f ，f ′都不含因数p ，这些项的和式为
它的分子不能被p 整除，所以这个分数不可能经过简化使其分母所含的p 的方幂比t ＋τ 低。因此，在（P ）和（Q ）的乘积中，项x g ＋y 的系数为
即，这是一个分母含有p 的t ＋τ -1次幂的分数。证明完毕。
43
m 次同余方程Ax m ＋Bx m -1 ＋Cx m -2 ＋…＋Mx ＋N ≡0，它的模是不能整除A 的质数p ，不能有多于m 种不同的解法，即，它不能有多于m 个对于p 不同余的根（参考条目25 和26 ） 。
假如这条定理不成立，那么我们就有不同次数m ，n ，…的同余方程分别有多于m ，n ，…个根。设其中最低的次数是m ，那么所有类似的较低次的同余方程都符合我们的定理。因为我们已经讨论过一次同余方程 （参考条目26） ，这里的m 会大于或等于2。令同余方程
Ax m ＋Bx m -1 ＋Cx m -2 ＋…＋Mx ＋N ≡0
至少有m ＋1个根x ＝α ，x ＝β ，x ＝γ ，…。我们假定（这是合理的） 所有的数α ，β ，γ ，…都是正的且小于p ，并且α 是其中最小的。现在在这个同余方程中令y ＋α 替换x ，结果就是
A ′y m ＋B ′y m -1 ＋C ′y m -2 ＋…＋M ′y ＋N ′≡0
显然，如果y ≡0，y ≡β -α 或y ≡γ -α ，…都能满足同余方程，那么，所有这些根都各不相同，它们的个数为m ＋1。但是因为y ≡0是方程的根，N ′能够被p 整除。因此，m 个值β -α ，γ -α ，…中的每一个都将满足同余方程
y （A ′y m -1 ＋B ′y m -2 ＋…＋M ′）≡0（mod p ）
由于这m 个值都大于0小于p ，所以它们也都将满足
A ′y m -1 ＋B ′y m -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 中，欧拉证明了同余方程x n -1≡0不存在多于n 的不同的根。尽管这只是一种特例，但这位著名数学家使用的方法可以很容易应用于所有同余方程。他之前在Novi comm. acad. Petrop .上解决了一个更加特殊的情形，但这种方法不能应用于一般情形。在第8章 [5] ，我们会演示证明这则定理的另一种方法。尽管乍一看来这些方法似乎不同，想要对这些方法做比较的专家会发现它们的原理都是一样的；但是，因为这则定理在这里仅仅是作为一个引理来讨论，并且对其完整阐述与本章的关系不大，因此我们不会停下来专门讨论合数模。
[1] 这种关系可以更加普遍地讨论，我们可能在其他情况下讨论。这里我们只给出两种对目前的探讨有用的命题：
1）［α ，β ，γ ，…，λ ，μ ］·［β ，γ ，…，λ ］-［α ，β ，γ ，…，λ ］·［β ，γ ，…，λ ，μ ］＝±1，其中α ，β ，γ ，…，λ ，μ 的项数为偶数时取＋号，项数为奇数时取-号。
2）数的顺序可以颠倒：［α ，β ，γ ，…，λ ，μ ］＝［μ ，λ ，…，γ ，β ，α ］。证明简单，这里略去。
[2] 它同样可以表示为 （mod 12）。
[3] 这条结论需要证明，但我们这里没有给出。从我们的分析只能得出未知数x ，y ，…，的其他值一定不能解这个同余方程组，但我们并没有证明这些值能够满足方程，因为这组方程可能是无解的。在处理线性方程组时也常出现类似错误。
[4] 如果把相似排列设想为表示在一个圆周上，使得最后一个元素与第一个元素相连，那么这些排列就完全一样了，因为在圆周上没有什么位置可以成为第一个或者最后一个。
