数论四大定理之欧拉定理

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

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

欧拉函数

欧拉函数 $\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})$

数论四大定理之欧拉定理

一、欧拉定理的证明

二、欧拉函数的求法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读