费马小定理求法(只适用于p为质数)
很显然第4个公式是不对的,那么当我们碰到要边除边取模的情况,该怎么处理呢?答案是使用乘法逆元.
就笔者个人理解,我们知道除一个数相当于乘这个数的倒数,那么在模运算的前提下,对于$(b\div a)%p$这个式子,我们也可以按照这个思想找到一个数x来代替b,使得$(b\times x)%p=(b\div a)%p$这样的数x,我们就称之为对于%p时a的逆元,记为x=inv(a,p)
Tips:x的值由a和p共同决定,这点和倒数有点不太一样,即对于一个固定的a,p不同时x的值也不同.
那么,inv(a,p)要怎么去求呢?一般是通过费马小定理或者拓展欧几里德去求.
下面是证明,不敢兴趣的可以直接跳过.
这里涉及到用exgcd解线性同余方程组的方法.
鉴于这是一块新的知识点,所以从头开始介绍了exgcd.