欧拉定理的推论：

　　若正整数a，n互质，那么对于任意正整数b，有a^b≡a^(b mod φ（n）)（mod n）

证明如下：（类似费马小定理的证明）

　　把目标式做一简单变形：a^(b - b mod φ（n）)* a^(b mod φ（n）)≡ a^(b mod φ（n）)（mod n），所以接下来只需要证明a^(b - b mod φ（n)）≡ 1 （mod n），又因为：

（ b - b mod φ（n））| φ（n），不妨设：（ b - b mod φ（n））= q*φ（n）（q为自然数），则有a^(q*φ（n）)== （a^q）^φ（n），因为a，n互质，那么（a^q）与n也互质，

那么就转换到了欧拉定理：（a^q）^φ（n）≡ 1 （mod n），成立。所以我们这个推论成立。

 b mod φ（n）是求模就是求余数的关系不是乘法，不等于b*φ（n），所以解释一下这一步：设b=q∗φ(n)+r,其中0≤r<φ(n),即r=b mod φ(n).于是：
（ b - b mod φ（n））| φ（n），
所以前面的成立。
这都是简述版，我压缩了，希望您能理解，明白一点过程就好，再深入的讲我也不会。
RSA密码的加解密过程的推导证明我整理一下再讲。

先发一个图片，后面再发令一文章的证明，二者本质一样，后者更全面思路更清晰点儿。

RSA公钥密码解密过程的证明：
也就是证明下面的式子：c^d=m(mod n).
因为根据加密规则：m^e=c(mod n).
于是c可以写成：c=m^e-kn。
将c代入要我们证明的解密规则：
（m^e-kn）^d=m（mod n）。
它等同于求证：m^（ed）=m（mod n）。
由于ed=1（mod  φ（n））
所以  ed=h φ（n）+1.
将ed代入：m^（h φ（n）+1）=m（mod n）。
接下来分两种情况证明上面的式子：
1，m与n互质：
根据欧拉定理，此时m^ φ（n）=1（mod n），
则得到：（m^ φ（n））^h *m=m （mod n）。
原式得证。
2，m与n不互质的情况：（其实我们用的n为素数，不会是这种情况的，m<n则二者互质，当m=n时由于都是素数和前一种情况一样。）
此时，由于n等于素数p和q的乘积，所以m必然等于kp或kq，
以m=kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：
（kp）^（q-1）=1（mod q）。
进一步得到：（（kp）^（q-1））^（h(p-1)） *kp=kp （mod q）
就是（kp）^(ed)=kp （mod q）
将它改写成下面的等式：
（kp）^(ed)=tq+kp
这时t必然能被p整除，即t=t1*p
则（kp）^(ed)=t1*pq+kp
因为m=kp，n=pq，所以：
m^(ed)=m （mod n）
原式得证。（完）

所以，不同于费马小定理的，我们采用n为素数，当 φ（n）不等于n-1时，还原不回去明文m，就可以确定n为合数。

这个是非对称加密，是两个过程，不同于费马小定理，加密是一个过程，用到公钥，解密是又一个过程用到私钥。是唯一的对应关系，不会出现错误。（指密文和公开模数n是唯一的对应关系）

[此贴子已经被作者于2020-3-3 12:21编辑过]

前面的图片中的证明用到了传递性，不容易明白吧，解释一下，所谓的传递性就是没有算到底，没有得出最后的余数，只是一系列的同余式相等，就像不断的累加商值余数仍然大于除数直到最后得到余数，中间一系列的同余式就是传递的过程。
这种方法书写不规范的就不容易明白，使人眼花缭乱的，上面的都是比较清晰的过程，供参考。
谢谢您关注和沟通，感谢您的帮助！

欧拉定理的另一个推论（据说和前面的道理一样），咱不明白无法证明（证明过程应该和前面一样原文都是证明结束说明了一下而已，就是说明当a和n不一定互质时就是这个等式，所以我不明白这个），无法用，用不到，发一下您看看吧：
特别的，如果a，n不互质，且b>φ（n）时，a^b≡a^(b mod φ（n）+ φ（n）)（mod n）。

举个例子，下面就是传递性：
3*5=15=8+7=8=1 （mod 7）.
这个写法规范不？我不知道，好多文章都这样写，规范的应该这样吧，虽然麻烦一点，应该这样我觉得：
15 （mod 7）=8 （mod 7）=1 （mod 7）.
这样才清楚，个人见解，供参考。（我们知道15和8是不相等的，容易使人搞错，使人糊涂。哈哈哈哈，见笑了！）

[此贴子已经被作者于2020-3-3 13:20编辑过]

RSA公钥密码体制是上世纪70年代～80年代好像是，由3个数学家弄出来的，RSA分别是3位数学家的名字的开首字母。
这个原理就是前面证明过程中的衡等式：m^（ed）=m（mod n）。
数学家居然把它拆开成两个等式，两个过程，没有反例，不会出错。

[此贴子已经被作者于2020-3-3 15:43编辑过]

比较这两个公式：a^p≡a（mod p）（费马小定理），m^（ed）=m（mod n）（欧拉原理）(其中ed=1（mod  φ（n）），n为素数也成立)
显然二者不同，不能同日而语。

谢谢你的帮助！一点儿小知识供参考！非常感谢您关注沟通和指导！