海之美文新闻资讯逐步淘汰原则
逐步淘汰原则（successive sweep principle ）亦称容斥原理，这是数论和组合理论的重要方法。在数论中，常常遇到一些计数问题，这些计数问题往往归结为计算一个有限集S中不属于某些指定子集的元素的个数。套用逐步淘汰原则，可以很容易得到计算欧拉函式的重要公式。
基本介绍
- 中文名：逐步淘汰原则
- 外文名：successive sweep principle
- 别名：容斥原理
- 概述：不属于有限集某些子集的元素个数
- 套用领域：数论、组合理论
- 学科：数学
定义
设
是一个非空的含有有限多个元素的集合，
为一个正整数，
是 的 个子集。若以
表示 中具有性质
的元素全体构成的集合，则可知：在 中既不具有性质
，又不具有性质
，...，又不具有性质
的元素的个数为
证明
我们用
表示任一个有限集合
中元素的个数。若 为空集，则令
。
设 是一个非空的含有有限多个元素的集合， 为一个正整数， 是 的 个子集，则可以证明
若用
表示 的任一子集
在 中的余集（即 是由 中的不在 中的元素构成的），则有
举例
例如，若
表示正整数，
，集合
定义为
Euler函式的计算公式
套用逐步淘汰原则，就很容易得到计算欧拉函式
的重要公式。
Euler函式的定义：模
的同余类
称为是模 的既约 （或互素）同余类，如果
。模 的所有既约同余类的个数记作
，通常称为Euler函式。
定理 若
是不同的素数，则
