素数的有关性质（二）欧拉函数的一些定理证明与计算

文章目录​​写在前面​​​​内容回顾​​​​模剩余类环​​​​定理​​​​模剩余类域​​​​定义​​​​欧拉函数的定义​​​​欧拉函数的性质​​​​命题1：欧拉函数等于与互素整数个数​​​​命题2：取值为素数的欧拉函数等于​​​证明​​​​定理2：取值为素数方幂的欧拉函数​​​​证 明​​​定理3：取值为可分解成互素整数乘积的欧拉函数​​​证 明​​​​证明思路​​​​会用到的一些结论​​​​具体步骤​​​​定理4：取值为任意大于1整数的欧拉函数​​​​欧拉函数的计算​​​​总结​​写在前面

这回总结欧拉函数的一些有关定理，涉及到的以前的知识比较多，具体内容参见丘维声教授的《数学的思维方式与创新》一书。

内容回顾

介绍后面定理证明中可能会用到的一些定义与定理，在教材中均有相关的证明，在此不做详述。

模 m m m剩余类环定理在模剩余类环中，是可逆元当且仅当。的每一个元素或者是可逆元，或者是零因子，二者必居其一，且只居其一。模 p p p剩余类域定义设是一个有单位元的交换环，若中每一个非零元都是可逆元，那么称是一个域。设是一个素数，则是一个域，称其为模剩余类域。欧拉函数的定义

把中所有可逆元组成的集合记作，把中可逆元的个数记作，称为欧拉函数，即。

欧拉函数的性质

下面的这些命题与定理，都可以从具体的例子中归纳总结出来，本文仅介绍定理的证明部分。

命题1：欧拉函数等于与 m m m互素整数个数

等于集合中与互素的整数的个数。

命题2：取值为素数 p p p的欧拉函数等于 p − 1 p-1 p−1

若是素数，则.

证明

若是素数，则是一个域，从而

于是.

定理2：取值为素数方幂的欧拉函数

设是素数，则对于任一正整数，有

证 明

由于互素的整数个数不易计算，下面从不互素的整数出发进行证明。

设集合，其中与不互素的整数的个数即所求。对，利用互素整数的性质3推广，有。若，则，从而，因此

从而中与中不互素的整数的个数为，于是得到

★ \bigstar ★定理3：取值为可分解成互素整数乘积的欧拉函数

设，且与是互素的大于的整数，则

★ \bigstar ★证 明证明思路

这个定理的证明比较长，但思路很清晰，大致可总结为：

由于所要证明的等式是【中可逆元的个数等于中可逆元的个数乘以中可逆元的个数】，自然想到联系两个环(本质上是一种集合)的一种运算是将两个环对应元素进行Cartes积（笛卡尔积），定义满足一定条件，且经笛卡尔积运算后的环为直和：。由于和的结构并不清楚，于是想到从和入手进行分析。从映射的角度考虑两个环的对应关系，再研究上的映射，可以发现集合计数之间的联系。会用到的一些结论映射的一些定义及结论，可以参考《​​关于映射的一些理解与常用定理​​》.互素的一些性质，可以参考《​​与素数有关的一些性质及证明（一）​​》.具体步骤首先考虑环和的笛卡尔积：

规定：

易验证为一个交换环，且其零元为，单位元为。把这个环称为环和环的直和，记作.而
根据上面的推导，以及“分步计数原理”，可以得到：，所以我们只需证明成立，即可证明这个定理。根据上面的分析，首先建立环与环之间的联系（对应法则）。建立的元素与的元素之间的对应关系，令
验证上述的对应法则是否构成映射，即对中的任一元素，是否能从中找到唯一确定的一个元素与之对应，亦即验证

是否成立。而

因此是到的一个映射，而由于像相同推出其对应的原像相同，所以为单射。又由于，并根据结论“建立单射且元素个数相同的两有限集合，其对应法则也为满射”，可以得到映射为满射，所以为双射。下面寻找环与环的可逆元之间的关系，只需证明存在到的一个双射，即可得到。因为可逆元是由乘法运算定义的，所以首先要验证保持乘法运算，即验证成立。

于是，
①：须满足为单射且保持乘法运算;②：因为是的可逆元，而是满射（陪域等于值域），所以，从而中每个元素都可以表成的形式，又，所以。由于是的可逆元是的可逆元，将映射限制在环（集合）上，记为，于是这个新的映射是到的一个映射，且该映射是满射（陪域中每一个元素都能找到一个与之对应，即值域等于陪域），而该映射显然为单射，所以是双射，于是证明了

即
定理4：取值为任意大于1整数的欧拉函数

设，其中是两两不等的整数，则

（这个定理是定理2与定理3的推论，利用算术基本定理及数学归纳法易证。根据此定理可以很方便地计算任意大于1整数的欧拉函数。）

欧拉函数的计算

例：计算.

总结

本文是在看了丘老师的课程之后的一个课程笔记与总结，不得不说丘老师的课程真的很棒，讲的很细致，而且关于一些数学思想的讲解很自然，很推荐大家学习。未来有时间我还会总结《数学的思维方式与创新》课程的一些笔记，希望大家喜欢。