`
jian0487
  • 浏览: 97492 次
  • 性别: Icon_minigender_1
  • 来自: 宁德
社区版块
存档分类
最新评论

欧拉函数

阅读更多
n为1至1000的整数时\varphi(n)的值
 
 
 

數論中,對正整數n歐拉函數\varphi(n)是小於或等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名,它又稱為φ函數歐拉商數等。

例如\varphi(8)=4,因為1,3,5,7均和8互質。

欧拉函数实际上是模n同余类所构成的乘法(即\mathbb{Z}/n\mathbb{Z}的所有单位元组成的乘法群)的。这个性质与拉格朗日定理一起構成了欧拉定理的證明。

 

目录

[隐藏]

<script type="text/javascript"></script>

 

欧拉函數的值

\varphi(1)=1(小于等于1的正整数中唯一和1互質的數就是1本身)。

n質數pk\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1},因為除了p倍數外,其他數都跟n互質。

歐拉函數是積性函數,即是说若m,n互質,\varphi(mn)=\varphi(m)\varphi(n)。證明:設A, B, C是跟m, n, mn互質的數的集,據中國剩餘定理A \times BC可建立雙射(一一對應)的關係。因此\varphi(n)的值使用算術基本定理便知,

n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}
\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac{1}{p}\right)

例如\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24

性质

n的欧拉函数\varphi(n) 也是循环群 Cn生成元的个数(也是n分圆多项式的次数)。Cn 中每个元素都能生成 Cn 的一个子群,即必然是某个子群的生成元。而且按照定义,不同的子群不可能有相同的生成元。此外, Cn 的所有子群都具有 Cd 的形式,其中d整除n(记作d | n)。因此只要考察n的所有因数d,将 Cd 的生成元个数相加,就将得到 Cn 的元素总个数:n。也就是说:

\sum_{d\mid n}\varphi(d)=n

其中的dn的正约数。

运用默比乌斯反转公式来“翻转”这个和,就可以得到另一个关于\varphi(n)的公式:

\varphi(n)=\sum_{d\mid n} d \cdot \mu(n/d)

其中 μ 是所谓的默比乌斯函数,定义在正整数上。

對任何兩個互質的正整數a, m(即 gcd(a,m) = 1),m\ge2,有

a^{\varphi(m)} \equiv 1 \pmod m

欧拉定理

这个定理可以由群论中的拉格朗日定理得出,因为任意与m互质的a都属于 \mathbb{Z}/n\mathbb{Z} 的单位元组成的乘法群\mathbb{Z}/n\mathbb{Z}^{\times}

m質數p時,此式則為:

a^{p-1} \equiv 1 \pmod p

費馬小定理

生成函数

以下两个由欧拉函数生成的级数都是来自于上节所给出的性质:\sum_{d|n} \varphi(d) = n

\varphi(n)生成的狄利克雷级数是:

\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

其中ζ(s)是黎曼ζ函数。推导过程如下:

\zeta(s) \sum_{f=1}^\infty \frac{\varphi(f)}{f^s} = \left(\sum_{g=1}^\infty \frac{1}{g^s}\right)\left(\sum_{f=1}^\infty \frac{\varphi(f)}{f^s}\right)
.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{h=1}^\infty \left(\sum_{fg=h} 1 \cdot \varphi(g)\right) \frac{1}{h^s}
.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{h=1}^\infty \left(\sum_{fg=h} \varphi(g)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d)\right) \frac{1}{h^s}
使用开始时的等式,就得到:\sum_{h=1}^\infty \left(\sum_{d|h} \varphi(d)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \frac{h}{h^s}
于是\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1)

欧拉函数生成的朗贝级数如下:

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

其对于满足 |q|<1 的q收敛

推导如下:

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n} =
\sum_{n=1}^{\infty} \varphi(n) \sum_{r\ge 1} q^{rn}

后者等价于:


\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) =
\sum_{k\ge 1} k q^k = \frac{q}{(1-q)^2}.

 欧拉函数的走势

随着n变大,估计\varphi(n) 的值是一件很难的事。当n为质数时,\varphi(n)=n-1,但有时\varphi(n)又与n差得很远。

n足够大时,有估计:

对每个 ε > 0,都有n > N(ε)使得 \,n^{1-\varepsilon}<\varphi(n)<n

如果考虑比值:

\,\varphi(n)/n,

由以上已经提到的公式,可以得到其值等于类似1 − p − 1的项的乘积。因此,使比值小的n将是两两不同的质数的乘积。由素数定理可以知道,常数 ε 可以被替换为:

C\,\log \log n/ \log n.

\varphi就平均值的意义上来说是与n很相近的,因为:

\frac{1}{n^2} \sum_{k=1}^n \varphi(k)= \frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right)

其中的O表示大O符号。这个等式也可以说明在集合 {1, 2, ..., n} 中随机选取两个数,则当n趋于无穷大时,它们互质的概率趋于 6 / π2 。一个相关的结果是比值\varphi(n)/n的平均值:

\frac{1}{n} \sum_{k=1}^n \frac{\varphi(k)}{k} = 
\frac{6}{\pi^2} + \mathcal{O}\left(\frac{\log n }{n}\right).

其他与欧拉函数有关的等式

  1. \;\varphi\left(n^m\right) = n^{m-1}\varphi(n)
  2.   \forall a \in N , \forall n \in N , \ \exists l \in N 使得 [(a >1 \and n > 1)\rightarrow (l|\varphi(a^n-1) \and l \geq n) ]
  3.     \forall a \in N , \forall n \in N , \ \exists l \in N 使得 [(a >1 \and n > 6 \and 4 \not| n )\rightarrow (l|\varphi(a^n-1) \and l \geq 2n) ]
  4. \sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}
  5. \sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1
  6. \sum_{k=1}^n\varphi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)
  7. \sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor
  8. \sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)
  9. \sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))

 与欧拉函数有关的不等式

  1. 
\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}
,其中n > 2,γ 为欧拉-马歇罗尼常数
  2. 
\varphi(n) \ge \sqrt{\frac {n} {2} }
,其中n > 0。
  3. 对整数n > 6,
\varphi(n) \ge \sqrt{n}
  4. n为质数时,显然有\varphi(n) = n-1。对于合数n,则有:

\varphi(n) \le n-\sqrt{n}

参考来源

  • Milton Abramowitz、Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications , New York. ISBN 0-486-61272-4. 24.3.2节.
  • Eric Bach、Jeffrey Shallit, Algorithmic Number Theory, 卷 1, 1996, MIT Press. ISBN 0-262-02405-5, 8.8节,234页.
  • 柯召,孙琦:数论讲义(上册),第二版,高等教育出版社,2001
分享到:
评论

相关推荐

    欧拉函数计算 C语言实现

    欧拉函数 C语言实现 #include "iostream" #include "math.h" #define maxsize 100 using namespace std; typedef struct node { int num; int total; }struct_num; struct_num a[maxsize]; int is_prime(int n)

    欧拉函数公式以及证明

    欧拉函数 : 欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,...

    组合数学 实现 欧拉函数 cayley定理 等

    这里我们将详细探讨标题和描述中提到的几个关键概念:欧拉函数、Cayley定理、Mobius定理以及整数拆分。 1. **欧拉函数**(Euler's totient function): 欧拉函数φ(n)定义为小于n且与n互质的正整数的数量。它是...

    欧拉函数的几个性质及证明.pdf

    欧拉函数(Euler's totient function),通常表示为φ(n),是数论中一个非常重要的函数。它定义为在1到n之间(包含1和n)与n互质的正整数个数。例如,φ(1)=1,因为只有1与1互质;φ(2)=1,因为只有1与2互质;φ(3)=...

    代码实现,欧拉函数代码实现,matlab

    标题提到的"代码实现,欧拉函数代码实现,matlab",表明我们将讨论如何在MATLAB环境中实现欧拉函数。欧拉函数,通常用φ(n)表示,是计算小于或等于n且与n互质的正整数的数量,它在数论中具有重要的地位。MATLAB是一种...

    欧拉定理与欧拉函数证明.mp4

    视频讲解欧拉定理和欧拉函数的证明。详细解释了证明简化剩余系的关系为什么要先证明完全剩余系的关系。以及欧拉函数的计算。

    线性素筛 欧拉函数 区间筛素数.zip_sowoc_算法 欧拉函数 线性筛

    总的来说,"线性素筛 欧拉函数 区间筛素数.zip_sowoc_算法 欧拉函数 线性筛"这个压缩包文件包含了一种高效的算法实现,该算法能够在线性时间内筛选素数,并且能快速计算欧拉函数值,适用于需要处理大量素数和欧拉...

    算法-数论- 欧拉函数.rar

    欧拉函数,通常用大写字母 φ 表示,是数论中一个非常重要的概念,由瑞士数学家欧拉在18世纪引入。这个函数在数论领域内有着广泛的应用,尤其是在模运算、同余类以及素数分布等方面。欧拉函数定义为:对于正整数n,...

    扩展欧几里得、模幂运算、欧拉函数

    在计算机科学和数学中,特别是在密码学和数论领域,扩展欧几里得算法、模幂运算以及欧拉函数是至关重要的工具。这些概念在解决复杂数学问题时起着核心作用,尤其是在处理整数的性质和计算上。下面我们将深入探讨这三...

    简化剩余系和欧拉函数.ppt

    在数论的广阔天地中,欧拉函数和简化剩余系如同两颗璀璨的明珠,它们在理论研究和实际应用中都占据着举足轻重的位置。欧拉函数 φ(n) 是一个计数函数,它描述了在1到n的所有正整数中,与n互素的正整数的个数。互素...

    euler.rar_Euler迭代_holehhw_欧拉_欧拉函数_欧拉法

    在微积分中,\(e^x\) 的导数就是它自身,这使得欧拉函数在微分方程中具有特别的地位。然而,在这个上下文中,"欧拉"更可能指的是欧拉迭代法,而不是欧拉函数。 **euler.slx文件** 根据提供的文件名 "euler.slx",...

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...

    代码实现,欧拉函数代码实现,matlab源码.zip

    欧拉函数,通常表示为φ(n),是数论中的一个重要概念,由数学家欧拉引入。这个函数计算了小于或等于n的正整数中与n互质(最大公约数为1)的数的数量。在密码学、计算复杂性和其他数学分支中,欧拉函数有广泛的应用。...

    欧拉函数 1

    "欧拉函数 1" 欧拉函数是一种_IMPORTANT_函数在数论中,它表示 1 到 n-1 之间,与 n 互质的数的个数。在本篇文章中,我们将详细介绍欧拉函数的定义、计算方法和应用场景。 定义 欧拉函数 phi(n) 是指 1 到 n-1 ...

    简化剩余系与欧拉函数PPT学习教案.pptx

    《简化剩余系与欧拉函数》的学习教案涵盖了数学领域中重要的数论概念,特别是与整数模运算相关的理论。欧拉函数(Euler's totient function),记为φ(k),是一个计算与给定正整数k互素的整数数量的函数。例如,φ(2...

    讲义204-第二章第四讲-欧拉函数的计算(2023-1005,周四34).pdf

    **欧拉函数的基本概念** 欧拉函数,记作(),是数论中的一个重要函数,它表示小于或等于的正整数中与互素的数的个数。换句话说,()计算的是集合{0, 1, ..., - 1}中与的最大公约数为1的元素数量。这个函数在数论的...

    PHP简单实现欧拉函数Euler功能示例

    欧拉函数的定义是:对于任意正整数n,欧拉函数φ(n)表示的是小于或等于n的正整数中与n互质的数的数目。所谓“互质”,指的是两个数的最大公约数为1。例如,φ(10)=4,因为1、3、7、9这四个数都和10互质。 在PHP中...

    Euler函数前缀

    总结来说,"欧拉函数前缀"是一个在数学和计算机科学中涉及数论和算法的重要概念,它涉及到欧拉函数的性质、计算以及在实际编程问题中的应用。理解和掌握这一知识点,不仅有助于解决竞赛编程问题,还能为深入学习数论...

    应用容斥原理推广欧拉函数 (2015年)

    利用容斥原理对欧拉函数进行了推广,得出如下结论:1 )给出了欧拉函数的3 种初步推广,即函数φr;k (m),Ωr;k;l (m),Hr;k;l (m),找到并证明了r= 0 的 3 个表达式;2 )进一步推广了欧拉函数,得到并...

    Not矩阵的广义平方根及其在隐逻辑算子揭示和全矩阵圆欧拉函数定义中的应用_Generalized Square roots of

    《Not矩阵的广义平方根及其在隐逻辑算子揭示和全矩阵圆欧拉函数定义中的应用》 本文深入探讨了Not矩阵的广义平方根的概念,并将其应用于逻辑操作的矩阵表示以及全矩阵圆欧拉函数的定义。Not矩阵在量子计算理论中...

Global site tag (gtag.js) - Google Analytics