欧拉函数

作者: ffacs 分类: 总结 发布时间: 2020-05-08 17:23

在数论中,对 正整数 $n$, 欧拉函数 $\phi(n)$ 是 小于等于 $n$ 的正整数中与 $n$ 互质的数的数目。

求欧拉函数值

首先我们考虑素数的欧拉函数值,素数肯定与小于本身的正整数互质,所以 $\phi(p)=p-1$

接下来我们考虑素数的 $k$ 次方的欧拉函数值。 如果一个数是 某个素数 $p$ 的 $k$ 次,那么小于等于自身的正整数中,与自身 互质的有 $p,2p,3p…p^{k-1}p$, 共 $p^{k-1}$个数。那么 $\phi(p^k)=p^k-p^{k-1}=p^{k-1}(k-1)$

接下来我们进一步考虑如果一个数是两个互质的数的乘积。设 $n=rs,(r,s)=1$,设一个数 $x$ 与 $n$ 互质,则 $x \bmod s\neq 0 ,x \bmod r \neq 0$, $(r,x\bmod r)=1,(s,x\bmod s)=1$, 也就是说 $x$ 与一个与 $s$ 互质的数和一个与 $r$ 互质的数对应。同时反过来,一个与 $s$ 互质的数和一个与 $r$ 互质的数唯一对应了一个 $\left[1,rs\right]$ 中的一个数。因为方程

$$
\cases{
x \equiv s \mod s \\ x \equiv r \mod r \
}
$$


的通解为 $x+krs$, 同时因为 $x$ 与 $s$ 和 $r$ 都互质,$(x,r*s)=1$ 。

我们就得到了一个双射。所以 $\phi(rs)=\phi(r)\phi(s)$ ,这也就是欧拉函数的可积性.

有了可积性,我们也就能给出任意一个数的欧拉函数值的求法了。

设 $n=p_1^{k_1}p_2^{k_2}…p_n^{k_n}$ 则
$$
\begin{align}
\phi(n)&=\phi(p_1^{k_1})\phi(p_2^{k_2})…\phi(p_n^{k_n}) \\
&=p_1^{k_1}(1-\frac{1}{p_1})p_2^{k_2}(1-\frac{1}{p_2})…p_n^{k_n}(1-\frac{1}{p_n}) \\
&=n\prod_\limits{i=1}^\limits{n}(1-\frac{1}{p_i})
\end{align}
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注