欧拉函数

补博客ing……

欧拉函数

今天,我们就来谈谈欧拉函数φ\varphi(话说这符号还挺好看的)

欧拉函数(Eulers  totient  function\mathtt{Euler's \; totient \; function}),即 φ(n)\varphi(n) ,表示的是小于等于 nnnn 互质的数的个数。

最简单的例子:φ(1)=1\varphi(1)=1

互质是公约数只有1的两个整数,叫做互质整数。公约数只有1的两个自然数,叫做互质自然数,后者是前者的特殊情形。

nn为质数时,很明显φ(n)=n1\varphi(n)=n-1

唯一分解定理与欧拉函数

利用唯一分解定理,我们可以把一个整数唯一地分解为质数幂次的乘积,

n=p1k1p2k2psksn = p_1^{k_1}p_2^{k_2} \cdots p_s^{k_s} ,其中 pip_i 是质数,那么定义 φ(n)=n×i=1spi1pi\varphi(n) = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}}

未完待续……

文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/08/17/欧拉函数/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论