数论四大定理之欧拉定理

作者: M_lear | 来源:发表于2019-02-02 11:35 被阅读0次

数论四大定理之欧拉定理
数论四大定理
2020-01-22（学习笔记附录）
欧拉定理
补充：复数、欧拉公式、棣美弗定理
Python解中国剩余定理（孙子定理）
同余方程(组)
数论四大定理之威尔逊定理
快速幂取余
公钥密码之RSA

本文分为两个部分，第一部分介绍欧拉定理的证明，第二部分介绍欧拉函数的求法。

欧拉函数

欧拉函数 $\varphi(n)(n\in N^*)$ 是小于等于 n 的正整数中与 n 互质的数的个数。

欧拉定理

对于任意互素的 $a和n$ ，有 $a^{\varphi(n)}\equiv1(\mod n)$

一、欧拉定理的证明

记小于 n 且与 n 互质的正整数集合为
$R=\{x_1,x_2,\cdots,x_{\varphi(n)}\}$
令 $S=\{ax_1\%n,ax_2\%n,\cdots,ax_{\varphi(n)}\%n\}$
$\forall i\in[1,\varphi(n)]$
$\because (a,n)=1,(x_i,n)=1$
$\therefore (ax_i,n)=1$
由最大公约数的性质可得 $(ax_i\%n,n)=1$
所以 S 中所有元素都与 n 互质，且都小于 n。
又 S 中无重复元素
假设 $i\neq j,ax_i\%n=ax_j\%n$
$即ax_i\equiv ax_j(\mod n),又(a,n)=1$
$\therefore x_i\equiv x_j(\mod n),i=j$ ，矛盾！
$\therefore S=R$
$\therefore\prod_{i=1}^{\varphi(n)}ax_i\%n=\prod_{i=1}^{\varphi(n)}x_i$
$\therefore\prod_{i=1}^{\varphi(n)}ax_i\equiv\prod_{i=1}^{\varphi(n)}x_i(\mod n)\Longrightarrow a^{\varphi(n)}\prod_{i=1}^{\varphi(n)}x_i\equiv\prod_{i=1}^{\varphi(n)}x_i(\mod n)$
$又(\prod_{i=1}^{\varphi(n)}x_i,n)=1$
$故a^{\varphi(n)}\equiv1(\mod n)$

二、欧拉函数的求法

$\varphi(1)=1$
如果 n 是质数，则 $\varphi(n)=n-1$ 。
因为质数与小于它的每一个正整数都互质。
如果 $n=p^k(p为质数,k\in N^*)$ ，则 $\varphi(p^k)=p^k-p^{k-1}$ ，这是因为只要当一个数不包含因子 p 时，就能与 $p^k$ 互质。而小于等于 n 包含质数 p 的数一共有 $p^{k-1}$ 个，即 $1\times p,2\times p,\cdots,p^{k-1}\times p$ ，把它们去除，剩下的就是与 $p^k$ 互质的数。
上式也可以写作： $\varphi(p^k)=p^k(1-\frac{1}{p})$
$如果n=p\cdot q$ ，而且 $p,q$ 互质，有 $\varphi(n)=\varphi(p\cdot q)=\varphi(p)\cdot\varphi(q)$ （欧拉函数是积性函数）
这一条的证明要用到"中国剩余定理"，这里就不展开了，只简单说一下思路：如果
a (a < p) 与 p 互质，b (b < q) 与 q 互质，c (c < pq) 与 pq 互质，则 c 与数对 (a , b) 是一一对应关系。由于 a 的值有 $\varphi(p)$ 种可能，b 的值有 $\varphi(q)$ 种可能，则数对 (a , b) 有 $\varphi(p)\cdot\varphi(q)$ 种可能，而 c 的值有 $\varphi(p\cdot q)$ 种可能，所以 $\varphi(p\cdot q)=\varphi(p)\cdot\varphi(q)$
通式，因为任意一个大于1的正整数，都可以写成一系列质数的积。
$n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}(p_1,\cdots,p_r都为质数)$
由4可得 $\varphi(n)=\varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots\varphi(p_r^{k_r})$
再由3可得 $\varphi(n)=p_1^{k_1}\cdot p_2^{k_2}\cdots p_r^{k_r}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_r})$
$即\varphi(n)=n\sum_{i=1}^r(1-\frac{1}{p_i})$

数论四大定理之欧拉定理
本文分为两个部分，第一部分介绍欧拉定理的证明，第二部分介绍欧拉函数的求法。欧拉函数欧拉函数是小于等于 n 的正...
数论四大定理
威尔逊定理、欧拉定理、孙子定理、费马小定理
2020-01-22（学习笔记附录）
数论概论同余式、幂与费马小定理费马小定理：p为质数，a除以p不为0，则a^(p-1) 除以p余1 欧拉公式：若...
欧拉定理
欧拉函数欧拉函数是小于等于的正整数中与互质的数的个数。欧拉定理对于任意互素的和，有参考链接费马小定理...
补充：复数、欧拉公式、棣美弗定理
复数欧拉公式棣美弗定理
Python解中国剩余定理（孙子定理）
中国剩余定理（Chinese Remainder Theorem，CRT）又称孙子定理，是数论中的一个定理。古典数...
同余方程(组)
第二章同余欧拉-费马定理定理1 （i）欧拉函数是积性的，即如果，则有（ii）设是的标准分解，...
数论四大定理之威尔逊定理
威尔逊定理 p 为质数证明：必要性：假设 p 不是质数，且 a 是 p 的质因子。易知，则，前后矛盾！故 p ...
快速幂取余
本文分成以下四个部分，全部都跟取余有关：引理证明介绍快速幂取余了解数论中的欧拉定理模幂运算如果你只想看快速...
公钥密码之RSA
算法分析 RSA是最早的公钥密码系统之一, 广泛用于安全数据传输。 RSA的基础是数论的欧拉定理，它的安全性依赖于...