文章目录
在数论中,对正整数 n,欧拉函数 φ(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名,它又称为 φ 函数(由高斯所命名)或是欧拉总计函数(totient function,由西尔维斯特所命名)。(来自维基百科)
温馨提示:
本文中有大量 KaTeX 公式,请确保浏览器支持,否则卡到超乎你想象。
Windows 可以在控制面板-程序-卸载程序-卸载\更新 Windows 组件中卸载IE浏览器。
本文中 (a,b) 或者 gcd(a,b) 表示a、b的最大公因数。
本文隶属⌈ 数论学习系列 ⌋。
欧拉函数
定义
欧拉函数 φ(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。例如:φ(10)=4,因为在1到10中1、3、7、9 这4个数字与 10 互质。
(注:φ(n)的另一种写法是ϕ(n),但是我更喜欢前者……)
几个性质
这两个性质下面证明的时候要用。
当x为质数p的k次幂时
如果φ(x)中的x是质数 p 的 k 次幂,那么可以用这个公式求:
φ(x)=φ(pk)=pk−pk−1=(p−1)pk−1=pk⋅(1−p1)
很好理解,除了 p 的倍数外,其他数都与 x 互质。(为什么要化成这样?因为后面我们证明 φ(x) 的公式要用~)
欧拉函数是积性函数
欧拉函数是积性函数,就是说如果 x 和 y 互质,则
φ(xy)=φ(x)φ(y)=(x−1)(y−1)
(剩下的两个性质就是下面要讲的费马小定理和欧拉定理了)
计算方法(公式)
φ(x)的计算公式是:
φ(x)=x(1−P11)(1−P21)⋯(1−Px1)
写得高端点:
φ(x)=xi=1∏n(1−Pi1)
其中Pi表示 x 的第 i 个质因子,上式条件为 x⩾2 且 x∈Z 。
特殊地,φ(1)=1。因为小于等于 1 的正整数中唯一和1互质的数就是 1 本身。
举例
比如说计算 φ(10):10 的质因子有 2 和 5。那么:
φ(10)=10(1−21)(1−51)=4
与前面验证的答案一致~
公式证明
我们先把 x 标准分解:
x=P1k1⋅P2k2⋯Pnkn
其中 Pi 表示 x 的第 i 个质因子,ki 则表示x中含有质因子 Pi 的数量。接下来根据“欧拉函数是积性函数”这一性质可以得出:
φ(x)=φ(P1k1)⋅φ(P2k2)⋯φ(Pnkn)
又根据前面推出的 φ(pk)=pk⋅(1−p1),得到:
φ(x)=x(1−P11)(1−P21)⋯(1−Px1)=xi=1∏n(1−Pi1)
就得到了刚刚的等式!!!
费马小定理
费马小定理(Fermat's Little Theorem)是数论中的一个重要定理,在1636年由费马提出。基本内容是:如果 p 是质数并且 (a,p)=1,则有:
ap−1≡1(modp)
举个例子,对于质数 p=3,a=8,那么:
83−1≡64≡1(mod3)
完全剩余系
为了方便证明,先要普及下完全剩余系的概念:
完全剩余系(简称完系),即是通过对一系列正整数模 m 后产生的从 0 至(m-1)的完全数系。通常地,完全剩余系在研究数论时很有用。
举个例子:{0, 1, 2, 3} 就是模 4 的完系。
知道了完全剩余系,我们就可以方便地开始证明了……
证明
证明其实并不难。
假设 {1,2,…,p−1,p} 是模 p 的完全剩余系,那么显然,{a−1,a−2,…,a−p} 也是模 p 的完全剩余系。得到:
(a−1)(a−2)⋯(a−(p−1))≡1⋅2⋯(p−1)(modp)
等价于:
ap−1⋅(p−1)!≡(p−1)!(modp)
又 ((p−1)!,p)=1,所以
ap−1≡1(modp)
欧拉定理
欧拉定理(Euler's Theorem)可以看作费马小定理的一般情况,即如果 (a,n)=1 ,则 a,n 满足:
aφ(n)≡1(modn)
举例:n=6,a=5:φ(6)=2 ;
52≡25≡1(mod6)
显然当 n 是质数的时候 φ(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)} 是模 p 的减缩剩余系,那么:
xi≡xj(modn)
又 (a,n)=1,所以
axi≡axj(modn)
所以 {ax1,ax2,…,axφ(n)} 也是模 p 的减缩剩余系。所以:
(ax1)(ax2)⋯(axφ(n))≡x1⋅x2⋯xφ(n)(modn)
上式等价于:
aφ(n)(x1⋅x2⋯xφ(n))≡x1⋅x2⋯xφ(n)(modn)
即:
aφ(n)≡1(modn)
参考
欧拉函数 - 维基百科,自由的百科全书
费马小定理 - 维基百科,自由的百科全书
完全剩余系 - 维基百科,自由的百科全书
欧拉定理 (数论) - 维基百科,自由的百科全书
费马小定理_百度百科
欧拉函数 - handsomecui - 博客园