1271期雅礼月考（四）欧拉函数的结论

推荐新教材中的数列新定义系列，可以参看链接
《系列1——斐波那契数列与36恒等式》
《系列2——隐藏的欧拉函数（与密码学）》
《系列3——冰雹猜想（角谷猜想）》
《系列4——无限循环小数分式化》
《系列5——高次方和与高阶等差（垛积术）》
《系列6——杨辉三角常用6性质（附新教材提到的19性质原文）》
《系列7——牛顿法与牛顿迭代数列》

该篇素材选自该篇素材选自湖南省长沙市雅礼中学25届高三月考卷（四）T14。该题其实是以新教材课后习题中介绍的欧拉函数为背景的数列题，比较简单，就是欧拉函数的一个结论，并不适合放在填空压轴的位置上！另外就是，在模考中也曾出现过密码学与欧拉函数的新定义压轴，这期借此题讲一下新教材中的隐藏的欧拉函数以及总结一下模考中考过的欧拉函数问题。

• 一、这道以欧拉函数为背景的数列题
• 二、新教材中隐藏的欧拉函数
• 三、欧拉函数定义与计算
• 1、欧拉函数定义
• 2、欧拉函数的计算
• 四、模考中的欧拉函数压轴
• 五、更多模考中的欧拉函数题
• 1、原卷版（文末下载）
• 2、解析版（文末下载）

一、这道以欧拉函数为背景的数列题

【湖南长沙雅礼中学25届高三月考（四）T14】（关注微信公众号：Hi数学派）欧拉函数 表示不大于正整数 且与 互素（互素：公约数只有 ）的正整数的个数. 已知 ，其中 ，，， 是 的所有不重复的质因数（质因数：因数中的质数）. 例如 . 若数列 是首项为 ，公比为 的等比数列，则 ________ .

解析： 由题意得

当 时，

当 时，

则

注： 若 为质数，且 ，则

形成了一个等比数列.

二、新教材中隐藏的欧拉函数

在人教 版新教材选择性必修二第 页课后习题第 题中介绍了欧拉函数的定义，如下

解析： （关注微信公众号：Hi数学派）

三、欧拉函数定义与计算

1、欧拉函数定义

【欧拉函数定义】 在数论中，对正整数 ，欧拉函数 是小于或等于 的正整数中与 互质的数的数目。

注： 此函数以其首名研究者欧拉命名，它又称为 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

例如，欧拉函数部分值如下，

哪有没有统一的欧拉函数值的计算公式呢？

2、欧拉函数的计算

在介绍欧拉函数计算方法之前先介绍一下正整数的标准分解

【标准分解式】 将质因数分解的结果，按照质因数大小，由小到大排列，并将相同质因数的连乘积，以指数形式表示，此种表示法称为标准分解式。

例如， 的标准分解式是

然后就可以介绍一下欧拉函数的计算方法了

【欧拉函数的计算公式】
（1） 先化为标准分解式形式（关注微信公众号：Hi数学派）

（2） 再依照下面的公式计算

其中 是 的所有不重复的质因数。

例如，

注： 当 为合数，且不知道 的标准因数分解式时，通常很难求出 的欧拉函数值 ，但如果 为质数时，有计算式就可以得到很好的结论

Ⅰ. 若 为质数，则

Ⅱ. 若 为质数，且 ，则

形成了一个等比数列.

四、模考中的欧拉函数压轴

【浙南名校联盟25届高三一联T19】（关注微信公众号：Hi数学派）密码学是研究编制密码和破译密码的技术科学. 研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学. 20 世纪 70 年代，一些学者提出了公开密钥体制，即运用单向函数的数学原理，以实现加、脱密密钥的分离. 加密密钥是公开的，脱密密钥是保密的. 这种新的密码体制，引起了密码学界的广泛注意和探讨.
某数学课外小组研究了一种编制密码的方法：取任意的正整数 ，将小于等于 且与 互质的正整数从小到大排列，即为密码. 记符合上述条件的正整数的个数为 .
（1） 求数列 的前 项和；
（2） 求 （ ） 的表达式和 的值；
（3） 记 ，数列 的前 项和 ，证明 .

解析：

（1）

（2） 为质数，则小于等于 的正整数中，只有 的倍数不与 互质，也即小于等于 的奇数满足条件，所以

在小于等于 的正整数中， 的倍数有 个， 的倍数有 个

（3） 由 （2）  

设（关注微信公众号：Hi数学派）

则对等式右边通分可得

对比等式两边可得

解得

故

所以（关注微信公众号：Hi数学派）

注1： 小于等于 且与 互质的正整数的个数其实就是欧拉函数 的值。

注2： 不过在第 （3） 问数列求和过程中，通项公式是二次多项式与等比数列之积，这时若用错位相减法就需要连用两次才能做出来，如果利用裂项相消法则会减少很多运算量。10月模考中裂项相消法有点多，比如极光杯线上联考T18的三角函数数列裂项，25届天域全国名校协作体高三联考T19的 裂项放缩，更多裂项放缩技巧可以参考小派之前的推文《更新！67个数列裂项&放缩》

【24 届开封二模T19】（关注微信公众号：Hi数学派）在密码学领域，欧拉函数是非常重要的，其中最著名的应用就是在 加密算法中的应用．设 ， 是两个正整数，若 ， 的最大公约数是 ，则称 ， 互素 ．对于任意正整数 ，欧拉函数是不超过 且与 互素的正整数的个数，记为 ．
（1） 试求 ，，， 的值；
（2） 设 是一个正整数， ， 是两个不同的素数 ．试求 ， 与 和 的关系；
（3）   算法是一种非对称加密算法，它使用了两个不同的密钥：公钥和私钥．具体而言：
① 准备两个不同的、足够大的素数 ， ；
② 计算 ，欧拉函数 ；
③ 求正整数 ，使得 除以 的余数是 ；
④ 其中 称为公钥， 称为私钥．
已知计算机工程师在某 加密算法中公布的公钥是 ．若满足题意的正整数 从小到大排列得到一列数记为数列 ，数列 满足 ，求数列 的前 项和 ．

解析：

（1） ， ， ， （详解可以参考标答，群内分享）

（2） 在不大于 的正整数中，只有 的倍数不与 互素，而 的倍数有 个， 因此

由 ， 是两个不同的素数，得 ，

在不超过 的正整数中， 的倍数有 个， 的倍数有 个，

于是

所以

（3）  计算机工程师在某   加密算法中公布 公钥是 ，则 ， ，从而

由 （2） 得，

即正整数 满足的条件为： ， ，

，令

则 ，

令 ，则 ，

取 ，则 ， ， ，于是

因此 ，即

所以（关注微信公众号：Hi数学派）

【24 届浙江天域名校协作体高三二模T19】（关注微信公众号：Hi数学派）欧拉函数 （ ） 的函数值等于所有不超过正整数 且与 互素的正整数的个数，例如： ， ， ，数列 满足 （ ）
（1） 求 ， ，并求数列 的通项公式；
（2） 记 ，求数列 的前 和 .

答案： （1） ， ， ， （详解群内分享）

（2）（详解群内分享）

【24 届湖北高中毕业生四月模拟T19】 欧拉函数在密码学中有重要的应用. 设 为正整数，集合 ，欧拉函数 的值等于集合 中与 互质的正整数的个数；记 表示 除以 的余数（ 和 均为正整数）
（1） 求 和 ；
（2） 现有三个素数 ，，（ ）， ，存在正整数 满足 ；已知对素数 和 ，均有 ，证明：若 ，则
（3） 设 为两个未知素数的乘积，， 为另两个更大的已知素数，且 ；又 ， ， ，试用 ， 和 求出 的值.

答案： （1） ， （详解群内分享）

（2）（3） （详解群内分享）

五、更多模考中的欧拉函数题

1、原卷版（文末下载）

2、解析版（文末下载）