尤拉函式的等價命題為什麼可以這麼表示

1樓：beanandbean

這道題的解法隱含了令全集的假定。也就是說對於解中所考慮的集合，其補集所表示的其實是

而非用全體自然數減去得到的補集。（注意到原解中定義時所寫的不等式為小於而非小於等於，不確定是否為筆誤，但是考慮到對於任意正整數，有與互素，因此顯然不能整除的素因子。所以定義時寫小於號和小於等於號都沒有影響）

這裡，我們可首先令

那麼顯然有。現在考慮任意，即且與不互素，那麼根據互素的定義，與的最大公倍數必定大於等於。因此，與的最大公倍數有至少乙個素因子，而它的任意素因子必然都是的素因子，也就是說存在整除。

上述關係的逆命題顯然成立，也就是說當且僅當存在整除，當且僅當在某個中。所以當且僅當不在所有集合中，也即

因此我們就得到原解中與各個之間的關係式。

原解中計算的方法為直接應用包含排斥定理，該定理通過數學歸納法證得了的大小為各個大小之和，減去所有任意一對集合之交大小之和，再加上所有任意三個集合之交，再減去......如此繼續，直到計算到全部個集合之交位置。現在，易於看出，

因此求只需用減去上述計算的結果即可，最終表示式就如原解中所列。

不過我覺得包含排斥原理即使理解了其思想，對於題中這種總集合數為變數的情況，對表示式進行化簡和因式分解，即說明為何最終結果等於也是一件頗為繁瑣的事情。我們一般傾向於用另一種方式推導尤拉函式的求值公式：

首先，考慮為單個素數的冪的情況，即，其中為素數，為正整數。

此時，對於任意，假設和不互素，則其最大公因數是的因子，也就必定是的某個正整數冪——因此顯然可以直接斷言任意與不互素當且僅當是的倍數。現在，到中共有個的倍數，也就是說與互素的數共有個。

接下來，考慮可分解為互素的兩數，即，其中與互素（但都不一定是素數）：

對於任意，顯然與互素當且僅當與、與都互素。我們知道對於任意整數，與的最大公因數等於與的最大公因數，因此與互素當且僅當除以的餘數與互素；與也同理，因此與互素當且僅當除以的餘數與互素、除以的餘數與互素。現在，除以得到的餘數都在到的範圍裡，因此與互素的餘數共有個，與互素的餘數同理共有的。

根據中國剩餘定理，在和互素的情況下，到的整數和除以、除以得到的餘數的有序對成一一對應關係，因此可求得到中與互素的數的個數為。

在此簡單提及一下中國剩餘定理的證明：

最後，將任意正整數寫作，由於乙個素因子冪都顯然與其前方的互素，所以用數學歸納法易於得到

上式顯然可化為，也即原解中出現的形式。

其實來說，比起原解中出現的形式，我覺得有時甚至更為常用。比如寫作，因此可直接寫出，免去了分數的計算。