定理:
任何正整数n等于其因数的欧拉函数值之和,即∑d|nφ(d)=n
证明:
设一个集合{1/n,2/n,3/n,...,(n-1)/n,n/n}
对于上述的分式集合,若我们都将其化简至最简形式,设其中一个最简形式是a/b,那么我们一定有:
b|n ①
(a,b)=1 ②
a<=b ③
由②③可得,对于一个确定的b,它对应的a的个数为φ(b)(根据欧拉函数的定义:φ(n)=1到n中与n互质的数的个数)
那么我们再考虑,每一个最简形式a/b都是互相不同的,因为它们都是最简形式
而且,对于上述分数集合来说每一个元素都可以化简成最简形式(完备性),而元素的个数正好就是n
于是定理得证