求解模线性方程

  模和同余

定义：设a，b和m均为整数，且m>0。如果a和b被m除所得的余数相同，那么称a和b关于模m是同余的，记作aº b mod n；

同于有以下性质：

1．         若n|(a-b),则aº b mod n。

2．         若a mod nºb mod n，则aºb mod n。

3．         aºa mod n。

4．         若aºb mod n，则bºa mod n。

5．         若 aºb mod n，bºc mod n，则aºc mod n。

6．         若aºb mod c，cºd mod n，则a+cºb+d mod n.

一般的，定义zn为小于n的所有非负整数集合，即Zn=｛0,1，……，n-1｝，称Zn为模n的同余类集合。Zn中的加法和乘法都为模n运算，具有如下性质：

1.     交换率 (w+x)mod n º (x+w)mod n

 (w*x)mod nº (x*w)mod n

2.     结合律  [(w+x)+y]mod nº [w+(x+y)]mod n

  [(w*x)*y]mod nº [w*(x*y)]mod n

3.     分配率  [w*(x+y)]mod nº [(w*x)+(w*y)]mod n

4.     单位元  (0+w)mod nºw mod n

 (1*w)mod nºw mod n

5.     加法逆元: 对w属于Zn，存在x属于Zn，使得w+x=0 mod n，称x为w的加法逆元，记作x=-w。

6.     乘法逆元 : 设w属于Zn，如果存在x属于Zn，使得w*x=1modn，就说w是可逆的，称x为w的乘法逆元，记作x=w；

并不是每个元素都又乘法逆元，可以证明，w属于Zn是可逆的，当且仅当gcd（w，n）=1.如果w是可逆的，则可顶一除法。

 

费马小定理：设a，p为整数，且p为素数,p（p,a）=1,

那么：a^(p-1) º1(mod p).

    例：当a分别为3与5时，求a^16被17除后所得的余数。

答案：均为1.

 

模线性方程      

                                  axºb(mod m)

 

      其中a,b和m是已知的（m>0），要求解出满足上式的对模m的x值。满足同余方程的x可能有多个，也可能一个都没有，上述模线性方程也称为一次同余方程。

     例如：57xº7（mod 11）有一个解x=9，而9xº7（mod 6）无解。

     解：模线性方程axºb（mod ）的步骤如下：

（1） 求 d=gcd（a,m）

（2） 若d不是b的因数，则axºb(mod m)无解，结束；否则转（3）

（3） 求x0,y0,是a*x0+m*y0=d;

（4） 由于d是b的因数，将a*x0+m*y0=d改写，得a(x0*(b/d))+m*(y0*(b/d))=b, 

      于是ax+my=b的一个特解为x=x0*(b/d),y=y0*(b/d);

（5） x0*(b/d)是axº（mod m）的一个特解，由此的axºb(mod m)的所有解

    （共d个）为：x= (x0*(b/d)+ i*(m/d) ) (mod m),    i=0,1,2,3,4.……d-1

定理1：

      设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b，则方程ax=b(modn)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod(n/d)，最大整数解x2=x1+(d-1)*(n/d)。
定理2：

       假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。

long long exgcd(long long a, long long b, long long &x,long long &y)

{

    if (b == 0)

    {

        x = 1, y = 0;

        return a;

    }

    long long re = exgcd(b, a % b, x ,y);

    long long tmp = x;

    x = y;

    y = tmp - a / b * y;

    return re;

}

long long modular_linear(long long a,long long b,long long n)

{

    long long x,y;

    long long d = exgcd(a,n,x,y);

    if (b % d)

    {

        return -1;

    }

    long long re = x*(b/d) %n + n;

    re = re%(n /d);

    return re;

}

 

用扩展欧几里德解模线性方程ax=b mod n

bool modularLinearEquation(int a,int b,int n)

{

  int x,y,x0,i;

  int d=extend_gcd(a,n,x,y);

  if(b%d)

  return false;

  x0=x*(b/d)%n;

  for(i=1;i<d;i++)

  {

  printf("%d\n",(x0+i*(n/d))%n);

  }

  return true;

}