欧拉函数级反演公式.pptx

欧拉函数及反演公式,主要内容,一、欧拉函数,二、麦比乌斯反演公式及其原理,三、多项式及矩阵反演公式,一、欧拉函数,设为素数，为正整数，则有,=1=(11),进一步，若正整数有标准因数分解式,=|=1122,一、欧拉函数,=(111)(112)(11),欧拉函数能干什么呢？,我们来看这样一个例题,一、欧拉函数,为正整数，1,，求使得gcd,为素数的有序对(,)的个数。,显然用欧拉函数非常简单,如果将上面的条件改为1，1ym又该怎么做呢？,二、麦比乌斯反演公式及其原理,我们先看这样一个函数,其中()和f()都是定义在正整数集上的两个函数,二、麦比乌斯反演公式及其原理,根据F(n)的定义，我们显然有：F(1)=f(1)F(2)=f(1)+f(2)F(3)=f(1)+f(3)F(4)=f(1)+f(2)+f(4)F(5)=f(1)+f(5)F(6)=f(1)+f(2)+f(3)+f(6)F(7)=f(1)+f(7)F(8)=f(1)+f(2)+f(4)+f(8),二、麦比乌斯反演公式及其原理,我们用F(n)表示f(n),f(1)=F(1)f(2)=F(2)-F(1)f(3)=F(3)-F(1)f(4)=F(4)-F(2)f(5)=F(5)-F(1)f(6)=F(6)-F(3)-F(2)+F(1)f(7)=F(7)-F(1)f(8)=F(8)-F(4),二、麦比乌斯反演公式及其原理,麦比乌斯反演公式,其中为麦比乌斯函数,=1=1(1)=12为互异素数0其他,二、麦比乌斯反演公式及其原理,()具有以下性质：,性质1,性质2,二、麦比乌斯反演公式及其原理,现在我们来证明莫比乌斯反演定理,其中用到了性质1,麦比乌斯公式的另一种形式,|=|=|()|()=(),二、麦比乌斯反演公式及其原理,有了这个公式我们能干什么？,对于一些函数f(n)，如果我们很难直接求出它的值，而容易求出倍数和或约数和F(n)，那么我们可以通过莫比乌斯反演来求得f(n)的值例：f(n)表示某一范围内(x,y)=n的数对的数量，F(n)表示某一范围内n|(x,y)的数对的数量那么直接求f(n)并不是很好求，而F(n)求起来相对无脑一些，我们可以通过对F(n)进行莫比乌斯反演来求得f(n),二、麦比乌斯反演公式及其原理,m为正整数，1，1ym，求使得gcd,为素数的有序对(,)的个数。,麦比乌斯公式的另一种形式,三、多项式及矩阵反演公式,=0=0,设n是一个自然数()和()为满足条件=0，=0的两个n次多项式序列，且ii0,0则,三、多项式及矩阵反演公式,证明：令=(0,1,),=(0,1,)=(0,1,),=(0,1,)将已知条件以矩阵形式表示为,三、多项式及矩阵反演公式,于是=由于|=0,1,2,是线性空间R的一组基，所以=，于是1=所以=1=,三、多项式及矩阵反演公式,该式即为为矩阵反演公式。,已知A为阶非奇异阵，D为m阶非奇异阵，B为阶矩阵，C为m阶矩阵，且+1与+1均为非奇异阵，则：,(+1)1=11(+1)11,三、多项式及矩阵反演公式,令=+1（1）将上式两边左乘1，得=1+11（2）式中的为单位阵，将上式两边右乘1，得1=1+111（3）在将上式两边右乘，得1=1+111（4）整理得1=11(+1)（5）,证明(+1)1=11(+1)11,将上式两边右乘(+1)1得1(+1)1=11（6）再将上式两边右乘1，得1(+1)11=111（7）根据（3）式可知11=111