线性同余方程

以前好像提及过关于同余问题，这里就不多讲了。。。

现在我要记录的，好像有些些复杂（当然，只是对于我来说）

首先我要提及的是一次同余方程，形如  ax≡b(mod m)

首先我们要对同余方程ax≡b(mod m) 解的情况进行分析（要的解范围要在0到m之间，不知道为啥哈哈哈）

1.当（a,m）=1时有唯一解；（默默的提一句，最大公约数）

2.当（a,m）| b时有解，解的个数是（a,m）个

 3.当（a,m） 不能整除  b时，无解；

概括一下，也就是说，我们首先要求出a与m的最大公约数，如果是b的倍数，那解的个数就是（a，m），如（a,m）不能整除b，那就是无解！！！

（至于为啥是这样的，我能力有限，就不在此讨论了，也许几年后的今天我就可以对此完善了）

那关于同余方程应该怎样求解呢？以下给出两种方法————形式分数求解（如果实在不懂，可从数学选修4-6,37页自行学习）

1.乘式求解

我们换种形式，然后分子、分母同乘以与m互素的正整数n后，在分别对分子、分母%m,使用等式右边变成整数，便得到方程唯一的解。（当然，我们要的解范围要在0到m之间）

 是不是没听懂？？我来给你举个例子：7x≡8(%10)   求解x

变换形式得到x≡8/7≡8*3  /  7*3≡ 24%10/21%10 ≡4/1≡4(mod10)

其中，那个3就是“与m互素的正整数”，这可以是任何数，但是我要满足原分母（7）乘上这个数之后能模 m（就是10）之后余1（余1的目的是最后可以得到整数），所以其实核心就是经过多次变换，把分母变成1，求得解。

 2.加式求解

我们依旧把他换成的形式，在分子上加上m的倍数，使新分子和分母有公约数，再约去它。最终得到的就是解。核心其实也就是让b一直加m，一直加到能让分子能整除分母即可；

3.扩展欧几里得算法（当然，这个原来提及过，这里就不赘述了）

那我总结一下吧（其实是贺的老师的PPT）

1. 一般的线性同余方程为ax≡b(%m)，其中a≠0，b,m均为已知数，x为未知数

2.这类方程解法：先将原方程化为ax+my=b的不定方程，根据b能否整除gcd(a,m)判断方程是否有解，然后再用刚才说的那三种方法求解

3.若”d=(a,m) | b” ,b不能被d整除，则方程ax≡b(%m)无解, 否则在%m的完全剩余系{0,1,2....m-1}中，恰有d个解，第一个解为：

x₀=x' * (b/d) %m,其余d-1个解可以通过对%n加上(m/d)的倍数得到，即xi=(x₀+i*(m/d))%m, (1≤i≤d-1).（拓欧几里得)

代码部分：