一些数学知识题

欧几里得算法

费马小定理

当a,p都是是质数时,a^(p-1)=1(mod p)

证明：

举个例子 a=2,p=5;

1,2,3,4 集合（1） {1，2，3，4...,(p-1)}
2,4,6,8 => %5 => 2,4,1,3 集合（2） {1a%p,2a%p,3a%p,4a%p...,(p-1)a%p}

我们发现{1，2，3，4}和{2，4，1，3}只是位置不同，成积相同

怎么个一定乘积相同法？

反证法：

首先（1）一定不会有相同，（2）的证法如下

ai=aj (mod P) => a(i-j)=0 (mod p) => p|a(i-j) 这可能吗？p是质数

证毕

裴属定理

证明：c|ax,c|by，所以c|ax+by,证毕：）

求逆元（老重要了！！！）

• 扩展欧几里得算法

点击查看代码

void Exgcd(ll a, ll b, ll &x, ll &y) {if (!b) x = 1, y = 0;else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {ll x, y;Exgcd (a, p, x, y);x = (x % p + p) % p;printf ("%d\n", x); //x是a在mod p下的逆元
}

• 线性方法

求i的逆元

点击查看代码

inv[1] = 1;
for(int i = 1; i < p; ++ i)inv[i] = (p - p / i) * inv[p % i] % p;//这里有个问题困扰了我很久，为什么（p-p/i)=-(p/i) ? 因为 -(p/i)%p=p-(p/i) 不知道的去查

对与中国剩余定理