首页 > 其他 > 详细

欧拉定理及扩展(附超易懂证明)

时间:2019-08-13 23:56:22      阅读:146      评论:0      收藏:0      [点我收藏+]

欧拉定理

\(\gcd(a,m)=1\),则满足\(a^{\varphi (m)} \equiv 1 \pmod m\)

证明

\([1,m)\)内与\(m\)互质的数为数列\(\{b_n\}=\{b_1,b_2,b_3,\cdots,b_{\varphi (m)}\}\)

因为\(a,m\)互质且\(b_i,m\)互质,所以数列\(\{A_n\}=\{ab_1,ab_2,ab_3,\cdots,ab_{\varphi(m)}\}\)中每个数都与\(m\)互质,且两两不同。

同时,由\(\gcd(ab_i,m)=1\)可得\(\gcd(ab_i \bmod m,m)=1\),即每个\(A_i\)除以\(m\)的余数都与\(m\)互质,且余数两两不同。

可以用反证法推出“余数两两不同”。假设存在\(ab_i \equiv ab_j \pmod m\),那么\(ab_i-ab_j=km\ (k \in \mathbb{Z})\),即\(a(b_i-b_j)=km\)。由于\(a\)\(m\)互质,那么只能是\(m \mid (b_i-b_j)\),即\(b_i \equiv b_j \pmod m\)。这与\(1 \leq b_i,b_j < m\)\(b_i \neq b_j\)的题设相违背,因此假设不成立。

所以\(\{A_n\}\)中的每个数一定与\(\{b_n\}\)中的一个数同余,且一一对应。

所以\(a^{\varphi (m)}\prod_{i=1}^{\varphi (m)}b_i \equiv \prod_{i=1}^{\varphi (m)}ab_i \equiv \prod_{i=1}^{\varphi (m)}b_i \pmod m\)

所以\(m \mid a^{\varphi (m)}\prod_{i=1}^{\varphi (m)}b_i-\prod_{i=1}^{\varphi (m)}b_i\)

\(m \mid (a^{\varphi (m)}-1)\prod_{i=1}^{\varphi (m)}b_i\)

又因为\(\gcd(m,\prod_{i=1}^{\varphi (m)}b_i)=1\)

所以\(m \mid a^{\varphi (m)}-1\)

\(a^{\varphi (m)} \equiv 1 \pmod m\)

费马小定理

\(p\)为质数,则\(a^{p-1} \equiv 1 \pmod p\)

证明:因为\(p\)为质数时,\(\varphi(p)=p-1\)

扩展欧拉定理

扩展到不要求互质。

\[ a^c \equiv \begin{cases} a^{c \bmod \varphi(m)} &\gcd(a,m)=1 \ a^c &\gcd(a,m) \neq 1,c<\varphi(m) \ a^{\left(c \bmod \varphi(m)\right)+\varphi(m)} &\gcd(a,m) \neq 1,c \geq \varphi(m) \end{cases} \pmod m \]

证明

case 1

\(\gcd(a,m)=1\)时,由欧拉定理知\(a^{\varphi (m)} \equiv 1 \pmod m\)

我们可以把指数\(c\)拆成\(k \times \varphi(m) + \left(c \bmod \varphi(m)\right)\),那么\(a^c=\left(a^{\varphi(m)}\right)^k \times a^{c \bmod \varphi(m)}\),再取模,就得到

\[ a^c \equiv a^{c \bmod \varphi(m)} \pmod m \]

case 2

\(\gcd(a,m) \neq 1\)\(c < \varphi(m)\)时,
\[ a^c \equiv a^c \pmod m \]

(无需证明)

case 3

\(\gcd(a,m) \neq 1\)\(c\geq \varphi(m)\)时,
\[ a^c\equiv a^{(c \bmod \varphi(m))+\varphi(m)} \pmod m \]

证明:

1.转化

要证明上式,只需证\(a\)的任意一个质因子\(p_i\)满足\({p_i}^c \equiv {p_i}^{(c \bmod \varphi(m))+\varphi(m)} \pmod{m}\)

1.1 证明转化的正确性

如果上式成立,设\(a\)质因数分解的结果为\(a=p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots\),其中\(p_i\)为质因数,\(r_i\)为其对应的指数

根据同余式可乘可推出\(({p_i}^c)^{r_i} \equiv ( {p_i}^{(c \bmod \varphi(m))+\varphi(m)} )^{r_i} \pmod{m}\)

进而\((p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots)^{c} \equiv (p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots)^{(c \bmod \varphi(m))+\varphi(m)} \pmod{m}\)

发现这就是\(a^c \equiv a^{\left(c \bmod \varphi(m)\right)+\varphi(m)} \pmod m\)

2.证明转化后的式子

那么现在要证明的东西已经转化,考虑如何证得\({p_i}^c \equiv {p_i}^{(c \bmod \varphi(m))+\varphi(m)} \pmod{m}\)(以下简称\(p_i\)\(p\)

2.1 若\(m,p\)互质

问题转化为case 1的情况。为了防止你翻上去,我再推一遍:

\(\gcd(m,p)=1 \Longrightarrow p^{\varphi(m)} \equiv 1 \pmod m\)(欧拉定理)

可以将指数\(c\)拆成\(k \times \varphi(m) + \left(c \bmod \varphi(m)\right)\),那么\(p^c=(p^{\varphi(m)})^k \times p^{c \bmod \varphi(m)}\)

再对\(m\)取模,就得到\(p^c \equiv (p^{\varphi(m)})^k\times p^{c \bmod \varphi(m)} \equiv 1^k\times p^{c \bmod \varphi(m)} \equiv p^{c \bmod \varphi(m)} \equiv p^{(c \bmod \varphi(m))+\varphi(m)} \pmod m\)

2.2 若\(p,m\)不互质

由于\(p\)为质数,则\(m\)必定\(\geq 2p\)

\(m=s\times p^r\),其中\(r=\lfloor\log_p{m}\rfloor\)(看作把\(m\)质因数分解后含有\(p^r\),剩下的都在\(s\)里,剩下的\(s\)不含因数\(p\)),那么\(\gcd(s,p^r)=\gcd(s,p)=1\)

根据欧拉定理\(p^{\varphi(s)} \equiv 1 \pmod s\)

因为\(s,p^r\)互质,所以\(\varphi(m)=\varphi(s)\times \varphi(p^r)\)(欧拉函数是积性函数),即\(\varphi(s) \mid \varphi(m)\)

结合欧拉定理\(p^{\varphi(s)} \equiv 1 \pmod{s}\)可得

\(p^{\varphi(m)} = (p^{\varphi(s)})^{\varphi(p^r)} \equiv 1^{\varphi(p^r)} = 1 \pmod{s}\)

同时乘以\(q^r\)得到

\(p^{r+\varphi(m)} \equiv p^r \pmod{s\times p^r}\)

\(m=s\times p^r\),则\(p^{r+\varphi(m)} \equiv p^r \pmod{m}\)

题设条件\(c\geq \varphi(m)\),显然\(\varphi(m)\geq r\)

本蒟蒻觉得这一点也不显然,花了好久才证明出\(\varphi(m)\geq r\)……QAQ
下面附上我的证明方法(我觉得应该有更简单的方法)

首先\(\varphi(m)=\varphi(s)\times \varphi(q^r) \geq \varphi(p^r)\)(等号在\(s=1,2\)时取到)

\(\varphi(p^r)=p^r-p^{r-1}=(p-1)\times p^{r-1} \geq p^{r-1}\)\(p\geq 2\),等号在\(p=2\)时取到)

数学归纳法\(p^{r-1}\geq r\)\(r=1\)时显然成立,假设\(r=i\)\(p^{i-1}\geq i\)成立,可推知\(p^{i}=p\times p^{i-1}\geq 2\times p^{i-1}=p^{i-1}+p^{i-1}\geq p^{i-1}+1=i+1\)成立,因此\(p^{r-1}\geq r\)对任意的\(p,r\in \mathbb{Z},p\geq 2,r\geq 1\)成立

把上面所有的不等号串起来,就是\(\varphi(m)\geq r\)

那么\(p^c=p^{c-r}\times p^r \equiv p^{c-r} \times p^{r+\varphi(m)}=p^{\varphi(m)+c} \pmod m\)

\(f(x)=x\bmod m\;(x\geq \varphi(m))\),上式表明:对于任意的正整数\(x\)\(f(x+\varphi(m))=f(x)\)。反过来\(f(x)=f(x-\varphi(m))\),但要注意定义域:此时\(x\)要满足\(x-\varphi(m)\geq \varphi(m)\),即\(x\geq 2\varphi(m)\)

如果要计算\(f(c)\),可以递推上面那个式子,每次让\(c-=\varphi(m)\),但只有\(c\geq 2\varphi(m)\)时才可以这样操作。

我们知道,如果递推条件改成\(c\geq \varphi(m)\),显然最后递推得到的值为\(c\bmod \varphi(m)\)。但现在条件是\(c\geq 2\varphi(m)\),发现递推条件相差为\(\varphi(m)\)\(c\geq 2\varphi(m)\)\(c\geq \varphi(m)\)少减一次\(\varphi(m)\)。所以只需把这一次\(\varphi(m)\)加回来就好了,即\(f(c)=f((c\bmod \varphi(m))+\varphi(m))\),也就是
\[ a^c\equiv a^{(c \bmod \varphi(m))+\varphi(m)} \pmod m \]

用途

再也不用担心指数爆炸了!!指数也可以取模了

题目

BZOJ3884(推公式)

BZOJ4869(+线段树)


参考CSDN博主「CaptainHarryChen」的证明思路。十分感谢。

原文链接:https://blog.csdn.net/can919/article/details/82318115

欧拉定理及扩展(附超易懂证明)

原文:https://www.cnblogs.com/1024th/p/11349355.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!