【定理证明】：通俗易懂的费马小定理和欧拉定理证明（以及扩展欧拉定理）

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

1.a^{p}\equiv a (mod\ p)

2.a^{p}-a\equiv 0(mod \ p)

3.a^{p-1}-1\equiv 0(mod \ p)

4.a^{p-1}\equiv 1(mod \ p)

欧拉定理：若正整数a与p互质，则有 x^{\varphi (b)}\equiv 1(mod\ b)

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

扩展欧拉定理：若正整数a，n互质，则对于任意正整数b，有a^{b}\equiv a^{b \ mod \ \varphi (n)}

证明如下：

设b=q*\varphi (n)+r，r=b mod\varphi (n)

a^{b}\equiv a^{q*\varphi (n)+r}\equiv (a^{\varphi(n)})^{q}*a^{r}\equiv 1^{q}*a^{r}\equiv a^{r}\equiv a^{b \ mod \ \varphi(n)} (mod \ n)

证毕

 

版权声明：本文为weixin_44603753原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。