設(shè)n有質(zhì)因子分解式n=p1^n1*p2^n2*...*pk^nk,其中p1,p2,..,pk是質(zhì)數(shù).
在1到p1^n1這些數(shù)中與p1不互質(zhì)有p1的如下倍數(shù),
p1,2p1,3p1,...,p^(n1-1)*p1.
于是1到p1^n1與p1互質(zhì)共有p1^n1-p1^(n1-1)=p1^(n1-1)(p1-1)個數(shù),
同理在1到p2^n2這些數(shù)中與p2互質(zhì)共有p2^(n2-1)(p2-1)個數(shù),
...
在1到pk^nk這些數(shù)中與pk互質(zhì)共有pk^(nk-1)(pk-1)個數(shù),
則小于n且與n互質(zhì)的自然數(shù)的個數(shù)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這些數(shù)中與2互質(zhì)共有2^2(2-1)=4,如1,3,5,7
在1到9這些數(shù)中與3互質(zhì)共有3^1(3-1)=6,如1,2,4,5,7,8
在1到5這些數(shù)中與5互質(zhì)共有5^0(5-1)=4,如1,2,3,4
與360互質(zhì)共有4*6*2=48個.
由于n>2,則必有一個質(zhì)數(shù)大于2,是奇質(zhì)數(shù),p1-1,p2-1,..,pk-1必有一個是偶數(shù),故A(n)必是偶數(shù).