逐步淘汰原则

---

这是数论和组合理论的重要方法。

在数论中，常常遇到一些计数问题，这些计数问题往往归结为计算一个有限集S中不属于某些指定子集的元素的个数。例如，求1000以内不能被4也不能被5整除的整数的个数，设，则所求个数等于｜S｜－｜S₁｜－｜S₂｜+｜S₁S₂｜=1000－250－200+50=600，这里记号｜A｜表示集A中元素的个数，S₁∩S₂简记为S₁S₂。

一般地说，设S₁，S₂，…，S_n是S的n个子集，T是S的一个子集，S＼T表示S中不在T中元素的集，故表示S中所有不属于S₁，S₂，…，S_n中任一个的元素的集。则集的元素的个数

这就是逐步淘汰原则。

应用逐步淘汰原则，就很容易得到计算欧拉函数φ(n)(即0，1，2，…，n－1中与n互素的数的个数)的重要公式：设，则

若取，由于当d｜n时，S中有n／d个d的倍数，故S_j｜=n／pj，｜s_is_j｜=n／p_ip_j，…，｜s_is₂…s_k｜=n／p₁…p_k，由逐步淘汰原则可得

应用逐步淘汰原则，还可以得到以下重要结果：(1)设整数n＞1，d＞0和r，其中d／n且(r，d)=1，则集S=｛r+td，t=1，2，…，n／d｝中与n互素的数的个数是φ(n)／φ(d)；(2)若a，b，…，k，1为任意非负整数，则max(a，b，…，k，1)=a+b+…+k+1－min(a，b)－min(a，c)－…－min(b，c)－…－min(k，1)+min(a，b，c)+…－…+…±min(a，b，…，k，1)