除法取模与逆元

2019-04-13 12:38发布

逆元:
若,b*b1 % c == 1
则,b1称为b模c的乘法逆元。

在ACM中,许多除法取模都要用到求逆元。
但是,逆元,为什么能给我们带来 ( a/b ) % c == ( a*b1 ) % c ???
(当然a/b要整除) 要知道,取模等式等价变形中,是没有除法的!!! 而推导式,还是没有用除法的地方!!!

我们用反证法证明:

若b*b1 % c == 1,则( a/b ) % c != ( a*b1 ) % c
若我们证明这一命题是错误的,我们目的就达到了。

令,a/b   == k1*c+y1
       a*b1 == k2*c+y2
原来的证明则变成了:若b*b1 % c == 1,则 y1!=y2


两式相减,有 a/b-a*b1 == (k1-k2)*c + (y1-y2)
设 k == k1-k2
     y == y1-y2
有,a/b-a*b1 == k*c + y
左右乘以b,有 a*(1-b*b1) == k*b*c + b*y
左右模上c,
左边 == a*(1-b*b1)%c
        == ( a*( 1%c - b*b1%c ) )%c
        == 0
右边 == (k*b*c + b*y)%c
        == b*y%c
因为a/b为整除,b显然不会是0,那么y必须是0,这与命题矛盾,证毕

p.s. 因为是自己证的,万一有错误,还望大牛指出。


为什么求逆元会用扩展欧几里得?

我们的目标,其实是解b*b1 % c == 1
令 b*b1 == k*c + 1
即 -k*c + b*b1 == 1
仔细观察,这个不就是扩展欧几里得嘛。

那么,为什么gcd(b,c)==1,才会有逆元变得简单了。
因为 1 % gcd(b,c) == 0 ,扩展欧几里得才有解,具体来说,gcd(b,c)只能为1