SkyWT / 博客 / 欧拉函数、费马小定理与欧拉定理略解

欧拉函数、费马小定理与欧拉定理略解

2018 年 6 月 24 日 11:49


文章目录

在数论中,对正整数 n,欧拉函数 φ(n)\varphi (n) 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名,它又称为 φ 函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。(来自维基百科)

温馨提示:
本文中有大量 KaTeX 公式,请确保浏览器支持,否则卡到超乎你想象。
Windows 可以在控制面板-程序-卸载程序-卸载\更新 Windows 组件中卸载IE浏览器。
本文中 (a,b) 或者 gcd(a,b) 表示a、b的最大公因数。

本文隶属⌈ 数论学习系列 ⌋。

欧拉函数

定义

欧拉函数 φ(n)\varphi(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。例如:φ(10)\varphi(10)=4,因为在1到10中1、3、7、9 这4个数字与 10 互质。

(注:φ(n)\varphi (n)的另一种写法是ϕ(n)\phi(n),但是我更喜欢前者……)

几个性质

这两个性质下面证明的时候要用。

当x为质数p的k次幂时

如果φ(x)\varphi(x)中的x是质数 p 的 k 次幂,那么可以用这个公式求:

φ(x)=φ(pk)=pkpk1=(p1)pk1=pk(11p)\varphi (x)=\varphi (p^k)=p^k-p^{k-1}=(p-1)p^{k-1}=p^k\cdot (1-\frac 1 p)

很好理解,除了 p 的倍数外,其他数都与 x 互质。(为什么要化成这样?因为后面我们证明 φ(x)\varphi (x) 的公式要用~)

欧拉函数是积性函数

欧拉函数是积性函数,就是说如果 x 和 y 互质,则

φ(xy)=φ(x)φ(y)=(x1)(y1)\varphi(xy)=\varphi(x) \varphi(y)=(x-1)(y-1)

(剩下的两个性质就是下面要讲的费马小定理和欧拉定理了)

计算方法(公式)

φ(x)\varphi(x)的计算公式是:

φ(x)=x(11P1)(11P2)(11Px)\varphi(x)=x(1-\frac 1 {P_1})(1-\frac 1 {P_2})\cdots(1-\frac 1 {P_x})

写得高端点:

φ(x)=xi=1n(11Pi)\varphi (x)=x\prod_{i=1}^n (1-\frac 1 {P_i})

其中PiP_i表示 xx 的第 ii 个质因子,上式条件为 x2x \geqslant 2xZx \in Z

特殊地,φ(1)=1\varphi(1)=1。因为小于等于 1 的正整数中唯一和1互质的数就是 1 本身。

举例

比如说计算 φ(10)\varphi(10):10 的质因子有 2 和 5。那么:

φ(10)=10(112)(115)=4\varphi(10)=10(1-\frac 1 2)(1-\frac 1 5)=4

与前面验证的答案一致~

公式证明

我们先把 xx 标准分解:

x=P1k1P2k2Pnknx=P_1^{k_1} \cdot P_2^{k_2} \cdots P_n^{k_n}

其中 PiP_i 表示 xx 的第 ii 个质因子,kik_i 则表示x中含有质因子 PiP_i 的数量。接下来根据“欧拉函数是积性函数”这一性质可以得出:

φ(x)=φ(P1k1)φ(P2k2)φ(Pnkn)\varphi(x)=\varphi(P_1^{k_1})\cdot \varphi(P_2^{k_2})\cdots \varphi(P_n^{k_n})

又根据前面推出的 φ(pk)=pk(11p)\varphi (p^k)=p^k\cdot (1-\frac 1 p),得到:

φ(x)=x(11P1)(11P2)(11Px)=xi=1n(11Pi)\varphi(x) = x(1-\frac 1 {P_1})(1-\frac 1 {P_2})\cdots(1-\frac 1 {P_x}) = x\prod_{i=1}^n (1-\frac 1 {P_i})

就得到了刚刚的等式!!!

费马小定理

费马小定理(Fermat's Little Theorem)是数论中的一个重要定理,在1636年由费马提出。基本内容是:如果 p 是质数并且 (a,p)=1(a,p)=1,则有:

ap11(modp)a^{p-1}\equiv 1 \pmod p

举个例子,对于质数 p=3,a=8,那么:

831641(mod3)8^{3-1}\equiv 64\equiv 1 \pmod 3

完全剩余系

为了方便证明,先要普及下完全剩余系的概念:

完全剩余系(简称完系),即是通过对一系列正整数模 m 后产生的从 0 至(m-1)的完全数系。通常地,完全剩余系在研究数论时很有用。

举个例子:{0, 1, 2, 3} 就是模 4 的完系。

知道了完全剩余系,我们就可以方便地开始证明了……

证明

证明其实并不难。

假设 {1,2,,p1,p}\lbrace 1,2,\dots,p-1,p \rbrace 是模 pp 的完全剩余系,那么显然,{a1,a2,,ap}\displaystyle \lbrace a-1,a-2,\dots,a-p \rbrace 也是模 pp 的完全剩余系。得到:

(a1)(a2)(a(p1))12(p1)(modp)(a-1)(a-2)\cdots(a-(p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod p

等价于:

ap1(p1)!(p1)!(modp)a^{p-1}\cdot (p-1)! \equiv (p-1)! \pmod p

((p1)!,p)=1((p-1)!,p)=1,所以

ap11(modp)a^{p-1} \equiv 1 \pmod p

欧拉定理

欧拉定理(Euler's Theorem)可以看作费马小定理的一般情况,即如果 (a,n)=1(a,n)=1 ,则 a,na,n 满足:

aφ(n)1(modn)a^{\varphi (n)}\equiv 1 \pmod n

举例:n=6,a=5n=6,a=5φ(6)=2\varphi(6)=2

52251(mod6)5^2 \equiv 25 \equiv 1 \pmod 6

显然当 nn 是质数的时候 φ(n)=n1\varphi(n)=n-1 ,就成了费马小定理了……

减缩剩余系

在证明之前又要普及一下减缩剩余系的概念了……

简缩剩余系(也叫简化剩余系,简称减系或者缩系):在每个剩余类选取至 1 个与 m 互素代表元构成简缩剩余系。举个例子:

10 的完系是:{0,1,2,3,4,5,6,7,8,9};
则 {1,2,5,6} 是 10 的一个减系。也就是说从完系里选几个数。要注意不一定是从这个固定的完系里选,例如 {10,14,15} 也是 10 的一个减系。

证明

这个定理证明和费马小定理类似:

假设 {x1,x2,,xφ(n)}\lbrace x_1,x_2,\dots,x_{\varphi (n)} \rbrace 是模 pp 的减缩剩余系,那么:
xi≢xj(modn)x_i \not ≡ x_j \pmod n
(a,n)=1(a,n)=1,所以
axi≢axj(modn)ax_i \not ≡ ax_j \pmod n
所以 {ax1,ax2,,axφ(n)}\displaystyle \lbrace ax_1,ax_2,\dots,ax_{\varphi (n)} \rbrace 也是模 pp 的减缩剩余系。所以:

(ax1)(ax2)(axφ(n))x1x2xφ(n)(modn)(ax_1)(ax_2)\cdots(ax_{\varphi (n)}) \equiv x_1 \cdot x_2 \cdots x_{\varphi (n)} \pmod n
上式等价于:
aφ(n)(x1x2xφ(n))x1x2xφ(n)(modn)a^{\varphi(n)}(x_1 \cdot x_2 \cdots x_{\varphi (n)}) \equiv x_1 \cdot x_2 \cdots x_{\varphi (n)} \pmod n
即:
aφ(n)1(modn)a^{\varphi(n)} \equiv 1 \pmod n


参考

欧拉函数 - 维基百科,自由的百科全书
费马小定理 - 维基百科,自由的百科全书
完全剩余系 - 维基百科,自由的百科全书
欧拉定理 (数论) - 维基百科,自由的百科全书
费马小定理_百度百科
欧拉函数 - handsomecui - 博客园


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)