若 t = 1 , a ^ ( p - 2 ) 为 a 在取模 p 意义下的乘法逆元
通常用 inv 表示
证明:
b * a =(三等)1(mod p)
a ^ ( p - 2 ) * a =(三等)1(mod p)
把两个阶乘拆开,发现组合数只与 n!、(n!)^ ( p - 2 ) 有关
证明:
d=gcd(a,b) a=xd b=yd a-b=(x-y)d
gcd(b,a-b)
假设存在t>1 , t|y , t|x-y , 推出t|x , t|y , 推出t|a , t|b , gcd(a,b) = td , 与题目描述矛盾