费马小定理

费马小定理！

设p为素数，p\nmida
a^{p-1}\equiv 1\pmod{p}

用整除的定义就可以得出以下很常用性质：

  1. 如果a\midb,那么a\mid(-b),同理如果a\midb,那么(-a)\midb,另外两种同理可得.
  2. 如果a\midb,b\midc,那么a\midc,说明整除有传递性.
  3. 如果a\midb,a\midc,则任意整数x,y都符合a\midbx+by=1

证明：

设质数p，我们取不为p倍数的数a。
构造一个序列：A={1，2，3\ldots，p-1},这个序列的性质：
\prod_{i=1}^nA_i\equiv\prod_{i=1}^n(A_i\times a)\pmod{p}

证明：
因为\forall_{1 \le i \le p-1}\gcd(A_i,p)=1,\gcd(a,p)=1
所以\forall_{1 \le i \le p-1}\gcd(A_i\times a,p)=1
因为每一个A_i\times a\pmod{p}都是唯一的，可得
\forall_{1 \le i,j \le p-1,i\not = j}A_i \times a \not \equiv A_j \times a \pmod{p}
而且每一个A_i\times a \pmod{p}都对应了一个A_j(1 \le j \le p-1)
把式子稍加整理：
a^{p-1}\times f \equiv f \pmod{p}
两边同时乘\frac{1}{f},得
a^{p-1} \equiv 1 \pmod{p}
证毕。
注：本文一部分摘自OI Wiki

好毒瘤qwq

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容