做图专业软件下载网站,wordpress添加备案号,南通制作手机网站,专业的移动网站建设公注#xff1a;本文为 “欧拉函数” 相关合辑。 略作重排#xff0c;未整理去重。 如有内容异常#xff0c;请看原文。 欧拉函数最全总结
jiet07 已于 2024-10-22 10:00:54 修改
一、欧拉函数的引入
首先引入互质关系#xff1a;
如果两个正整数#xff0c;除了 111 以…注本文为 “欧拉函数” 相关合辑。 略作重排未整理去重。 如有内容异常请看原文。 欧拉函数最全总结
jiet07 已于 2024-10-22 10:00:54 修改
一、欧拉函数的引入
首先引入互质关系
如果两个正整数除了 111 以外没有其他公因子我们就称这两个数是互质关系coprime。 比如151515 和 323232 没有公因子所以它们是互质关系。这说明不是质数也可以构成互质关系。
其次引进缩系的概念
在与模数 mmm 互素的全部剩余类中各取一数所组成的集叫做模数 mmm 的一组缩系。
在讨论缩系的过程中需要引入一个常用的数论函数–欧拉函数 φ(n)\varphi(n)φ(n)。
请思考以下问题 任意给定正整数 nnn请问在小于等于 nnn 的正整数之中有多少个与 nnn 构成互质关系比如在 111 到 888 之中有多少个数与 888 构成互质关系
计算这个值的方法就叫做欧拉函数以 φ(n)\varphi(n)φ(n) 表示。在 111 到 888 之中与 888 形成互质关系的是 111、333、555、777所以 φ(8)4\varphi(8) 4φ(8)4。
二、欧拉函数的定义
定义欧拉函数 φ(n)\varphi(n)φ(n) 是一个定义在正整数集上的函数φ(n)\varphi(n)φ(n) 的值等于序列 000111222…n−1n-1n−1 中与 nnn 互素的数的个数。
此函数以其首名研究者欧拉命名 (Euler’s totient function)它又称为 Euler’s totient function、φ\varphiφ 函数、欧拉商数等。
特别的φ(1)1\varphi(1)1φ(1)1和 111 互质的数 (小于等于 111) 就是 111 本身。
函数表0~100 欧拉函数表 (x?代表十位数, x代表个位数)
φ(n)01234567890?01122426461?410412688166182?8121022820121812283?83016201624123618244?164012422024224616425?203224521840243628586?166030363248206632447?247024723640366024788?325440822464425640889?24724460467232964260
φ(100)40\varphi(100)40φ(100)40
三、欧拉函数的性质
当 p 是素数时φ(p)p−1\varphi(p)p-1φ(p)p−1。欧拉函数是积性函数但不是完全积性函数。 当且仅当 n 可以分解成两个互质的整数之积即 np1×p2n p_1 \times p_2np1×p2其中 (p1,p2)1(p_1,p_2)1(p1,p2)1则 φ(n)φ(p1p2)φ(p1)φ(p2)\varphi(n) \varphi(p_1p_2) \varphi(p_1)\varphi(p_2)φ(n)φ(p1p2)φ(p1)φ(p2)。 特别的对于两个素数 p, qφ(pq)(p−1)(q−1)\varphi(pq)(p-1)(q-1)φ(pq)(p−1)(q−1)RSA 算法应用核心性质。当 n2n2n2 时φ(n)\varphi(n)φ(n) 都是偶数也即 φ(n)≡0(mod2)\varphi(n) \equiv 0 \pmod{2}φ(n)≡0(mod2)。 简单证明若 n 是质数 p 的 k 次幂即 npknp^knpk则 φ(n)pk−pk−1(p−1)pk−1\varphi(n)p^k - p^{k-1}(p-1)p^{k-1}φ(n)pk−pk−1(p−1)pk−1。 当 p2 时pk−1p^{k-1}pk−1 必为偶数k≥2 时2k−12^{k-1}2k−1 是偶数当 p2 时(p-1) 必为偶数奇素数减 1 为偶数。 因此无论 p 是 2 还是大于 2 的素数φ(n)\varphi(n)φ(n) 均为偶数。
四、欧拉函数的计算方法
一素数分解法 对于一个正整数 N 的素数幂分解 NP1q1P2q2…PnqnNP_1^{q_1}P_2^{q_2}\dots P_n^{q_n}NP1q1P2q2…Pnqn其中 PiP_iPi 为素数1≤i≤n1 \leq i \leq n1≤i≤n根据欧拉函数的积性性质可得 φ(N)φ(P1q1)φ(P2q2)…φ(Pnqn)\varphi(N)\varphi(P_1^{q_1})\varphi(P_2^{q_2})\dots\varphi(P_n^{q_n})φ(N)φ(P1q1)φ(P2q2)…φ(Pnqn) 注意每种质因数只保留一个即素数幂分解中每个素数的最高次幂。 若 n 是质数 p 的 k 次幂npknp^knpk则 φ(n)pk−pk−1(p−1)pk−1\varphi(n)p^k - p^{k-1}(p-1)p^{k-1}φ(n)pk−pk−1(p−1)pk−1。 原理除了 p 的倍数外其他数都与 n 互质。 简单证明 由 φ(n) 的定义φ(pk)\varphi(p^k)φ(pk) 等于从 pkp^kpk 中减去 1 到 pkp^kpk 中与 p 不互素的数的个数。 因为 p 是素数1 到 pkp^kpk 中与 p 不互素的数就是 p 的倍数共有 pk−1p^{k-1}pk−1 个即 p,2p,…,pk−1pp,2p,\dots,p^{k-1}pp,2p,…,pk−1p。 因此 φ(pk)pk−pk−1(p−1)pk−1\varphi(p^k)p^k - p^{k-1}(p-1)p^{k-1}φ(pk)pk−pk−1(p−1)pk−1证完。
二编程思维
利用欧拉函数和它本身不同质因数的关系用筛法计算出某个范围内所有数的欧拉函数值。
核心公式欧拉函数与质因数的关系为 φ(N)N×∏p∣N(1−1p)\varphi(N)N \times \prod_{p|N} \left(1-\frac{1}{p}\right)φ(N)N×p∣N∏(1−p1) 其中 p∣Np|Np∣N 表示 p 是 N 的质因数即 p 能整除 N。
示例
φ(10)10×(1−12)×(1−15)4\varphi(10)10 \times \left(1-\frac{1}{2}\right) \times \left(1-\frac{1}{5}\right)4φ(10)10×(1−21)×(1−51)410 的质因数为 2,5φ(30)30×(1−12)×(1−13)×(1−15)8\varphi(30)30 \times \left(1-\frac{1}{2}\right) \times \left(1-\frac{1}{3}\right) \times \left(1-\frac{1}{5}\right)8φ(30)30×(1−21)×(1−31)×(1−51)830 的质因数为 2,3,5φ(49)49×(1−17)42\varphi(49)49 \times \left(1-\frac{1}{7}\right)42φ(49)49×(1−71)4249 的质因数为 7。
1. 求 n 以内的所有素数
#l[]
def prime(n):#global l[] # 全局变量错误写法声明与赋值不能同时进行global ll []for x in range(n):# 判断如果 x 是素数则加入列表否则跳过if x 2:continuefor i in range(2, x):if x % i 0:breakelse:l.append(x)print(l)prime(100)输出结果
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]2. 求 φ(n)
def phi(n):ans nfor i in l:if n % i 0:ans ans * (1 - 1/i) # 等价于核心公式将 n 代入计算return int(ans)phi(100)# 可通过循环输出 1-9 的欧拉函数值
# for i in range(1, 10):
# print(phi(i))输出结果
403. 格式化输出 0-100 欧拉函数表“x?”代表十位数“x”代表个位数
步骤一输出表头和表格横向数值
print({:40}.format(0~100 欧拉函数表“x?”代表十位数“x”代表个位数))
print()
print({:6}.format(φ(n)), end)
for x in range(0, 10):print({:6}.format(x), end)输出结果 0~100 欧拉函数表“x?”代表十位数“x”代表个位数φ(n) 0 1 2 3 4 5 6 7 8 9步骤二输出表格横向和纵向数值
print({:40}.format(0~100 欧拉函数表“x?”代表十位数“x”代表个位数))
print()
print({:6}.format(φ(n)), end)
for x in range(0, 10):print({:6}.format(x), end)for x in range(0, 10):print(\n)print({:6}.format(str(x) ?), end)输出结果 0~100 欧拉函数表“x?”代表十位数“x”代表个位数φ(n) 0 1 2 3 4 5 6 7 8 90?1?2?3?4?5?6?7?8?9?步骤三输出最终效果
import termcolor
# titletermcolor.colored(0~100 欧拉函数表“x?”代表十位数“x”代表个位数,white,on_red,[bold])
title termcolor.colored(0~100 欧拉函数表“x?”代表十位数“x”代表个位数, colorNone, on_colorNone, attrs[bold]) # 加粗
print({0:^70}.format(title))
print()
print({:7}.format(φ(n)), end)
for x in range(0, 10):print({:7}.format(x), end)for x in range(0, 10):a x * 10print(\n)print({:8}.format(str(x) ?), end)for y in range(0 a, 10 a):print({0:7}.format(phi(y)), end)print()
print()
# print(φ(100), phi(100))
print({:40}{:}.format(φ(100), phi(100)))输出结果 0~100 欧拉函数表“x?”代表十位数“x”代表个位数φ(n) 0 1 2 3 4 5 6 7 8 90? 0 1 1 2 2 4 2 6 4 61? 4 10 4 12 6 8 8 16 6 182? 8 12 10 22 8 20 12 18 12 283? 8 30 16 20 16 24 12 36 18 244? 16 40 12 42 20 24 22 46 16 425? 20 32 24 52 18 40 24 36 28 586? 16 60 30 36 32 48 20 66 32 447? 24 70 24 72 36 40 36 60 24 788? 32 54 40 82 24 64 42 56 40 889? 24 72 44 60 46 72 32 96 42 60φ(100)40五、欧拉函数相关定理以及证明
定理 1缩系与欧拉函数的关系
模数 m 的一组缩系含有 φ(m) 个数。
根据缩系定义缩系是从与 m 互素的剩余类中各取一个数组成的集合而与 m 互素的剩余类个数恰好为 φ(m)故定理成立。
定理 2缩系的充要条件
若 a1a2…aφ(m)a_1a_2\dotsa_{\varphi(m)}a1a2…aφ(m) 是 φ(m) 个与 m 互素的整数则 a1a2…aφ(m)a_1a_2\dotsa_{\varphi(m)}a1a2…aφ(m) 是模数 m 的一组缩系的充要条件是它们两两对模数 m 不同余。 定理 1 和定理 2根据缩系和欧拉函数的定义显然成立。 定理 3缩系拓展
若 (a,m)1(a,m)1(a,m)1x 通过模数 m 的缩系则 ax 也通过模数 m 的缩系。
证明
当 x 通过模数 m 的缩系时ax 共生成 φ(m) 个整数。由于 (a,m)1(a,m)1(a,m)1 且 (x,m)1(x,m)1(x,m)1根据互素性质可知 (ax,m)1(ax,m)1(ax,m)1即 ax 与 m 互素。假设 ax1≡ax2(modm)ax_1 \equiv ax_2 \pmod{m}ax1≡ax2(modm)两边同时乘以 a 的逆元因 (a,m)1a 的逆元存在可得 x1≡x2(modm)x_1 \equiv x_2 \pmod{m}x1≡x2(modm)。但 x 是通过缩系的元素两两不同余故假设不成立即 ax 两两不同余。
综上axaxax 通过模数 mmm 的缩系证完。
特别说明 根据定理“整数 a,b 对模数 m 同余的充分必要条件是 m|(a-b)”可得 ax1≡ax2(modm)ax_1 \equiv ax_2 \pmod{m}ax1≡ax2(modm) 的充分必要条件是 m∣a(x1−x2)m|a(x_1 - x_2)m∣a(x1−x2)。 又因 (a,m)1(a,m)1(a,m)1故 m 必整除 (x1−x2)(x_1 - x_2)(x1−x2)即 x1≡x2(modm)x_1 \equiv x_2 \pmod{m}x1≡x2(modm)进一步验证结论成立。
1. 简单证明(a,m)1(a,m)1(a,m)1(x,m)1(x,m)1(x,m)1故 (ax,m)1(ax,m)1(ax,m)1
① 当 m0 时a±1因 (a,0)1 等价于 a±1结论成立 ② 当 a0 时m±1因 (0,m)1 等价于 m±1结论成立 ③ 当 am≠0 时由最大公约数性质(a,m)(a(x,m),m)((ax,am),m)(ax,m(a,1))(ax,m)(a,m)(a(x,m),m)((ax,am),m)(ax,m(a,1))(ax,m)(a,m)(a(x,m),m)((ax,am),m)(ax,m(a,1))(ax,m)。 因 (a,m)1(a,m)1(a,m)1 且 (x,m)1(x,m)1(x,m)1故 (ax,m)1(ax,m)1(ax,m)1结论成立。
证完。
定理 4欧拉定理
设 m1m 1m1(a,m)1(a, m) 1(a,m)1则 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}aφ(m)≡1(modm)。
证明
设 r1,r2,…,rφ(m)r_1, r_2, \dots, r_{\varphi(m)}r1,r2,…,rφ(m) 是模数 mmm 的一组缩系由定理 3 可知ar1,ar2,…,arφ(m)ar_1, ar_2, \dots, ar_{\varphi(m)}ar1,ar2,…,arφ(m) 也是模数 mmm 的一组缩系。两组缩系中元素对模 mmm 同余仅顺序不同故它们的乘积对模 mmm 同余 (ar1)(ar2)…(arφ(m))≡r1r2…rφ(m)(modm)(ar_1)(ar_2)\dots(ar_{\varphi(m)}) \equiv r_1 r_2 \dots r_{\varphi(m)} \pmod{m} (ar1)(ar2)…(arφ(m))≡r1r2…rφ(m)(modm)左边整理得 aφ(m)×(r1r2…rφ(m))a^{\varphi(m)} \times (r_1 r_2 \dots r_{\varphi(m)})aφ(m)×(r1r2…rφ(m))因此 aφ(m)×(r1r2…rφ(m))≡r1r2…rφ(m)(modm)①a^{\varphi(m)} \times (r_1 r_2 \dots r_{\varphi(m)}) \equiv r_1 r_2 \dots r_{\varphi(m)} \pmod{m} \quad ① aφ(m)×(r1r2…rφ(m))≡r1r2…rφ(m)(modm)①由于每个 rir_iri 与 mmm 互素缩系定义故 r1r2…rφ(m)r_1 r_2 \dots r_{\varphi(m)}r1r2…rφ(m) 与 mmm 互素即 (r1r2…rφ(m),m)1(r_1 r_2 \dots r_{\varphi(m)}, m) 1(r1r2…rφ(m),m)1 ②。根据定理“若 ac≡bc(modm)ac \equiv bc \pmod{m}ac≡bc(modm)且 (m,c)d(m, c) d(m,c)d则 a≡b(modm/d)a \equiv b \pmod{m/d}a≡b(modm/d)”结合 ② 中 d1d 1d1由 ① 可得 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m} aφ(m)≡1(modm)
证完。
1. 辅助定理若 ac≡bc(modm)ac \equiv bc \pmod{m}ac≡bc(modm)且 (m,c)d(m,c)d(m,c)d则 a≡b(modm/d)a \equiv b \pmod{m/d}a≡b(modm/d)
简单证明 由 ac≡bc(modm)ac \equiv bc \pmod{m}ac≡bc(modm) 得 m∣c(a−b)m|c(a - b)m∣c(a−b)即 md∣cd(a−b)\frac{m}{d}|\frac{c}{d}(a - b)dm∣dc(a−b)。 因 (m/d,c/d)1(m/d, c/d)1(m/d,c/d)1d 是 m 和 c 的最大公约数故 md∣(a−b)\frac{m}{d}|(a - b)dm∣(a−b)即 a≡b(modm/d)a \equiv b \pmod{m/d}a≡b(modm/d)。
证完。
定理 5费马小定理
若 p 是素数则对于每个整数 a有 ap≡a(modp)a^p \equiv a \pmod{p}ap≡a(modp)。 由定理 4欧拉定理立刻推得定理 5它通常叫做费马小定理。 简单证明 分两种情况讨论 ① 若 a 不是 p 的倍数因 p 是素数故 (a,p)1(a,p)1(a,p)1。由欧拉定理φ(p)p−1\varphi(p)p-1φ(p)p−1故 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)。两边乘以 a 得 ap≡a(modp)a^p \equiv a \pmod{p}ap≡a(modp)。 ② 若 a 是 p 的倍数则 a≡0(modp)a \equiv 0 \pmod{p}a≡0(modp)故 ap≡0(modp)a^p \equiv 0 \pmod{p}ap≡0(modp)即 ap≡a(modp)a^p \equiv a \pmod{p}ap≡a(modp)。
综上定理成立证完。
定理 6缩系组合性质
设 m10m_10m10m20m_20m20(m1,m2)1(m_1,m_2)1(m1,m2)1x1,x2x_1,x_2x1,x2 分别通过模数 m1,m2m_1,m_2m1,m2 的缩系则 m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 通过模数 m1m2m_1m_2m1m2 的缩系。
证明
第一步证明 m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 与 m1m2m_1m_2m1m2 互素
假设 (m2x1m1x2,m1m2)1(m_2x_1 m_1x_2, m_1m_2)1(m2x1m1x2,m1m2)1则存在素数 p 整除 m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 和 m1m2m_1m_2m1m2。
若 p|m_1则 p|m_2x_1因 m2x1m1x2≡0(modp)m_2x_1 m_1x_2 \equiv 0 \pmod{p}m2x1m1x2≡0(modp)。又 p 是素数且 (m1,m2)1(m_1,m_2)1(m1,m2)1故 p∤m_2因此 p|x_1。但 x1x_1x1 是 m1m_1m1 缩系元素(x1,m1)1(x_1,m_1)1(x1,m1)1故 p∤x_1矛盾。若 p|m_2同理可推出 p|x_2与 (x2,m2)1(x_2,m_2)1(x2,m2)1 矛盾。
因此假设不成立即 (m2x1m1x2,m1m2)1(m_2x_1 m_1x_2, m_1m_2)1(m2x1m1x2,m1m2)1。
第二步证明所有 m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 对模 m1m2m_1m_2m1m2 两两不同余
假设 m2x1′m1x2′≡m2x1′′m1x2′′(modm1m2)m_2x_1 m_1x_2 \equiv m_2x_1 m_1x_2 \pmod{m_1m_2}m2x1′m1x2′≡m2x1′′m1x2′′(modm1m2)则 m2(x1′−x1′′)≡m1(x2′′−x2′)(modm1)m_2(x_1 - x_1) \equiv m_1(x_2 - x_2) \pmod{m_1}m2(x1′−x1′′)≡m1(x2′′−x2′)(modm1)。
左边 m2(x1′−x1′′)≡0(modm1)m_2(x_1 - x_1) \equiv 0 \pmod{m_1}m2(x1′−x1′′)≡0(modm1)因 (m1,m2)1(m_1,m_2)1(m1,m2)1故 m1∣m2(x1′−x1′′)m_1|m_2(x_1 - x_1)m1∣m2(x1′−x1′′)即 m1∣(x1′−x1′′)m_1|(x_1 - x_1)m1∣(x1′−x1′′)故 x1′≡x1′′(modm1)x_1 \equiv x_1 \pmod{m_1}x1′≡x1′′(modm1)。
因 x1′、x1′′x_1、x_1x1′、x1′′ 是 m1m_1m1 缩系元素两两不同余故 x1′x1′′x_1 x_1x1′x1′′。同理可得 x2′x2′′x_2 x_2x2′x2′′因此 m2x1′m1x2′m2x1′′m1x2′′m_2x_1 m_1x_2 m_2x_1 m_1x_2m2x1′m1x2′m2x1′′m1x2′′。
第三步证明所有与 m1m2m_1m_2m1m2 互素的数均可表示为 m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 的形式
由完全剩余系定理“设 m10m_10m10m20m_20m20(m1,m2)1(m_1,m_2)1(m1,m2)1x1,x2x_1,x_2x1,x2 分别通过 m1,m2m_1,m_2m1,m2 的完全剩余系则 m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 通过 m1m2m_1m_2m1m2 的完全剩余系”可知任意与 m1m2m_1m_2m1m2 互素的数 a 可表示为 a≡m2x1m1x2(modm1m2)a \equiv m_2x_1 m_1x_2 \pmod{m_1m_2}a≡m2x1m1x2(modm1m2)。
若 (x1,m1)1(x_1,m_1)1(x1,m1)1则存在素数 q 整除 x1x_1x1 和 m1m_1m1进而 q 整除 a与 (a,m1m2)1(a,m_1m_2)1(a,m1m2)1 矛盾故 (x1,m1)1(x_1,m_1)1(x1,m1)1。同理 (x2,m2)1(x_2,m_2)1(x2,m2)1。
综上m2x1m1x2m_2x_1 m_1x_2m2x1m1x2 通过模数 m1m2m_1m_2m1m2 的缩系证完。
由定理 6立得推论 推论若 (m1,m2)1(m_1,m_2)1(m1,m2)1则 φ(m1m2)φ(m1)φ(m2)\varphi(m_1m_2)\varphi(m_1)\varphi(m_2)φ(m1m2)φ(m1)φ(m2)。
定理 7欧拉函数的一般计算方法
对于一个正整数 n 的素数幂分解 nP1q1P2q2…PkqknP_1^{q_1}P_2^{q_2}\dots P_k^{q_k}nP1q1P2q2…Pkqk其中 PiP_iPi 为素数1≤i≤k1 \leq i \leq k1≤i≤k则 φ(n)n×(1−1P1)×(1−1P2)×⋯×(1−1Pk)\varphi(n)n \times \left(1-\frac{1}{P_1}\right) \times \left(1-\frac{1}{P_2}\right) \times \dots \times \left(1-\frac{1}{P_k}\right)φ(n)n×(1−P11)×(1−P21)×⋯×(1−Pk1) 证明过程参考 四、一素数分解法 以及 定理 6 的推论积性函数性质。 补充证明由定理 6 推论欧拉函数是积性函数故 φ(n)∏i1kφ(Piqi)\varphi(n)\prod_{i1}^k \varphi(P_i^{q_i})φ(n)∏i1kφ(Piqi)。结合素数幂的欧拉函数公式 φ(Piqi)Piqi−Piqi−1Piqi×(1−1Pi)\varphi(P_i^{q_i})P_i^{q_i} - P_i^{q_i-1}P_i^{q_i} \times \left(1-\frac{1}{P_i}\right)φ(Piqi)Piqi−Piqi−1Piqi×(1−Pi1)代入得 φ(n)∏i1kPiqi×(1−1Pi)n×∏i1k(1−1Pi)\varphi(n)\prod_{i1}^k P_i^{q_i} \times \left(1-\frac{1}{P_i}\right)n \times \prod_{i1}^k \left(1-\frac{1}{P_i}\right)φ(n)∏i1kPiqi×(1−Pi1)n×∏i1k(1−Pi1)证完。
六、欧拉函数的应用
一应用一证明相关题目
题目设 n≥1n≥1n≥1则有 ∑d∣n,d0φ(d)n\sum_{d|n, d0} \varphi(d) n∑d∣n,d0φ(d)n即 n 的所有正约数的欧拉函数值之和等于 n。
证明
对 n 进行素数幂分解nP1q1P2q2…PkqknP_1^{q_1}P_2^{q_2}\dots P_k^{q_k}nP1q1P2q2…PkqkPiP_iPi 为素数qi≥1q_i≥1qi≥1。n 的所有正约数 d 可表示为 dP1x1P2x2…PkxkdP_1^{x_1}P_2^{x_2}\dots P_k^{x_k}dP1x1P2x2…Pkxk其中 0≤xi≤qi0 \leq x_i \leq q_i0≤xi≤qi1≤i≤k1 \leq i \leq k1≤i≤k。由欧拉函数的积性定理 6 推论φ(d)φ(P1x1)φ(P2x2)…φ(Pkxk)\varphi(d)\varphi(P_1^{x_1})\varphi(P_2^{x_2})\dots\varphi(P_k^{x_k})φ(d)φ(P1x1)φ(P2x2)…φ(Pkxk)因此 ∑d∣nφ(d)∑x10q1∑x20q2⋯∑xk0qk[φ(P1x1)φ(P2x2)…φ(Pkxk)]\sum_{d|n} \varphi(d) \sum_{x_10}^{q_1} \sum_{x_20}^{q_2} \dots \sum_{x_k0}^{q_k} \left[ \varphi(P_1^{x_1})\varphi(P_2^{x_2})\dots\varphi(P_k^{x_k}) \right]d∣n∑φ(d)x10∑q1x20∑q2⋯xk0∑qk[φ(P1x1)φ(P2x2)…φ(Pkxk)]上述多重和可拆分为单重和的乘积乘法分配律 ∑d∣nφ(d)[∑x10q1φ(P1x1)]×[∑x20q2φ(P2x2)]×⋯×[∑xk0qkφ(Pkxk)]\sum_{d|n} \varphi(d) \left[ \sum_{x_10}^{q_1} \varphi(P_1^{x_1}) \right] \times \left[ \sum_{x_20}^{q_2} \varphi(P_2^{x_2}) \right] \times \dots \times \left[ \sum_{x_k0}^{q_k} \varphi(P_k^{x_k}) \right]d∣n∑φ(d)[x10∑q1φ(P1x1)]×[x20∑q2φ(P2x2)]×⋯×[xk0∑qkφ(Pkxk)]计算单个素数幂的欧拉函数和 当 xi0x_i0xi0 时Pi01P_i^01Pi01φ(1)1\varphi(1)1φ(1)1当 xi≥1x_i≥1xi≥1 时φ(Pixi)Pixi−Pixi−1\varphi(P_i^{x_i})P_i^{x_i} - P_i^{x_i-1}φ(Pixi)Pixi−Pixi−1素数幂欧拉函数公式。 因此 ∑xi0qiφ(Pixi)1(Pi−1)(Pi2−Pi)⋯(Piqi−Piqi−1)\sum_{x_i0}^{q_i} \varphi(P_i^{x_i}) 1 (P_i - 1) (P_i^2 - P_i) \dots (P_i^{q_i} - P_i^{q_i-1})xi0∑qiφ(Pixi)1(Pi−1)(Pi2−Pi)⋯(Piqi−Piqi−1) 展开后中间项抵消得 ∑xi0qiφ(Pixi)Piqi\sum_{x_i0}^{q_i} \varphi(P_i^{x_i}) P_i^{q_i}∑xi0qiφ(Pixi)Piqi。 代入步骤 4 的乘积式得 ∑d∣nφ(d)P1q1×P2q2×⋯×Pkqkn\sum_{d|n} \varphi(d) P_1^{q_1} \times P_2^{q_2} \times \dots \times P_k^{q_k} nd∣n∑φ(d)P1q1×P2q2×⋯×Pkqkn
证完。
二应用二求原根个数以及全部原根
1. 原根个数
若模 m 有原根则原根共有 φ(φ(m))\varphi(\varphi(m))φ(φ(m)) 个。
原理原根的定义是“使得 gφ(m)≡1(modm)g^{\varphi(m)} \equiv 1 \pmod{m}gφ(m)≡1(modm) 且最小正整数 kφ(m) 的 g”所有原根可表示为 gkg^kgk其中 (k,φ(m))1(k,φ(m))1(k,φ(m))1这样的 k 共有 φ(φ(m)) 个故原根个数为 φ(φ(m))。
2. 全部原根
特别地若 mp 为素数则模 p 共有 φ(p−1)\varphi(p-1)φ(p−1) 个原根并且若 g 为模 p 的一个原根则模 p 的全部原根为 {gk∣1≤k≤p−1,(k,p−1)1}\{g^k \mid 1 \leq k \leq p-1, (k, p-1)1\}{gk∣1≤k≤p−1,(k,p−1)1}。
因 p 是素数φ§p-1故原根个数为 φ(φ§)φ(p-1)且原根形式由原根定义推导可得。
三应用三RSA 算法
RSA 算法是一种非对称加密算法其安全性基于“大整数分解困难”的数学问题核心依赖欧拉函数的性质尤其是 φ(pq)(p−1)(q−1)\varphi(pq)(p-1)(q-1)φ(pq)(p−1)(q−1)其中 p,q 为素数。
RSA 算法的具体描述如下
密钥生成 任意选取两个不同的大素数 p 和 q计算乘积 npqnpqnpq以及欧拉函数 φ(n)(p−1)(q−1)\varphi(n)(p-1)(q-1)φ(n)(p−1)(q−1)选取一个大整数 e加密密钥满足 gcd(e,φ(n))1\gcd(e, \varphi(n))1gcd(e,φ(n))1e 需与 φ(n) 互素例如选取大于 p 和 q 的素数计算解密密钥 d满足 de≡1(modφ(n))de \equiv 1 \pmod{\varphi(n)}de≡1(modφ(n))即 dekφ(n)1de k\varphi(n) 1dekφ(n)1k≥1 为整数。 密钥发布公开整数 n 和 e公钥秘密保存 d私钥。加密过程将明文 mmn且 m 为整数加密为密文 c加密算法为 cE(m)me(modn)c E(m) m^e \pmod{n}cE(m)me(modn)解密过程将密文 c 解密为明文 m解密算法为 mD(c)cd(modn)m D(c) c^d \pmod{n}mD(c)cd(modn)
安全性说明仅通过公钥 n 和 e 无法直接计算私钥 d因为计算 d 需要 φ(n)而 φ(n) 的计算依赖 p 和 q 的分解——对于大整数 n如 1024 位以上目前尚无高效算法可分解其素因数因此 RSA 算法具有较高安全性。
七、测试
一termcolor 库的使用
termcolor 是 Python 中用于终端输出彩色文本的库支持文本颜色、背景色和文本属性如加粗、闪烁的设置。
1. 查看库的属性和方法
import termcolor
dir(termcolor)输出结果
[ATTRIBUTES,COLORS,HIGHLIGHTS,RESET,VERSION,__ALL__,__builtins__,__cached__,__doc__,__file__,__loader__,__name__,__package__,__spec__,colored,cprint,os,print_function]2. 查看库的帮助文档
help(termcolor)输出结果核心部分
Help on module termcolor:NAMEtermcolor - ANSII Color formatting for output in terminal.FUNCTIONScolored(text, colorNone, on_colorNone, attrsNone)Colorize text.Available text colors:red, green, yellow, blue, magenta, cyan, white.Available text highlights:on_red, on_green, on_yellow, on_blue, on_magenta, on_cyan, on_white.Available attributes:bold, dark, underline, blink, reverse, concealed.Example:colored(Hello, World!, red, on_grey, [blue, blink])colored(Hello, World!, green)cprint(text, colorNone, on_colorNone, attrsNone, **kwargs)Print colorize text.It accepts arguments of print function.DATAATTRIBUTES {blink: 5, bold: 1, concealed: 8, dark: 2, reverse: 7, underline: 4}COLORS {blue: 34, cyan: 36, green: 32, grey: 30, magenta: 35, red: 31, white: 37, yellow: 33}HIGHLIGHTS {on_blue: 44, on_cyan: 46, on_green: 42, on_grey: 40, on_magenta: 45, on_red: 41, on_white: 47, on_yellow: 43}RESET \x1b[0mVERSION (1, 1, 0)__ALL__ [colored, cprint]print_function _Feature((2, 6, 0, alpha, 2), (3, 0, 0, alpha, 0), 65536)3. 彩色文本输出示例
# 红色文本
print(termcolor.colored(error, red))输出结果终端中显示红色“error”
[31merror[0m# 错误示例attrs 中不能包含颜色值如 red只能包含属性如 bold
print(termcolor.colored(error, red, on_red, [red, bold]))输出结果报错因 ‘red’ 不是合法的属性
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
ipython-input-125-7c06270d31d5 in module
---- 1 print(termcolor.colored(error,red,on_red,[red, bold]))c:\users\tianjie\test1\lib\site-packages\termcolor.py in colored(text, color, on_color, attrs)110 if attrs is not None:111 for attr in attrs:
-- 112 text fmt_str % (ATTRIBUTES[attr], text)113114 text RESETKeyError: red# 正确示例白色文本、红色背景、反向显示、加粗绿色文本、红色背景
from termcolor import colored, cprinttext colored(Hello, World!, white, on_red, attrs[reverse, bold])
print(text)
cprint(Hello, World!, green, on_red)输出结果终端中显示对应格式的文本
[1m[7m[41m[37mHello, World×∏i1m(1−1pi)n×∏i1m(1−1pi)\varphi(n) \prod_{i1}^m \left[ p_i^{k_i} \times \left(1 - \frac{1}{p_i}\right) \right] \left( \prod_{i1}^m p_i^{k_i} \right) \times \prod_{i1}^m \left(1 - \frac{1}{p_i}\right) n \times \prod_{i1}^m \left(1 - \frac{1}{p_i}\right)φ(n)∏i1m[piki×(1−pi1)](∏i1mpiki)×∏i1m(1−pi1)n×∏i1m(1−pi1)。
性质 5与 nnn 互质数的和
所有小于 nnn 且与 nnn 互质的数的和为 sumn×φ(n)2\text{sum} n \times \frac{\varphi(n)}{2}sumn×2φ(n)。
证明 先证若 gcd(n,i)1\gcd(n,i) 1gcd(n,i)1则 gcd(n,n−i)1\gcd(n,n-i) 1gcd(n,n−i)1反证法 假设 gcd(n,i)1\gcd(n,i) 1gcd(n,i)1 但 gcd(n,n−i)k1\gcd(n,n-i) k 1gcd(n,n−i)k1则 k∣nk \mid nk∣n 且 k∣(n−i)k \mid (n-i)k∣(n−i)。由 k∣nk \mid nk∣n 和 k∣(n−i)k \mid (n-i)k∣(n−i) 可得 k∣ik \mid ik∣i因此 gcd(n,i)≥k1\gcd(n,i) \geq k 1gcd(n,i)≥k1与假设矛盾。故 gcd(n,i)1⟹gcd(n,n−i)1\gcd(n,i) 1 \implies \gcd(n,n-i) 1gcd(n,i)1⟹gcd(n,n−i)1。 由上述结论与 nnn 互质的数必成对出现iii 和 n−in-in−i且每对的和为 i(n−i)ni (n-i) ni(n−i)n。 与 nnn 互质的数共有 φ(n)\varphi(n)φ(n) 个因此共有 φ(n)2\frac{\varphi(n)}{2}2φ(n) 对总和为 n×φ(n)2n \times \frac{\varphi(n)}{2}n×2φ(n)。
性质 6欧拉函数与质数的乘积
设 ppp 为质数对任意正整数 iii
若 imodp0i \mod p 0imodp0即 ppp 是 iii 的质因数则 φ(i×p)p×φ(i)\varphi(i \times p) p \times \varphi(i)φ(i×p)p×φ(i)若 imodp≠0i \mod p \neq 0imodp0即 ppp 不是 iii 的质因数gcd(i,p)1\gcd(i,p)1gcd(i,p)1则 φ(i×p)(p−1)×φ(i)\varphi(i \times p) (p - 1) \times \varphi(i)φ(i×p)(p−1)×φ(i)。
证明 当 imodp0i \mod p 0imodp0 时 设 ipk×ti p^k \times tipk×t其中 gcd(t,p)1\gcd(t,p)1gcd(t,p)1则 i×ppk1×ti \times p p^{k1} \times ti×ppk1×t。由性质 4φ(i)i×(1−1p)×∏q∣t(1−1q)\varphi(i) i \times \left(1 - \frac{1}{p}\right) \times \prod_{q \mid t} \left(1 - \frac{1}{q}\right)φ(i)i×(1−p1)×∏q∣t(1−q1)φ(i×p)(i×p)×(1−1p)×∏q∣t(1−1q)p×[i×(1−1p)×∏q∣t(1−1q)]p×φ(i)\varphi(i \times p) (i \times p) \times \left(1 - \frac{1}{p}\right) \times \prod_{q \mid t} \left(1 - \frac{1}{q}\right) p \times \left[ i \times \left(1 - \frac{1}{p}\right) \times \prod_{q \mid t} \left(1 - \frac{1}{q}\right) \right] p \times \varphi(i)φ(i×p)(i×p)×(1−p1)×∏q∣t(1−q1)p×[i×(1−p1)×∏q∣t(1−q1)]p×φ(i)。 当 imodp≠0i \mod p \neq 0imodp0 时 因 gcd(i,p)1\gcd(i,p)1gcd(i,p)1由性质 2积性函数φ(i×p)φ(i)×φ(p)φ(i)×(p−1)\varphi(i \times p) \varphi(i) \times \varphi(p) \varphi(i) \times (p - 1)φ(i×p)φ(i)×φ(p)φ(i)×(p−1)性质 1 中 φ(p)p−1\varphi(p)p-1φ(p)p−1。
性质 7欧拉函数的和等于原数
对任意正整数 nnn有 n∑d∣nφ(d)n \sum_{d \mid n} \varphi(d)n∑d∣nφ(d)其中 d∣nd \mid nd∣n 表示 ddd 是 nnn 的正约数。
通俗证明 考虑分数集合 {1n,2n,3n,…,nn}\left\{ \frac{1}{n}, \frac{2}{n}, \frac{3}{n}, \dots, \frac{n}{n} \right\}{n1,n2,n3,…,nn}共 nnn 个分数。将每个分数化简为最简形式 ad\frac{a}{d}da其中 gcd(a,d)1\gcd(a,d)1gcd(a,d)1d∣nd \mid nd∣n
对每个约数 ddd化简后分母为 ddd 的分数其分子 aaa 必满足 1≤a≤d1 \leq a \leq d1≤a≤d 且 gcd(a,d)1\gcd(a,d)1gcd(a,d)1这样的 aaa 共有 φ(d)\varphi(d)φ(d) 个所有化简后的分数恰好覆盖原集合的 nnn 个分数因此所有 φ(d)\varphi(d)φ(d) 的和等于 nnn。
性质 8欧拉定理
对于互质的整数 aaa 和 mmm即 gcd(a,m)1\gcd(a,m)1gcd(a,m)1有 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}aφ(m)≡1(modm)。
证明 设集合 Z{q1,q2,…,qφ(m)}Z \{ q_1, q_2, \dots, q_{\varphi(m)} \}Z{q1,q2,…,qφ(m)}其中 q1,q2,…,qφ(m)q_1,q_2,\dots,q_{\varphi(m)}q1,q2,…,qφ(m) 是所有小于 mmm 且与 mmm 互质的数即 ZZZ 是 mmm 的缩系显然 ∣Z∣φ(m)|Z| \varphi(m)∣Z∣φ(m)。 构造集合 Y{(a×q1)modm,(a×q2)modm,…,(a×qφ(m))modm}Y \{ (a \times q_1) \mod m, (a \times q_2) \mod m, \dots, (a \times q_{\varphi(m)}) \mod m \}Y{(a×q1)modm,(a×q2)modm,…,(a×qφ(m))modm}需证明 YZY ZYZ 步骤 1YYY 中元素均属于 ZZZ因 gcd(a,m)1\gcd(a,m)1gcd(a,m)1 且 gcd(qi,m)1\gcd(q_i,m)1gcd(qi,m)1故 gcd(a×qi,m)1\gcd(a \times q_i, m)1gcd(a×qi,m)1因此 (a×qi)modm(a \times q_i) \mod m(a×qi)modm 是小于 mmm 且与 mmm 互质的数即属于 ZZZ。步骤 2YYY 中元素两两不同反证法假设 i≠ji \neq jij 但 (a×qi)modm(a×qj)modm(a \times q_i) \mod m (a \times q_j) \mod m(a×qi)modm(a×qj)modm则 a×(qi−qj)≡0(modm)a \times (q_i - q_j) \equiv 0 \pmod{m}a×(qi−qj)≡0(modm)。因 gcd(a,m)1\gcd(a,m)1gcd(a,m)1故 qi−qj≡0(modm)q_i - q_j \equiv 0 \pmod{m}qi−qj≡0(modm)即 qiqjq_i q_jqiqj与 i≠ji \neq jij 矛盾。 因 YZY ZYZ两组集合的元素乘积对模 mmm 相等 (a×q1)×(a×q2)×⋯×(a×qφ(m))≡q1×q2×⋯×qφ(m)(modm)(a \times q_1) \times (a \times q_2) \times \dots \times (a \times q_{\varphi(m)}) \equiv q_1 \times q_2 \times \dots \times q_{\varphi(m)} \pmod{m}(a×q1)×(a×q2)×⋯×(a×qφ(m))≡q1×q2×⋯×qφ(m)(modm) 左边整理为 aφ(m)×(q1×q2×⋯×qφ(m))a^{\varphi(m)} \times (q_1 \times q_2 \times \dots \times q_{\varphi(m)})aφ(m)×(q1×q2×⋯×qφ(m))因此 aφ(m)×(q1×q2×⋯×qφ(m))≡q1×q2×⋯×qφ(m)(modm)a^{\varphi(m)} \times (q_1 \times q_2 \times \dots \times q_{\varphi(m)}) \equiv q_1 \times q_2 \times \dots \times q_{\varphi(m)} \pmod{m}aφ(m)×(q1×q2×⋯×qφ(m))≡q1×q2×⋯×qφ(m)(modm) 因 q1,q2,…,qφ(m)q_1,q_2,\dots,q_{\varphi(m)}q1,q2,…,qφ(m) 均与 mmm 互质其乘积也与 mmm 互质可两边同时除以该乘积得 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}aφ(m)≡1(modm)
推论费马小定理若 ppp 为质数且 gcd(a,p)1\gcd(a,p)1gcd(a,p)1则 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)。 因质数 ppp 的欧拉函数 φ(p)p−1\varphi(p)p-1φ(p)p−1代入欧拉定理即可得。
四、欧拉函数求法
1. 线性筛法O(n)适合求 1 到 n 所有数的欧拉函数
利用欧拉函数的性质 2、3、6结合线性筛埃氏筛的优化可在 O(n)O(n)O(n) 时间内求出 1 到 nnn 所有数的欧拉函数值。
代码实现
#include iostream
#include cstring
using namespace std;const int maxn 1e6 10; // 根据需求调整最大值
int p[maxn]; // 存储质数
bool vis[maxn]; // 标记是否为合数
long long phi[maxn]; // 存储欧拉函数值
int cnt 0; // 质数的个数// 线性筛求 1~len 的欧拉函数
long long get_phi(int len maxn) {memset(vis, false, sizeof(vis));phi[1] 1; // 特殊规定φ(1)1for (int i 2; i len; i) {if (!vis[i]) { // i 是质数p[cnt] i;phi[i] i - 1; // 性质 1质数的欧拉函数为 i-1}// 遍历已找到的质数更新 i*p[j] 的欧拉函数for (int j 0; j cnt; j) {if (p[j] * i len) break; // 超出范围退出vis[p[j] * i] true; // 标记为合数if (i % p[j] 0) { // p[j] 是 i 的质因数性质 6 前半部分phi[i * p[j]] p[j] * phi[i];break;} else { // p[j] 不是 i 的质因数性质 6 后半部分phi[i * p[j]] phi[i] * (p[j] - 1);}}}
}int main() {get_phi(100); // 求 1~100 的欧拉函数for (int i 1; i 10; i) {cout φ( i ) phi[i] endl;}return 0;
}2. 单点求法O(√n)适合求单个正整数的欧拉函数
对单个正整数 xxx先进行质因数分解再代入欧拉函数公式 φ(x)x×∏p∣x(1−1p)\varphi(x) x \times \prod_{p \mid x} \left(1 - \frac{1}{p}\right)φ(x)x×∏p∣x(1−p1) 计算。
代码实现
#include iostream
using namespace std;typedef long long ll;// 求单个正整数 x 的欧拉函数
ll get_phi(ll x) {ll res x; // 初始值为 x// 质因数分解遍历到 √xfor (int i 2; (ll)i * i x; i) {if (x % i 0) { // i 是 x 的质因数res res - res / i; // 等价于 res * (1 - 1/i)while (x % i 0) { // 去除所有 i 的因子避免重复计算x / i;}}}if (x ! 1) { // 若 x 剩余部分为质数大于 √x 的质因数res res - res / x;}return res;
}int main() {ll x;cin x;cout φ( x ) get_phi(x) endl;return 0;
}五、欧拉函数的应用
1. 欧拉筛质数
线性筛法在求欧拉函数的同时也会筛选出所有质数存储在数组 ppp 中因此可直接用于质数筛选。
2. 欧拉降幂
在计算大指数幂 AkmodmA^k \mod mAkmodm 时利用欧拉函数可降低指数的规模避免直接计算大指数导致的溢出或效率低下。
欧拉降幂公式
若 gcd(A,m)1\gcd(A,m) 1gcd(A,m)1则 Ak≡Akmodφ(m)(modm)A^k \equiv A^{k \mod \varphi(m)} \pmod{m}Ak≡Akmodφ(m)(modm)若 gcd(A,m)≠1\gcd(A,m) \neq 1gcd(A,m)1 且 kφ(m)k \varphi(m)kφ(m)则 Ak≡Ak(modm)A^k \equiv A^k \pmod{m}Ak≡Ak(modm)直接计算若 gcd(A,m)≠1\gcd(A,m) \neq 1gcd(A,m)1 且 k≥φ(m)k \geq \varphi(m)k≥φ(m)则 Ak≡Akmodφ(m)φ(m)(modm)A^k \equiv A^{k \mod \varphi(m) \varphi(m)} \pmod{m}Ak≡Akmodφ(m)φ(m)(modm)。
说明公式的严格证明需结合数论中的“阶”和“缩系”概念实际应用中可直接记忆公式使用。 via 欧拉函数最全总结-CSDN博客 https://blog.csdn.net/weixin_41603028/article/details/107078050 欧拉函数及其性质-CSDN博客 https://blog.csdn.net/qq_37493070/article/details/81988725 欧拉降幂公式解析-CSDN博客 https://blog.csdn.net/weixin_38686780/article/details/81272848 欧拉函数详解-CSDN博客 https://blog.csdn.net/w144215160044/article/details/51158735 欧拉函数的几个性质及证明 - henry_y - 博客园 https://www.cnblogs.com/henry-1202/p/10246196.html 欧拉函数 φ(n) 的计算及欧拉定理 - 知乎 https://zhuanlan.zhihu.com/p/151756874
