莫比乌斯变换.ppt

2017-2-3莫比乌斯变换上海大学沈云付 ******@. 上海大学计算机工程与科学学院 1、引言莫比乌斯变换?1)复平面上的莫比乌斯变换?公元 1858 年,德国数学家莫比乌斯(Mobius , 1790 ~1868) 发现:把一个扭转 180 °后再两头粘接起来的纸条,具有魔术般的性质。这样的纸带只有一个面(即单侧曲面),一只小虫可以爬遍整个曲面而不必跨过它的边缘!这种由莫比乌斯发现的神奇的单面纸带,称为“莫比乌斯带”。?几何学中的莫比乌斯变换: ?其中 z, a, b, c, d 为复数且满足 ad?bc?0. 2017-2-3 d cz baz zf???)(1、引言莫比乌斯变换?2)数论中的莫比乌斯变换?对于给定的数论函数 f (n) ,( n?N),定义新的数论函数?称 F(n) 为 f(n) 的莫比乌斯变换,而 f(n) 为 F(n) 的莫比乌斯逆变换。 2017-2-3 ?? nddfnF |)()(2、数论莫比乌斯变换计算实例? 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) 2017-2-3 莫比乌斯逆变换计算实例? 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) 2017-2-3 3、逆变换与莫比乌斯函数?观察发现 f(n) 的表示式中有形式为? F(n/d) 的项。?引入莫比乌斯函数?(n) ,记?(d) 为? F(n/d) 的符号+或-之一?有?(1)= ?(6)=1, ?(2)= ?(3)= ?(5)= ?(7)=-1 ,?(4)= ?(8)=0 。?若p是素数,由 F(p)=f(1)+f(p) ,得 f(p)=F(p)-F(1) ,因此?(p)=-1 。?继续观察, F(p 2 )=f(1)+f(p)+f(p 2 ) ,得 f(p 2 )=F(p 2 )-(F(p)- F(1))-F(1)=F(p 2 )-F(p) ,这又有?(p 2 )=0 。?同理推出, f(p 3 )=F(p 3 )-F(p 2),这又有?(p 3 )=0 ,继续推下去,有当 k>1 ,有?(p k )=0 。 2017-2-3 ?? ndd nFdnf |)()()(?莫比乌斯函数?(n) ?继续观察: ?设p 1,p 2为不同素数? F(p 1*p 2 )=f(p 1*p 2 )+f(p 1 )+f(p 2 )+f(1) ,得 f(p 1*p 2 )=F(p 1*p 2 )-F(p 1 )-F(p 2 )+F(1) 。?这里有?(1)=1, ?(p 2 )=-1, ?(p 1 )=-1, ?(p 1*p 2 )=1 。 2017-2-3 莫比乌斯函数?(n) ?总结得 2017-2-3 ?????????其它为不同素数、、、, r r rppppppn nd ... ... 10 )1( 1)( 2121?积性函数?积性函数 f(n) :对数论函数 f(n) ,如果满足对任意正整数 m,n,只要 gcd(m,n)=1 ,就有 f (mn)=f(m)f(n) ,那么称 f(n) 为积性函数?完全积性函数 g(n) :对数论函数 g(n) ,如果满足对任意正整数 m,n,均有 g (mn)=g(m)g(n) ,那么称 g(n) 完全积性函数 2017-2-3 莫比乌斯函数的性质?莫比乌斯函数是积性函数,即 gcd(m,n)=1 ,则?(mn)= ?(m) ?(n) ; gcd (m,n)>1 ,则?(mn)=0 ; f(n)=1 的特例, 证明:首先?(n) 是积性函数,因此用下面将证明的一个命题可知 I(n) 也是积性函数。显然, I(1)=1; 而对素数 p, I(p t )=1+ ?(p)+ ?(p 2 )+…+?(p t) =1-1+0+ …+0=0. 证毕 2017-2-3 ????????? 10 11] 1[)()( |n nn dnI nd?