1同余概述

1.1基本定义和定理

给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)，并称该式子为同余式。
整数的集合被分为m个不同的集合，这些集合被称为模m剩余类（同余类）。每个同余类中的任意两个整数都是模m同余的。
a≡b(mod m)，当且仅当m|(a-b)。
a≡b(mod m)，当且仅当存在任意整数k，使得a=b+km。
费马小定理：若p是质数，则对于任意整数a，有a^p ≡a(mod p)。
欧拉定理：若正整数a，n互质，则，φ(n)为欧拉函数。

1.2同余的性质

对于整数a，b，c和自然数m，n，对模m同余满足：
性质1：a≡a（mod m），（自反性）。
性质2：若a≡b（mod m），那么b≡a（mod m），（对称性）。
性质3：若a≡b（mod m），b≡c（mod m），那么a≡c（mod m），（传递性）。
性质4：若a≡b（mod m），c≡d（mod m），那么a±c≡b±d（mod m），（可加减性）。
性质5：若a≡b（mod m），c≡d（mod m），那么ac≡bd（mod m）（可乘性）。
性质6：若a≡b（mod m），那么an≡bn（mod m），（其中n为自然数）。
性质7：若a mod p=x，a mod q=x，其中p，q互质，则a mod (pq)=x。

2扩展欧几里得算法

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。
定理1:设a和b不全为0，则存在整数x和y，使得ax+by=gcd(a，b)。

void Exgcd(int a,int b,int &d,int &x,int &y)
//求解ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b) 
{
    int t;
    if(b==0){//若b=0m,则最大公约数为a,a=1*a+0*0 
        d=a;
        x=1;
        y=0;
    }
    else {
        Exgcd(b,a%b,d,x,y);
        t=x;x=y;y=t-(a/b)*y;
    }
}

定理2:对于不定方程ax+by=x，当且当且仅当gcd(a,b) | c时，方程有整数解。

3线性同余方程

1.给定整数a，b，m，求一个整数x满足a*x≡b（mod m），或者给出无解。因为未知数的指数为1，所以我们称之为一次同余方程，也称线性同余方程。
2.a，b，m是整数且m>0，gcd(a，m)=d，如果d | b，则方程有d个模m不同余的解，否则方程无解。
方程的解：假设x0为方程ax≡b(mod m) 的任意一个解，则该方程对模m恰有d个不同的解，分别为:xi = x0 + I * (m/d) (0<=i<=d-1)。
3.若gcd(a,m)=1，则称ax≡1(mod m)的一个解为a模m的逆。
求解ax≡b(mod m)线性同余方程的核心代码

#include<iostream>
using namespace std;
typedef long long LL;
LL x,y,m,n,L;
void Exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b){
        x!=1;y=0;d=a;
    }
    else {
        Exgcd(b,a%b,d,x,y);
        int t=x,x=y,y=t-a/b*y;
    }
}
int main()
{
    LL a,b,d,x,y;
    scanf("%lld%lld",&a,&b);
    Exgcd(a,b,d,x,y);
    printf("%lld\n",(x%b+b)%b);
    return 0;
}

4 乘法逆元

若整数b，q互质，并且b | a，则存在一个整数x，使得a/b≡ax(mod p)。称x为b的模p乘法逆元，记为b^-1(mod p)。
因为a/b≡a(b^-1)≡a/bb(b^-1)(mod p)，所以b(b^-1)≡1(mod p)。
如果p是质数，并且b<p，根据费马小定理，b^(p-1)≡1(mod p)，即b(b^(p-2))≡1(mod p)。因此，当模数p为质数时，b^(p-2)即为b的乘法逆元。
如果只是保证b，p互质，那么乘法逆元可通过求解同余方程bx≡1(mod p)得到。

5中国剩余定理

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组有解，并且通解可以用如下方式构造得到：设是整数m1,m2, ... ,mn的乘积，并设是除了mi以外的n- 1个整数的乘积。设为模的数论倒数( 为模意义下的逆元) 方程组的通解形式为在模的意义下，方程组只有一个解：

6高次同余方程

问题：给定整数a，b，p，其中a，p互质，求一个非负整数x，使得a^x≡b(mod p)。
分析：该问题利用BSGS(baby step giant step)算法求解。
因为a，p互质，所以可以在模p意义下执行关于a的乘、除法运算。
设x=im – j，其中m=[sqrt(p)]（向下取整），0<=j<=m-1，则方程变为a^(i*m - j)≡b(mod p)。即(a^m)^i≡b(a^j)(mod p)。
对于所有的j∈[0，m - 1]，把b*(a^j) mod p插入一个Hash表。
枚举i的所有可能取值，即i∈[0，m]，计算出((a^m)^i) mod p，在Hash表中查找是否存在对应的j，更新结果即可。时间复杂度为O(sqrt(p))。
下面为利用BSGS求解同余方程(a^x)≡b mod p的最小非正整数解，无解时输出-1的核心代码：

typedef long long ll;
void Exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(!b){
        x=1;d=a;y=0;
    }
    else {
        Exgcd(b,a%b,d,y,x);
        y-=a/b*x;
    }
}
map<int,int>mp;
void BSGS(int a,int b,int p)
{
    a%=p;
    mp.clear();
    ll m=ceil(sqrt(p)),tmp=1;
    mp[l]=m+1;
    for(ll i=1;i<m;i++)
    {
        tmp=tmp*a%p;
        if(!mp[tmp])mp[tmp]=i;
    }
    tmp=tmp*a%p;
    ll d=1,gcd,x,y;
    for(ll i=0;i<m;i++)
    {
        Exgcd(d,p,gcd,x,y);
        x=(b/gcd*x%p+p)%(p/gcd);
        i=mp[x];
        if(j)
        {
            if(j==m+1)j=0;
            printf("%lld\n",i*m+j);
            return ;
        }
        d=d*tmp%p;
    }
    printf("-1\n");
}

同余问题