浅谈扩展欧拉定理

## 浅谈扩展欧拉定理### 前置知识：$1,$数论欧拉定理[这里](https://www.cnblogs.com/wangxiaodai/p/9758242.html)$2,$积性函数$\phi$的性质$3,$以下引理### 证明引理用到的引理(一)，**引理**​设$x$=$lcm(a,b)$。​可以分解如下$$a=p_1^{a_1}*……*p_k^{a_k}\\b=p_1^{b_1}*……*p_k^{b_k}$$那么可得：$$x=p_1^{max(a_1,b_1)}*……*p_k^{max(a_k,b_k)}$$**证明**：推倒上面的式子，将指数可加解释到整体的乘除法，同理取max也是一样。​或者手推几个数。## 引理#### (一)，已知$$\begin{cases}x\equiv y(mod　m_1)\\x\equiv y(mod　m_2)\end{cases}$$​可得：$$x\equiv y(mod　lcm(m1,m2))$$#### 引理一证明：可以对$x,m1,m2$进行分解：$$\begin{cases}x= p_1^{a_1}*……*p_k^{a_k}\\m1=p_1^{b_1}*……*p_k^{b_k}\\m2=p_1^{c_1}*……*p_k^{c_k}\end{cases}$$又因为：$$\begin{cases}x％m_1=p_1^{a_1％b_1}*……*p_k^{a_k％b_k}=y\\x％m_2=p_1^{a_1％c_1}*……*p_k^{a_k％c_k}=y\end{cases}$$那么对于$y$可以有唯一分解定理解得：$$a_i％b_i=a_i％c_i$$稍加分析就可以得到：$$x％lcm(m1,m2)=p_1^{a_1％max(b_1,c_1)}*……*p_k^{a_k％max(b_k,c_k)}=y$$即证得：$$x\equiv y(mod　lcm(m1,m2))$$#### (二)，在p是质数的前提下$$\phi(p^q)=p^q-p^{q-1}\geq q$$引理二的证明也是非常的妙妙啊。### 引理二证明小于等于$p^q$的正整数一共有$p^q-1$个，其中不与$p^q$互质的是$p,p*2,p*3,p^q-p=(p^{q-1}-1)*p$这$p^{q-1}-1$个数。那么就可以得到$\phi(p^q)=p^q-p^{q-1}$妙妙**另外在正式证明之前还要提一句$\phi$的性质：**在n和m互质的前提下，存在$$\phi(n*m)=\phi(n)*\phi(m)$$### 正式证明​首先先来回顾一下我们要证得是什么？​欧拉定理CRT​先把式子放出来：$$a^b \equiv\begin{cases}a^{b％\phi(m)}　　　　(gcd(a,m)==1)\\a^b　　　　　　(gcd(a,m) !=1 ＆b<\phi(m))\\a^{b％\phi(m)+\phi(m)}　(gcd(a,m)!=1＆b\geq\phi(m))\end{cases}(mod 　m)$$​然后很容易发现这三个式子都可以用第三个式子表示，也就是在满足任何数的意义下，存在扩展欧拉定理：$$a^b\equiv a^{b％\phi(m)+\phi(m)}(mod 　m)$$开始愉快地证明吧：​首先我们假设模数$m=p^q$，那么很容易知道$a$和$m$的同余性是可以推至$a$和$p$的，当然反推也可以。​那么就开始最美妙的分情况讨论时间了：​(1)，$gcd(a,p)==1$时，求证：$$a^b \equiv a^{x％\phi(p^q)}(mod 　p^q)$$​这就不证了，很明显的欧拉定理式子。​(2)，$gcd(a,p)!=1$也就是$gcd(a,p)==p$。 因为p是质数啊喂​那么我们另$a=k*p$。​那么就是求证：$$(k*p)^b \equiv (k*p)^{b％\phi(p^q)+\phi(p^q)}(mod 　p^q)$$​因为$b\geq\phi(p^q)$ 根据引理二可以知道$b\geq q$​所以可以得到：$$p^b％p^q=0$$​所以又可以得到：$$a^b=(k*p)^b \equiv 0 (mod 　p^q)$$​又因为$\phi(p^q)\geq q$，所以又可得：$$a^{b％\phi(m)+\phi(m)}\equiv 0 (mod　p^q)$$​那么到了这里，就已经证毕。​即证得：$$a^b \equiv a^{b％\phi(m)+\phi(m)}(mod　p_q)$$ 又因为$\phi$函数的积性，可以将上述结论推至对所有模数m都成立。