设n有质因子分解式n=p1^n1*p2^n2*...*pk^nk,其中p1,p2,..,pk是质数.
在1到p1^n1这些数中与p1不互质有p1的如下倍数,
p1,2p1,3p1,...,p^(n1-1)*p1.
于是1到p1^n1与p1互质共有p1^n1-p1^(n1-1)=p1^(n1-1)(p1-1)个数,
同理在1到p2^n2这些数中与p2互质共有p2^(n2-1)(p2-1)个数,
...
在1到pk^nk这些数中与pk互质共有pk^(nk-1)(pk-1)个数,
则小于n且与n互质的自然数的个数A(n)=p1^(n1-1)(p1-1)*p2^(n2-1)(p2-1)...*pk^(nk-1)(pk-1),
例如:
360=2^3*3^2*5
在1到8这些数中与2互质共有2^2(2-1)=4,如1,3,5,7
在1到9这些数中与3互质共有3^1(3-1)=6,如1,2,4,5,7,8
在1到5这些数中与5互质共有5^0(5-1)=4,如1,2,3,4
与360互质共有4*6*2=48个.
由于n>2,则必有一个质数大于2,是奇质数,p1-1,p2-1,..,pk-1必有一个是偶数,故A(n)必是偶数.