一切都要从欧拉说起：一文看懂欧拉函数和欧拉定理

前情回顾：

今天就把上篇文章结尾的填坑上吧。

01

什么是欧拉函数

在上一篇文章结尾，我们留了这么一个小悬念：

其中，这种 “不大于 n 且与 n 互素的数的个数” 在数论中有一个专用的名字，叫 欧拉函数，记作 φ(n) 。

同时，欧拉还告诉我们：

其中 p 取到 n 的所有质因数。

想证明的需要分四种情况讨论：

情况一：当 n = 1 时， φ(1)=1 ，因为 1 与自身互素。

情况二：当 n 为素数时， φ(n)=n−1 ，因为 1,2,3,⋯,n−1 都不被 n 整除，所以这些数都与 n 互素。

情况三：如果 p 为素数，n 是 p 的正整数次方，那么：

证明如下：

情况四：当 n 是任意正整数时：

有：

其中，这一步叫做 欧拉函数的积性：

“积性”指的是对于互素的 m, n，函数 f(x) 满足：

证明如下：

构造 n×m 的一个数阵：

02

证明欧拉定理

所谓的 欧拉定理，就是：

证明了这个定理，只需令 a = 10，n = c，上一篇文章中留下的问题也就迎刃而解了。

不过想证明这个定理，我们首先要介绍数论中的几个基本概念：

1. 同余：

参考资料：

[1]初等数论笔记Part 1： 欧拉定理 - 知乎 (zhihu.com)

[2]欧拉函数的计算式 - 知乎 (zhihu.com)

[3]如何求欧拉函数~转载_欧拉函数值怎么计算的_飞机飞过天空的博客-CSDN博客