前情回顧：

今天就把上篇文章結(jié)尾的填坑上吧。

01

什么是歐拉函數(shù)

在上一篇文章結(jié)尾，我們留了這么一個小懸念：

其中，這種 “不大于 n 且與 n 互素的數(shù)的個數(shù)” 在數(shù)論中有一個專用的名字，叫 歐拉函數(shù)，記作 φ(n) 。

同時，歐拉還告訴我們：

其中 p?取到?n?的所有質(zhì)因數(shù)。

想證明的需要分四種情況討論：

情況一：當 n = 1 時，?φ(1)=1?，因為 1 與自身互素。

情況二：當 n 為素數(shù)時，?φ(n)=n?1?，因為?1,2,3,?,n?1?都不被 n 整除，所以這些數(shù)都與 n 互素。

情況三：如果 p 為素數(shù)，n 是 p 的正整數(shù)次方，那么：

證明如下：

情況四：當?n?是任意正整數(shù)時：

有：

其中，這一步叫做?歐拉函數(shù)的積性：

“積性”指的是對于互素的 m, n，函數(shù) f(x) 滿足：

證明如下：

構(gòu)造 n×m?的一個數(shù)陣：

02

證明歐拉定理

所謂的 歐拉定理，就是：

證明了這個定理，只需令 a = 10，n = c，上一篇文章中留下的問題也就迎刃而解了。

不過想證明這個定理，我們首先要介紹數(shù)論中的幾個基本概念：

1.?同余：

參考資料：

[1]初等數(shù)論筆記Part 1： 歐拉定理 - 知乎 (zhihu.com)

[2]歐拉函數(shù)的計算式 - 知乎 (zhihu.com)

[3]如何求歐拉函數(shù)~轉(zhuǎn)載_歐拉函數(shù)值怎么計算的_飛機飛過天空的博客-CSDN博客