同余问题*

(1) 同余式

求同余式 ax≡b (mod m)的解。

1. 有解的充要条件是：存在一个整数 n，使得 ax－mn＝b。

2. 求解过程：只需把它转化为 ax－mn＝b。于是，x 和 n 就可以用exgcd求出来了。

3. 若gcd(a,m)=d, b%d==0，则同余式 ax≡b (mod m)恰有 d 个解。  

(2) 同余式组

ìx≡b1 (mod m1)，求 x。

① 已知íîx≡b2 (mod m2)

1. 有解的充要条件是：(b1-b2)%gcd(m1,m2)==0

2. 求解过程：设p，q为两个整数，则

ìx≡b1 (mod m1)        ìx－pm1＝b1……① íîx≡b2 (mod m2) ó íîx－qm2＝b2……②

②－①，得 pm1－qm2＝b2－b1 利用exgcd求出 p，q，则 x＝b1＋pm1＝b2＋qm2

3. 通解：x 对模lcm(m1, m2)有唯一解，可据此构造通解。

x≡b1 (mod m1)

ì

íx≡b2 (mod m2)，求 x。

② 已知 …

îx≡bn (mod mn)

1. 求解过程：可以先解ìîíxx≡≡bb12  ((mod mod mm12))，然后构造出一个新的同余式 x≡b2'(mod lcm(m1,m2))。

接下来将其与第三个式子联立……

2. 中间有一步出现无解，则同余式组无解。

否则 x 对模lcm(m1, m2, …, mn)有唯一解，可据此构造通解。