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的整数倍的元素，因此$A\cup B$={p,2p…(q-1)p, q,2q,…(p-1)q}，元素个数为**(q-1)+(p-1)**,所以

$ϕ(n)=(pq-1)-((q-1)+(p-1))=(p-1)*(q-1)=ϕ(p)*ϕ(q)$

证明完