欧拉定理： 

 

证明： 

由欧拉函数的定义，有 个不同的数字与n互质，设为







又



若



矛盾



有个不同的与n互质的元素

S也有个不同的与n互质的元素



即与S中的元素一一对应





 

费马小定理：若p是素数，则对于任意整数a来说都有（以下这四个都是，可根据等式的性质互相转化）

1.

2.

3.

4.

欧拉定理：若正整数a与p互质，则有 


因为对于素数X来说，=X-1 所以不难发现，费马小定理是欧拉定理中p为素数的特殊情况。因此我们只需要证明出欧拉定理，费马小定理自然就可得证。




扩展欧拉定理：若正整数a，n互质，则对于任意正整数b，有


证明如下：

设b=q*+r，r=b mod 



证毕

 

    
欧拉定理证明：https://www.cnblogs.com/wangxiaodai/p/9758242.html

阶乘的逆元：
记    f[i] = i! mod p,
　　g[i] = (i!)−1 mod p 
容易发现 g[i] = g[i]+1∗(i +1)
　　　　  i−1 = f[i]−1∗g[i]
只需要算出 f[n]，然后求出 f[n] 的逆元 g[n]，然后递推即可。 


转载于:https://www.cnblogs.com/minun/p/11367417.html

　改成全角就能行首空两格了… 

　发现这玩意儿没有欧拉定理那么好证啊… 欧拉定理消去律做一下推推即可. 

　从丁学长那里学会了之后写一下证明. 论有一个善良的学长的重要性！！ 

　终于会用makdown写数学公式了~



扩展欧拉定理

 $$a^q 　\equiv　 a^{q　mod 　\varphi (m) 　+ 　\varphi(m)} (mod　ｍ)(a 与 m不一定互质)$$ 




证明

 $$a = {p_1}^{r_1} * {p_2}^{r_2} * {p_3}^{r_3}...$$  

 $$要证明扩展欧拉定理则只需证a的任意一个质因子p_i　 {p_i}^q 　\equiv　{p_i}^{q 　mod 　\varphi (m)　＋　\varphi (m) }(mod　m)$$  

简单解释一下这是如何转化的. 

 $${p_i}^q 　\equiv　{p_i}^{q 　mod 　\varphi (m)　＋　\varphi (m) }(mod　m)$$  

 $$根据同余式可乘可推出 ({p_i}^q)^{r_i} 　\equiv　({p_i}^{q 　mod 　\varphi (m)　＋　\varphi (m) })^{r_i}(mod　m)$$  

 $$即 ({p_i}^{r_i})^q 　\equiv　({p_i}^{r_i})^{q 　mod 　\varphi (m)　＋　\varphi (m)}(mod　m), 根据同余式可乘得到$$  

 $$({p_1}^{r_1} *{p_2}^{r_2} * {p_3}^{r_3}...)^q　\equiv　({p_1}^{r_1} * {p_2}^{r_2} * {p_3}^{r_3}...)^{q 　mod 　\varphi (m)　＋　\varphi (m)}(mod　m)$$  

 $$可以发现这就是a^q　\equiv　a^{q 　mod 　\varphi (m)　＋　\varphi (m)}(mod　m)$$  

那么现在要证明的东西已经转化， 考虑如何证得. 

 $$p为a某质因子， 若p\not\mid m则欧拉定理显然证得， 考虑p\mid m.$$  

 $$m = p^r * s, 则p^{\varphi (s)} \equiv 1 (mod　s) (因为 s和p互质， 由欧拉定理可得)$$  

 $$由\varphi (m) = \varphi (p^r) * \varphi (s)可得(积性函数)， \varphi (s) \mid \varphi (m)$$  

 $$所以　p^{\varphi (m)} \equiv 1 (mod　s)$$  

 $$从而　p^q \equiv p ^ {q 　mod　\varphi(m)} (mod　s)，　显然式子同时乘以q^r可以得到$$  

 $$=>　p^{q　+　 r} \equiv p ^ {q 　mod　\varphi(m)　+　r} (mod　m)(因为m = s * q^r)$$  

 $$显然r <= \varphi(m), 所以两边同时乘以p^{\varphi(m) 　-　r}可以得到上面转化出来要求的式子$$  

 $$p^q 　\equiv　p^{q 　mod 　\varphi (m)　＋　\varphi (m) }(mod　m)$$  

 $$证毕$$