欧拉定理相关性质及证明

最新推荐文章于 2023-08-13 15:14:27 发布

良月澪二

最新推荐文章于 2023-08-13 15:14:27 发布

阅读量1.1k

点赞数 5

分类专栏：欧拉定理证明 ========数论======== 文章标签：欧拉定理

本文链接：https://blog.csdn.net/yandaoqiusheng/article/details/102686554

版权

========数论======== 同时被 3 个专栏收录

29 篇文章

订阅专栏

证明

7 篇文章

订阅专栏

欧拉定理

4 篇文章

订阅专栏

欧拉定理：当 $a$ 与 $n$ 互质时，有 $a^{\phi(n)}\equiv 1\mod n$
通项公式及其证明：
如果 $n=p^k$ ， $p$ 为质数，则 $\phi(p^k)=p^k-p^{k-1}$

证明：当一个数不包含质因子 $p$ 时就能与 $n$ 互质，小于等于 $n$ 的数中包含质因子p的只有 $p^{k-1}$ 个，即 $p,2*p,...,p^{k-1}*p$ ，把他们去除即可

由唯一分解定理可知， $n=p_{1}^{a_1}p_{2}^{a_2}...p_{k}^{a_k}$
$\begin{aligned} \phi(n) &=\phi(p_{1}^{a_1})\phi(p_{2}^{a_2})...\phi(p_{k}^{a_k})\\ &=p_{1}^{a_1}(1-\frac{1}{p_1})p_{2}^{a_2}(1-\frac{1}{p_2})...p_{k}^{a_k}(1-\frac{1}{p_k})\\ &=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k}) \end{aligned}$
这就是欧拉函数的通项公式
欧拉定理证明：
设 $A=\left\{x_1,x_2,...,x_{\phi(n)}\right\}$ 是 $1 - n$ 中与 $n$ 互质的数的集合
则他们模 $n$ 两两不相同，且余数与 $n$ 互质
下面我们证明 $B=\left\{ax_1,ax_2,...,ax_{\phi(n)}\right\}$ 也有这两个性质
模 $n$ 两两不相同：反证法，设 $i! = j$ 且 $ax_i\equiv ax_j\mod n$ ，即 $a(x_i-x_j)\equiv 0\mod n$
由于 $a$ 与 $n$ 互质，且 $x_i-x_j)$ 不可能是 $n$ 的倍数，所以不可能存在这样的 $i$ 和 $j$ 。
余数都与 $n$ 互质：因为 $a$ 与 $n$ 互质， $x_i$ 与 $n$ 互质，所以 $ax_i$ 也与 $n$ 互质， $ax_i$ 模 $n$ 后也与 $n$ 互质。
所以 $B$ 这个集合模 $n$ 后一定是 $\phi(n)$ 个两两不同且与 $n$ 互质的数，即为 $A$
$\displaystyle\prod_{i=1}^{\phi(n)}ax_i\equiv\displaystyle\prod_{i=1}^{\phi(n)}x_i(\mod n)\longrightarrow a^{\phi(n)}\displaystyle\prod_{i=1}^{\phi(n)}x_i\equiv\displaystyle\prod_{i=1}^{\phi(n)}x_i(\mod n)\longrightarrow a^{\phi(n)}\equiv 1(\mod n)$