Last Updated: 2023-04-18 09:44:07 Tuesday
-- TOC --
本文总结欧拉函数和欧拉定理的基本概念，注意不是那个著名的欧拉公式！欧拉牛逼...
所谓函数，就是一个计算从输入到输出的过程，有过编程经验的同学会很好理解。欧拉函数，计算的是与小于等于输入的那个数存在互质关系的数的个数。
任意给定正整数n，问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到12之中，有多少个数与12构成互质关系？）计算这个值得方法，就叫欧拉函数，以 \(\psi(n)\) 表示。在1到12中，与12互质的正整数有：1,5,7,11，因此 \(\psi(12)=4\) 。只有1与它自己构成互质，其它任何正整数都不与自己构成互质。
现在开始一步步推到欧拉函数的计算公式。
如果n=1，则 \(\psi(1)=1\) 。因为1与任何数（包括自身）都构成互质关系。
如果n是质数，则 \(\psi(n)=n-1\) 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。（1不是质数）
如果n是质数的某次方，即如果 \(n=p^k\)，p是质数，\(k\ge{1}\)，则：
$$ \psi(p^k)=p^k-p^{k-1} $$
因为，只有当一个数不包含质数p的时候（质因数分解，没有p），才可以与n互质。而含有质因数p的小于等于n的数，分别是： \(1\times p\)，\(2\times p\)，\(3\times p\)，......，\(p^{k-1}\times p\)，现在含有质因数p的数，有 \(p^{k-1}\) 个。用总数减去这些数，剩下的就都是与n互质的数了。
上面的公式，还可以写成如下形式：
$$ \psi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p}) $$
第2种情况，就是 \(k=1\) 时的特例。
如果n可以分解成两个互质整数的积， \(n=p1 \times p2\)，则：
$$\psi(n)=\psi(p1)\times\psi(p2)$$
即积的欧拉函数值，等于各因子（这里不是质因子，而是互质因子）的欧拉函数值的积。
据说要用“中国剩余定理”来证明第4种情况，我就举个例子来简单理解吧：
$$\psi(15)=\psi(3)\times\psi(5)=2\times{4}=8$$
与3互质的数：1,2；与5互质的数：1,2,3,4；与15互质的数：1,2,4,8,10,11,13,14
因为任意一个大于1的正整数，都可以分解为一系列质因数的乘积（质因数分解唯一定理），根据第3和4种情况，我们可以得到：
$$\begin{align} \psi(n)&=\psi(p_1^{k1})\psi(p_2^{k2})...\psi(p_n^{kn})\\ &=p_1^{k1}p_2^{k2}...p_n^{kn}(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})\\ \end{align}$$
这就是欧拉函数，可以直接计算任何数的互质数个数，前提是这个数要能够被质因数分解！（中学学过的质因数分解，还是有点用的）
欧拉函数的作用，在于欧拉定理，如下：
如果两个正整数a和n互质，则n的欧拉函数 \(\psi(n)\) 可以使下面的等式成立：
$$a^{\psi(n)} \equiv 1 \pmod{n}$$
即，\(a^{\psi(n)}\) 被n除的余数是1，或者说 \(a^{\psi(n)}-1\) 可以被n整除。
证明太复杂，我也不懂，先了解结论。欧拉定理的作用，在于可以大大简化某些计算过程。
比如，7和10互质，根据欧拉定理：
\(7^{\psi(10)} \equiv 1\pmod{10}\)
\(\psi(10)=4\)，因此可以得到 \(7^{4k}\equiv1\pmod{10}\)
即7的任意4倍次方的个位数都是1。
欧拉定理的一个特殊情况：
假设正整数a和质数p互质，因质数p的欧拉函数为\(\psi(p)=p-1\)，则欧拉定理可以写成：
$$a^{p-1}\equiv1\pmod{p}$$
这就是著名的费马小定理。
欧拉定理是RSA算法的核心，理解欧拉定理，就可以理解RSA算法。
本文链接：https://cs.pynote.net/math/202110047/
-- EOF --
-- MORE --