小鱼干

V1

2022/04/25阅读:21主题:橙心

欧拉函数及其性质的证明

欧拉函数定义

中与 互质的数的个数被称为欧拉函数,记为

在算数基本定理中: ,则:

证明

的质因子, 的倍数有 ,共 个。同理。若 的质因子, 的倍数有 个。这 个数中,其中既是 的倍数,又是 的倍数的数有 个。根据容斥原理, 中去掉 的倍数:

类似的, 的全部质因子都能使用容斥原理实现,得到与 互质的数的个数。

证毕。

性质

  1. 中与 互质的数的和为
  2. 若a,b互质,则

证明性质1

为与 互质的数,则根据更相减损术原理, 。故,与n互质的x,n-x成对出现,总和为

性质1证毕。

证明性质2

算数基本定理中:

互质

各不相同

性质

是质数

证明性质3

因为 是质数, 的每个数都互质,故

证明性质4

为质数,

性质4证毕

证明性质5

为质数,

互质

为互质

性质5证毕

代码实现

int erla(int n){//利用线性筛更新欧拉函数值
 int cnt=0;//质数个数
 v[0]=v[1]=1;//标记0和1为非质数
 phi[1]=1;//记录1的欧拉函数值为1
 for(int i=2;i<=n;i++){//遍历2~n
  if(!v[i]){//i是质数
   prime[cnt++]=i;//存储i到质数表
   phi[i]=i-1;//性质3: p是质数,phi(p)=p-1
  }
  //遍历质数表
  for(int j=0;j<cnt&&prime[j]*i<=n;j++){
   v[prime[j]*i]=1;//标记质数与i的乘积为非质数
   if(i%prime[j]==0){//性质4:若p%i==0,phi(i*p)=p*phi(i)
    phi[i*prime[j]]=prime[j]*phi[i];
    break;
   }else{//性质5:若p%i!=0,phi(i*p)=(p-1)*phi(i)
    phi[i*prime[j]]=(prime[j]-1)*phi[i];
   }
  }
 }
 return cnt;//返回质数个数
}

分类:

数学

标签:

数学编程

作者介绍

小鱼干
V1