1 欧拉函数ϕ(n)表示小于n且与n互素的正整数的个数,且习惯上有ϕ(1)=1。
2 显然,对素数p,有ϕ§=p-1
3 证明ϕ(n)=ϕ(pq)=ϕ§ * ϕ(q)=(p-1)(q-1): p,q为素数,证明如下
因为n=p*q,易得小于n的数正整数的集合S={1,…(pq-1)},一共有pq-1个元素,其中不与n互素的集合为A={p,2p,3p…(q-1)p}与B={q,2q,…(p-1)q}。且这两个集合没有重复元素,因为p和q都是素数,在集合A中找不到是q的整数倍的元素,同理在集合B中也找不到是p的整数倍的元素,因此={p,2p…(q-1)p, q,2q,…(p-1)q},元素个数为**(q-1)+(p-1)**,所以
证明完