模运算

一些基本规则

加法：

$(a+b)\mod n=(a \mod n+b \mod n)\mod n$

减法：

$(a-b)\mod n=(a \mod n-b \mod n)\mod n$

乘法：

$(a∗b)\mod n=(a \mod n∗b \mod n)\mod n$

幂：

$a^b \mod n=(a \mod n)^b mod \ n$

注意！除法不成立。

那么，如何计算$(a/b)\ mod\ n$?

我们可以通过将除b转换成乘b的逆元来解决，即$(a∗b^{-1} )\mod n$

求$(a/b)\ mod\ m $

逆元定义

对于正整数$a$和$m$，如果有$ax\equiv 1(\ mod\ m)$，那么把这个同余方程中的$x$最小正整数解叫做$a$模$m$的逆元。

逆元的存在性质：当$a$与$m$互素的时候，逆元才存在解，如果不互素则无解（这里说的都是整数解）

求法

逆元一般用扩展欧几里得算法来求得，如果$m$为素数，那么还可以根据费马小定理得到逆元为$a^{m-2}\ mod\ m$。（都要求$a$和$m$互质）

费马小定理求解（m为素数是费马小定理的前置条件）

费马小定理：对于素数 $m$ 任意不是 $m$ 的倍数的 $b$，都有：$b^{m-1}\equiv1\ mod \ m$

于是有$ b* b^{m-2}\equiv1\ mod \ m $

于是有

$a/b=a/b*(b * b ^ {m-2})=a*b ^ {m-2}\ mod\ m$

扩展欧几里得

利用费马小定理只能求出m为素数的情况下的乘法逆元，所以还是需要采用扩展欧几里德算法来计算普遍情况下的乘法逆元的情况。

当 a 与 b 互素时有$ gcd （ a ， b ） = 1 $；

即得： $a*x + b*y = 1$

$a * x ≡ 1 （ mod b ）；$

由于 a 与 b 互素，同余式两边可以同除 a ，得：

$1 * x ≡ 1 / a （mod b）$；

因此 $x$ 是 $a \ mod\ b$ 的逆元；

$a*x + b*y = 1$

求得$x$即为$a\%b$的逆元$(ax\%b \equiv 1)$；$ y$即为$b\%a$的逆元$(by\%a \equiv 1)$。

所以

用扩展欧几里得算法求得一组$x0,y0$和$gcd$;检查$gcd$是否为1
$gcd$不为1说明逆元不存在，若为1,调整$x0$到0~m-1的范围中即可。

//此算法即可求出gcd(a,b)，也可求出x和y。
int ex_gcd(int a,int b,int &x,int &y)       //扩展欧几里得 
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=ex_gcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return r;
}

int mod_reverse(int a,int n)//ax=1(mod n) 求a的逆元x 
{
    int d,x,y;
    d=ex_gcd(a,n,x,y);
    if(d==1)
        return (x%n+n)%n;
    else
        return -1;
}