逐步淘汰原則

逐步淘汰原則（successive sweep principle ）亦稱容斥原理，這是數論和組合理論的重要方法。在數論中，常常遇到一些計數問題，這些計數問題往往歸結為計算一個有限集S中不屬於某些指定子集的元素的個數。套用逐步淘汰原則，可以很容易得到計算歐拉函式的重要公式。

基本介紹

• 中文名：逐步淘汰原則
• 外文名：successive sweep principle 
• 別名：容斥原理
• 概述：不屬於有限集某些子集的元素個數
• 套用領域：數論、組合理論
• 學科：數學

定義

設 是一個非空的含有有限多個元素的集合， 為一個正整數， 是 的 個子集。若以 表示 中具有性質 的元素全體構成的集合，則可知：在 中既不具有性質 ，又不具有性質 ，...，又不具有性質 的元素的個數為

上述計數表達式通常被稱為逐步淘汰原則（或容斥原理）。

證明

我們用 表示任一個有限集合 中元素的個數。若 為空集，則令 。

設 是一個非空的含有有限多個元素的集合， 為一個正整數， 是 的 個子集，則可以證明

上式可以從相應於 時的關係式（ 與 為 的任意子集）

經套用數學歸納法而獲得證明。

若用 表示 的任一子集 在 中的余集（即 是由 中的不在 中的元素構成的），則有

現在，若以 表示 中具有性質 的元素全體構成的集合，則可知：在 中既不具有性質 ，又不具有性質 ，...，又不具有性質 的元素的個數為

舉例

例如，若 表示正整數， ，集合 定義為

則不超過 且既不能被3除盡，也不能被5除盡的正整數的個數為（注意： ）

Euler函式的計算公式

套用逐步淘汰原則，就很容易得到計算歐拉函式 的重要公式。

Euler函式的定義：模 的同餘類 稱為是模 的既約 （或互素）同餘類，如果 。模 的所有既約同餘類的個數記作 ，通常稱為Euler函式。

定理 若 是不同的素數，則