欧拉函数

jian0487

浏览: 96125 次
性别:
来自: 宁德

最近访客更多访客>>

wyzyanys

发发的啥

zyz251314

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

随笔

C C++C#出版 JavaScript

当n为1至1000的整数时 $\varphi(n)$ 的值

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

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

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

欧拉函數的值

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

若n是質數p的k次冪， $\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 B$ 和 $C$ 可建立雙射(一一對應)的關係。因此 $\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)$ 也是循环群 C_n 的生成元的个数（也是n阶分圆多项式的次数）。C_n 中每个元素都能生成 C_n 的一个子群，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， C_n 的所有子群都具有 C_d 的形式，其中d整除n（记作d | n）。因此只要考察n的所有因数d，将 C_d 的生成元个数相加，就将得到 C_n 的元素总个数：n。也就是说：

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

其中的d为n的正约数。

运用默比乌斯反转公式来“翻转”这个和，就可以得到另一个关于 $\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).$

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

$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n)$
$\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) ]$
$\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) ]$
$\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}$
$\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1$
$\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)$
$\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor$
$\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)$
$\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))$

与欧拉函数有关的不等式

$\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$ ，其中n > 2，γ 为欧拉-马歇罗尼常数。
$\varphi(n) \ge \sqrt{\frac {n} {2} }$ ，其中n > 0。
对整数n > 6， $\varphi(n) \ge \sqrt{n}$ 。
当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页.

Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311.

柯召，孙琦：数论讲义（上册），第二版，高等教育出版社，2001

分享到：

DES算法理论 | 悖论概念

2009-08-11 00:47
浏览 1589
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

欧拉函数

目录

欧拉函數的值

性质

生成函数

欧拉函数的走势

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

与欧拉函数有关的不等式

参考来源

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

欧拉函数

目录

欧拉函數的值

性质

生成函数

欧拉函数的走势

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

与欧拉函数有关的不等式

参考来源

评论

发表评论

相关推荐

你想知道您的那个端口号被那个程序占用了吗？

在电话接入时处理音频播放

单向陷门函数

RSA加密算法

数据加密标准DES

Java做一个最简单的Socket通话程序

C/S模式中的远程方法调用

Java加密和数字签名编程快速入门

Vigenere密码与Playfair密码 收

java实现DES加密算法

DES算法理论

悖论概念

生日悖论

TCP/IP端口基础常识大全

嵌入式处理器的基本概念

嵌入式实时操作系统的现状和未来

网络编程－－WININET

Mod运算

欧拉定理 (数论)

数字签名和加密

最近访客更多访客>>

Vigenere密码与Playfair密码收