关于几个数学定理的推导及证明

关于欧拉函数线性筛法的证明

设p为素数,线性筛法现在筛到i

1.i为素数,phi(i)=i-1

[1,i]中只有i与i不互质

2.i%p==0时,有phi(ip)=phi(i)p

先证明一个定理

若整数n不与i互质,n+i依然与i不互质

3.i%p!=0,phi(ip)=phi(i)phi(p)=phi(i)*(p-1)

此时i与p互素,由于欧拉函数是积性函数且(i,p)=1

(未完待续)

本文总阅读量