关于欧拉函数及其一些性质的美妙证明

欧拉函数是数论中最重要也是最基础的一个函数，这个函数的很多性质及其证明虽然基础，但是显得很“烧脑”，一些数学爱好者往往看了不少资料，最终仍然“莫名其妙”，不能理解它的奥妙所在。这回，我努力用一些更容易看懂的方式，来证明（或者叫说明）欧拉函数许多有趣的性质。希望大家能从中体会到，数学之美、逻辑之美像艺术之美一样，深刻而美妙，值得欣赏。

一、什么是欧拉函数？

欧拉是一位极其伟大的数学家，他一生建树颇多，在数论领域也有着很多贡献。欧拉函数就是以他的名字命名的一个数论中的极其基础同时也极其重要的函数。欧拉函数的概念简单易懂，但是带来的性质却让人很难一眼看穿，这也是数论基础知识中很有思维乐趣的地方。

对于一个正整数n，欧拉函数被定义为小于等于n且与n互质的正整数的个数，记为

注意，上面说的“小于等于n”的“等于”仅在n=1时才出现，n>1时，n不会与自身互质。

对于较小的数，欧拉函数很容易手工计算，比如与1、2互质的数只有1，与3互质的数有1和2两个，与4互质的数有1和3两个，与5互质的数有1、2、3、4共4个，与6互质的数有1和5两个，于是：

从上面可以看出，欧拉函数值肯定是一个正整数，但是欧拉函数不是一个增函数，更不是一个严格增函数。欧拉函数定义简单明确，却具有很多奇妙的性质。

二、欧拉函数的两个有趣性质

1、如果正整数a与n互质，那么

这个性质叙述上很简单，但是如果有谁能够立刻明白为什么，或者能够直接判断此性质成立，那么这个人一定具有极为良好的数学直觉和极佳的数学天赋！绝大多数人都很难自行证明这个性质。下面给出一个美妙且并不复杂的证明。

既然小于n且与n互质的数有个，那么我们设这个数是。它们每个数都小于n。

然后我们考察这个数与a相乘得到的新的个数，它们为中任意两个数的差都不能被n整除。这是因为任意两个数的差是，其中a与n互质，又小于n。

这意味着新的个数除以n得到的余数两两不相同。

另外，由于每个都与n互质，a也与n互质，这就是说每个都与n互质。我们知道，与n互质的数除以n得到的余数也必然与n互质。也就是说，这新的个数除以n得到的余数都是小于n且与n互质的数。

而小于n且与n互质的数正好就是

所以我们知道，新的个数除以n的余数就是当然，不见得恰巧顺序也一一对应。

有了这个结论，我们显然可以得到以下同余式成立，

即

即

这个性质又被叫做欧拉定理，是数论中非常有名、非常基础的定理。在比欧拉早几十年的一个著名大牛民间数学家费马曾经得到了一个定理，对于正整数a和素数p，如果p不能整除a，那么

可以被看作是欧拉定理的一个特例。因为对于素数p，。

有一个与我们日常生活息息相关的非对称加密算法——RSA算法，就是基于欧拉定理设计出来的。感兴趣的朋友可以在网上查一下RSA算法的原理，很容易就可以利用欧拉定理给出证明。

2、对于每个能够整除n的正整数d，其欧拉函数之和恰好为n。或者说，n的所有因子的欧拉函数之和等于n。

这个性质用数学公式表示为，

这个性质更不容易立刻想通了。从基本概念出发，n的每个因子d，小于d且与d互质的正整数的个数加在一起，居然恰好等于n，好神奇！？

我们验证一下一个小一点的数字，比如n=10，那么n的因子有1、2、5、10。容易计算得到，

把它们加起来，恰好结果是10。

这个性质用一些高等的数学工具会给出更精炼的证明，不过涉及到的数学知识会深一些。下面我给出的这个证明，相信对于具有扎实初中数学基础的数学爱好者，都应该可以看懂。无论是使用深一些的数学知识还是更初等的数学知识证明，其数学实质都是一样的。

我们首先设n的全部因子为d₁、d₂、…、d_k。对于每个d_i，我们再设与d_i互质且小于等于d_i的个数为

显然，所有的数对们的个数就是要计算的。

下面，我们定义两个集合，并在这两个集合之间建立一一对应，如果这个一一对应建立成功，就说明这两个集合中元素的个数是一样多的，从而就证明了命题。

定义集合，即A是全部的集合。

定义集合B={1,2,…,n}，就是前n个正整数的集合。

下面在集合A到B之间建立一个映射，

f (A->B) : (

这个映射是可以成立的，因为任意1，所以，而且是整数，所以必然是一个1到n之间的整数。

下面我们来证明这个映射是一个一一对应（双射）。这只需要证明两点，一是A中不同的元素映射成的B中的元素也不同（单射），二是B中每个元素都有A中元素来对应（满射）。

先来证明第一点（单射成立）。

A中的两个不同元素有两种情况，一是i相同但j不同，设为(和(，j

此时显然，所以，所以对应的B中元素不同。

二是i就不同，设为和，，也即。因为只要i不同，相应的数对就不同，所以这种情况下无须要求。

这两个A中元素对应的B中元素分别是和，如果它们相等，有

因为与互质，因此上面等式成立意味着要整除；同理，因为与互质，因此上面等式成立意味着要整除。这就是说，，这意味着，因此与矛盾。

于是这种情况下对应的B中元素也不相同。（单射得证）

再来证明第二点（满射成立）。

对于B中任意元素m，令m与n的最大公约数是g。那么显然与互质，且。于是（）这个数对必然是集合A中的一个元素，且按照映射f，这个元素映射到B中的元素就是m。

于是，B中任意元素都会被A中元素对应到。（满射得证）

综上，映射f是一个从集合A到集合B的一一对应，因此A中元素个数与B中元素个数相同。也即下式成立。

这个性质的证明较有思维乐趣，也反映了性质成立的本质原因。

三、欧拉函数的计算公式

看到了欧拉函数和它的一些奇妙性质，很多人都会希望知道欧拉函数有没有什么通项公式或者计算公式，比如能够直接用n来表示。遗憾的是这个难度太大，事实上，如果不知道n的质因数分解，是无法计算的。

为了计算，我们由浅入深的思考一下欧拉函数的各种情况。

结论1、如果n是一个素数，这种情况最简单。

设n=p，p为素数。此时显然等于p-1。这是因为从1到p，除了p以外的数都与p互质。即。

结论2、如果n是一个素数的α次幂

设，那么从1到n中，只有含素因子p的数不与n互质，其它数都与n互质。含有素因子p的数就是能被p整除的数，也就是p的倍数。那么从1到n有多少个p的倍数呢？显然，p、2p、3p、……、、，这些都是p的倍数，一直到为止。数一数就知道，一共有个p的倍数。

于是，此时。

从这两种情况我们发现，当表达为时，这两种情况下的计算公式是一样的。

结论3、稍微复杂一点的情况，n是两个素数的乘积。

设，这里q是另外一个素数。显然，此时与n互质的数必须不包含素因子p和q，也就是说既不能是p的倍数，也不能是q的倍数。类似上面2中的分析，p倍数应有q个，q的倍数有p个，但是还多算了一个即是p的倍数也是q的倍数的数，就是n自己。这样，小于等于n且包含质因子p或q的数共有p+q-1个。于是，

注意观察的话，还可以发现，

结论4、再扩展一步，n是某个数m和一个与m互质的素数p的乘积。

此时，小于等于n且与n互质的数必须是即与m互质也与p互质的数。

我们首先看小于等于n（也即m*p）且与m互质的数。任何与m互质的数除以m的余数也必然与m互质，反之也如此，一个数除以m的余数如果与m互质，那么这个数就与m互质。所以，如果某个小于m的数r与m互质，那么任意k*m+r都与m互质。在小于m*p的数里面，这样的数有r、m+r、2m+r、…、（p-1）m+r，共计p个。如果我们把n个数写成一个m*p的矩阵，容易发现这正好是这个矩阵第r列的p个数。

再看这p个数中，有哪些与p互质呢？类似前面证明中的思路，这p个数任意两个数之差都是一个小于p的数与m的乘积，由于m与p互质，因此任意两个数之差都不是p的倍数。也就是说，这p个数除以p的余数两两不相同，或者说，这p个数除以p的余数组成的集合正好是{0、1、…、p-1}。我们知道，因为p是素数，只要一个数除以p的余数不为0（也就是不能被p整除），那么这个数就与p互质。所以，这p个数中，除了那个除以p余数为0的数以外，其余p-1个数都与p互质。

好了，既然这么凑巧，每个r对应的一列与m互质的数之中，恰巧都有p-1个与p也互质的数，就是说，这一列与n（即m*p）互质的数有p-1个。这样的列有多少呢？显然，就是小于m且与m互质的数的个数，也就是列。

于是，我们得到，此时

结论5、最后一种情况，如果n=m*p，p是素数，但是p不与m互质呢？

这时，显然p|m（p整除m）。这种情况其实比上一种情况还要简单，是因为既然素数p是m的因子，那么任何与m互质的数都与p互质。

我们仍然观察4中的矩阵，可以知道，对于任意一列r（r与m互质），其中的r、m+r、2m+r、…、（p-1）m+r都与p互质（因为它们都与m互质）。所以，这一列中与n（即m*p）互质的数有p个。这样的列仍然有个，于是此时

好，大功告成！有了1～5这些结论，我们可以给出任意的计算公式了。

设，则

由上式可见，一个整数的欧拉函数不仅仅与这个整数有关，还与这个整数的质因数分解有关，这是欧拉函数的一个重要特点。

四、欧拉函数的其它性质

如果对数论或者对欧拉函数感兴趣，喜欢认真研究一下的话，就会发现，欧拉函数还有很多有趣的性质。这里列举几个，感兴趣的朋友可以自己证明一下。

1、当m和n互质时【记作(m,n)=1，或gcd(m,n)=1，就是m和n的最大公约数是1】，。

提示，使用欧拉函数计算公式可以直接得到，也可以通过扩展第三部分中的结论4的方法来证明。

2、如果gcd(m,n)=d，那么。

提示，可以使用欧拉函数计算公式推演得到。

3、n>2时，都是偶数。

提示，可以通过欧拉函数计算公司很容易得到。但是，还可以通过另外一个思路，发现与n互质的数总是成对出现。

4、当n>1时，

提示，如果3的证明你找到了另一个思路，4这个问题就迎刃而解了。

好了，欧拉函数及其相关性质并不是多复杂的数学问题，而是初等数论的基础知识。但是其证明过程中有着很美妙的逻辑，让人感觉原来纷繁复杂的、似乎没有任何规律的互质、同余等问题原来有着更深刻的内在的规律。当你体验到这种规律和其得出的结论时，你就能从一个很小的角度体会到数学与逻辑之美。

所以我一直认为，欣赏数学之美和欣赏艺术之美在本质上是类似的！