线性同余方程的特点及求解是什么？

线性同余方程 在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如： 的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。这时，如果 x0 是方程的一个解，那么所有的解可以表示为： 其中d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。 目录 1 例子 2 求特殊解 3 线性同余方程组 4 参见 例子 在方程 3x ≡ 2 (mod 6) 中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程无解。 在方程 5x ≡ 2 (mod 6) 中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。 在方程 4x ≡ 2 (mod 6) 中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2 and x=5。 求特殊解 对于线性同余方程 ax ≡ b (mod n) (1) 若d = gcd(a, n 整除 b ，那么为整数。由裴蜀定理，存在整数对 (r,s) （可用辗转相除法求得）使得 ar+sn=d，因此 是方程 (1) 的一个解。其他的解都关于与 x 同余。 举例来说，方程 12x ≡ 20 (mod 28) 中d = gcd(12,28) = 4 。注意到 ，因此 是一个解。对模 28 来说，所有的解就是 {4,11,18,25} 。 线性同余方程组 线性同余方程组的求解可以分解为求若干个线性同余方程。比如，对于线性同余方程组： 2x ≡ 2 (mod 6) 3x ≡ 2 (mod 7) 2x ≡ 4 (mod 8) 首先求解第一个方程，得到x ≡ 1 (mod 3)，于是令x = 3k + 1，第二个方程就变为： 9k ≡ 1 (mod 7) 解得k ≡ 3 (mod 7)。于是，再令k = 7l + 3，第三个方程就可以化为： 42l ≡ 16 (mod 8) 解出：l ≡ 0 (mod 4)，即 l = 4m。代入原来的表达式就有 x = 21(4m) + 10 = 84m + 10，即解为： x≡ 10 (mod 84) 对于一般情况下是否有解，以及解得情况，则需用到数论中的中国剩余定理。 参见 二次剩余 中国剩余定理 谈谈解线性同余方程 因为ACM/ICPC中有些题目是关于数论的，特别是解线性同余方程，所以有必要准备下这方面的知识。关于这部分知识，我先后翻看过很多资料，包括陈景润的《初等数论》、程序设计竞赛例题解、“黑书”和很多网上资料，个人认为讲的最好最透彻的是《算法导论》中的有关章节，看了之后恍然大悟。经过几天的自学，自己觉得基本掌握了其中的“奥妙”。拿出来写成文章。 那么什么是线性同余方程。对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值。 解题例程：pku1061 青蛙的约会 解题报告 符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理： 对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法，见下面的MLES算法。 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 实现：古老的欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 实现： triple Extended_Euclid(int a,int b) { triple result; if(b == 0) { result.d = a; result.x = 1; result.y = 0; } else { triple ee = Extended_Euclid(b,mod(a,b)); result.d = ee.d; result.x = ee.y; result.y = ee.x - (a/b)*ee.y; } return result; } 附：三元组triple的定义 struct triple { int d,x,y; }; 第三个问题：求解ax≡b(mod n) 实现：由x，y堆砌方程的解 int MLES(int a,int b,int n) { triple ee = Extended_Euclid(a,n); if(mod(b,ee.d) == 0) return mod((ee.x * (b / ee.d)),n / ee.d); else return -1; }//返回-1为无解，否则返回的是方程的最小解 说明：ax≡b(mod n)解的个数： 如果ee.d 整除 b 则有ee.d个解； 如果ee.d 不能整除 b 则无解。

求采纳