费马小定理与GCD&LCM

费马小定理与GCD&LCM

若 t = 1 ,  a ^ ( p - 2 ) 为 a 在取模 p 意义下的乘法逆元

通常用 inv 表示

证明:

b * a =(三等)1(mod p)

a ^ ( p - 2 ) * a =(三等)1(mod p)

费马小定理与GCD&LCM

把两个阶乘拆开,发现组合数只与 n!、(n!)^ ( p - 2 ) 有关

费马小定理与GCD&LCM

费马小定理与GCD&LCM

证明:

  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 , 与题目描述矛盾

上一篇:ElasticSearch中profile API的使用


下一篇:markdown绘图插件----mermaid简介