线性同余方程

维基百科,自由的百科全书
跳转至: 导航搜索

数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次,即形如:

ax \equiv b \ \pmod{n} \ \ \ \ (1)

的方程。此方程有解当且仅当 b 能够被 an最大公约数整除(记作 gcd(a,n) | b)。这时,如果 x0 是方程的一个解,那么所有的解可以表示为:

\{x_0+k\frac{n}{d}\mid k\in\Bbb{Z}\}.

其中 dan最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中,恰有 d 个解。

例子[编辑]

  • 在方程
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以及x=5。

求特殊解[编辑]

对于线性同余方程

axb (mod n)      (1)

d = gcd(a, n) 整除 b ,那么{b \over d}为整数。由裴蜀定理,存在整数对 (r,s) (可用辗转相除法求得)使得 ar+sn=d,因此 x={rb \over d}是方程 (1) 的一个解。其他的解都关于{n \over d}x 同余。

举例来说,方程

12x ≡ 20 (mod 28)

中 d = gcd(12,28) = 4 。注意到 4 = 12 \times (-2)+28 \times 1,因此 x \equiv 5 \times (-2) \equiv -10 \equiv 4 \ \pmod{7}是一个解。对模 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)

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

参见[编辑]