查看“︁线性同余方程”︁的源代码

在[[数论]]中，'''线性同余方程'''是最基本的同余方程，“线性”表示方程的[[未知数]]次数是一次，即形如：
:<math>ax \equiv b \ \pmod{n} \ \ \ \ (1)</math>

的方程。此方程有解[[当且仅当]]<math>b</math>能够被<math>a</math>与<math>n</math>的[[最大公约数]][[整除]]（记作<math>\gcd(a,n)|b</math>）。这时，如果<math>x_0</math>是方程的一个解，那么所有的解可以表示为：
:<math>\{x_0+k\frac{n}{d}\mid k\in\mathbb{Z}\}.</math>

其中<math>d</math>是<math>a</math>与<math>n</math>的[[最大公约数]]。在模<math>n</math>的[[完全剩余系]]<math>\{0,1,\ldots,n-1\}</math>中，恰有<math>d</math>个解。

== 例子 ==

* 在方程
:<math>3x \equiv 2 \pmod{6}</math>
中，<math>d = \gcd(3,6) = 3</math> ，3 不整除 2，因此方程无解。 
* 在方程
:<math>5x \equiv 2 \pmod{6}</math>
中， <math>d = \gcd(5,6) = 1</math>，1 整除 2，因此方程在<math>\{0,1,2,3,4,5\}</math>中恰有一个解：<math>x=4</math>。
* 在方程
:<math>4x \equiv 2 \pmod{6}</math>
中， <math>d = \gcd(4,6) = 2</math>，2 整除 2，因此方程在<math>\{0,1,2,3,4,5\}</math>中恰有两个解：<math>x=2</math>以及<math>x=5</math>。

== 求特殊解 ==

对于线性同余方程
:<math>ax \equiv b \pmod{n}</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''(1)'''
若<math>d = \gcd(a, n)</math>整除<math>b</math> ，那么<math>{b \over d}</math>为整数。由[[裴蜀定理]]，存在整数对<math>(r,s)</math>（可用[[辗转相除法#扩展欧几里得算法|扩展欧几里得算法]]求得）使得<math>ar+sn=d</math>，因此 <math>x={rb \over d}</math>是方程 (1) 的一个解。其他的解都关于<math>{n \over d}</math>与<math>x</math>同余。

举例来说，方程
:<math>12x \equiv 20 \pmod{28} </math>
中 <math>d = \gcd(12,28) = 4</math> 。注意到 <math>4 = 12 \times (-2)+28 \times 1</math>，因此 <math>x \equiv 5 \times (-2) \equiv -10 \equiv 4 \ \pmod{7}</math>是一个解。对模 28 来说，所有的解就是 <math>\{4,11,18,25\}</math> 。

== 与线性[[丟番圖方程|丢番图方程]]的关系 ==
考虑<math>ax\equiv{b}\pmod{n}</math>，其等价于<math>ax=b+yn</math>（<math>y</math>是整数），也就是线性丢番图方程。运用辗转相除法可以求得该方程的解，有无限多个；但是在原同余方程中，解的个数受到<math>\gcd(a,n)</math>限制，因此正如上面例子所示，只能选取前面的几个解。

== 线性同余方程组 ==

线性同余方程组的求解可以分解为求若干个线性同余方程。比如，对于线性同余方程组：
:<math>2x \equiv 2 \pmod{6}</math>
:<math>3x \equiv 2 \pmod{7}</math>
:<math>2x \equiv 4 \pmod{8}</math>

首先求解第一个方程，得到<math>x \equiv 1 \pmod{3}</math>，于是令<math>x = 3k + 1</math>，第二个方程就变为：
:<math>9k\equiv -1 \pmod{7}</math>

解得<math>k\equiv 3 \pmod{7}</math>。于是，再令<math>k = 7l + 3</math>，第三个方程就可以化为：
:<math>42l\equiv -16\pmod{8}</math>

解出：<math>l\equiv 0\pmod{4}</math>，即 <math>l=4m</math>。代入原来的表达式就有 <math>x = 21(4m) + 10 = 84m + 10</math>，即解为：
:<math>x\equiv 10\pmod{84}</math>

对于一般情况下是否有解，以及解得情况，则需用到数论中的[[中国剩余定理]]。

== 参见 ==

* [[同余方程]]
* [[二次剩余]]
* [[中国剩余定理]]
* [[線性同餘方法]]

[[Category:同余]]
[[Category:方程]]