积性函数系列(一):欧拉函数

November 14, 2014 at 1:23 am

本系列是数论篇章的第一篇(于是又挖了一个数论的坑orz),主要介绍、证明初等数论中一些重要的概念、结论。 在微积分学领域,积性函数指的是具有的函数,在数论领域这个概念略有不同,仅定义在正整数上,它揭示了整数的很多性质。废话不多说,直奔主题。 为了区分通常意义上的函数,我们定义算数函数: 定义1.1 定义在所有正整数上的函数称为算数函数。 在整个积性函数篇里,不加说明地,我们总是讨论算数函数。 定义1.2 算术函数如果满足对于任意两个互质的正整数和,均有,就称为积性函数(或乘性函数)。如果对于任意两个正整数和,均有,就称为完全积性函数。 很容易找到一些trivial的积性函数,如,事实上所有的幂函数都是积性函数。 结合积性函数的定义和算数基本定理,很容易得到下面的定理: 定理1.1 如果是一个积性函数,对于任意的正整数有素数幂分解,那么有 证明:略,使用数学归纳法即可。 好了,介绍完了积性函数的基本概念,就开始介绍今天的主角,欧拉函数,它也被称为欧拉函数。顾名思义,它是由欧拉首先研究的。 定义1.3 欧拉函数定义为不超过且和互质的正整数的个数。 下面我们就来探讨欧拉函数在各个点上的取值。很容易得到对于素数,,那么反过来是不是也成立呢? 定理1.2 如果是素数,那么.反之,如果是正整数且满足,那么是一个素数。 证明:前句可由互质定义得到,我们只证明后句。若不是素数,那么或是1或是合数。而,但若是合数,得有因子,而不与自身互质,这使得和互质的数至多只有个,所以也不可能,故是素数。 […]