同余式逆元费马小定理

同余式

若 $a$,$b$ 模$m$的余数相同，则称a,b 模$m$同余

记作 $a\equiv b(mod\ m)$

逆元

若$a$,$b$互质 , $(a,b) = 1$ 且满足同余方程 $ax\equiv1(mod\ b)$

则称 $x$ 为 $a$ 模$b$的逆元记 $a^{-1}$,$x$ 可能有多个解

注意这个-1并不是普通意义上的倒数

逆元解决的问题之一就是因为有时候数太大所以题会对结果取余

而在不像加乘运算$ (a+b)\%p = (a\%p+b\%p)\%p$

实际上$\frac{a}{b} \%p\ \ne \frac{a\%p}{b\%p} \%p$

那么换个想法如果能找到一个乘数转化为 $\frac{a}{b}\equiv a\times x^{-1} (mod \ p)$

就可以使用乘法的取余运算

费马小定理

若$p$为质数 , 且 $a$,$p$互质 $a^{p-1} \equiv 1(mod\ p)$

另一形式对于任意整数 $a$ 有 $a^{p} \equiv a(mod\ p)$

证明

构造$A = {1,2,3,\cdots,p-1}$

假设 $ \prod_{i=1}^{p-1} a \times A_{i} \equiv \prod_{i=1}^{p-1}A_{i} (mod \ p) $

每个$a \times A_{i} (mod \ p)$的余数必然是独一无二的

且 $a \times A_{i} (mod \ p) \lt p$

则必与$A_{i}(mod p) $ 的余数集合相同，得证

假设$aA_{i}(mod \ p)$ 与 $aA_{j}(mod \ p)$ 余数相同都为 $r$

则 $aA_i = xp + r$ , $aA_j = yp + r$

既 $a(A_{i} - A_{J}) = (x-y)p$

∵(a,p) = 1 , 显然等式不成立

提取$a$ 证毕

$a^{p-1} \times \prod_{i=1}^{p-1}A_{i} \equiv \prod_{i=1}^{p-1}A_{i} (mod \ p) $

由同余除法性质固 $a^{p-1} \equiv 1 (mod \ p)$

作业

给定两个数 $a,p$ , $p$ 为质数求$a$ 模 $p$的逆元

显然 $a^{p-1} \equiv 1 (mod \ p)$ , 则 $a \times a^{n-2} \equiv 1 (mod \ p)$

∴ $a^{n-2}$就是逆元用快速幂即可, 注意不要忽略 (a,p) = 1的细节

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int qp(int a,int b,int p){
  int ans = 1;
  while(b){
    if(b&1) ans = ans*a%p;
    a = a*a%p;//倍增
    b>>=1;
  }
  return ans;
}
int main(){
  int a , p;
  cin>>a>>p;
  if(a % p)
    printf("%d\n",qp(a,p-2,p));
}

练习题

参考 via

oiwiki

Rising_Date