Please enable JavaScript.
Coggle requires JavaScript to display documents.
第二章 同余 - Coggle Diagram
第二章 同余
一次同余式
设𝑚为正整数，同余式𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑 𝑚)有解的充要件是(𝑎，𝑚)|𝑏。在有解的情况下，解数为(𝑎，𝑚)，且若𝑥 = 𝑥0是同余式的一个特解，那么同余式的所有解可以表示为
𝑥 ≡ 𝑥0 +(m / (a,m) ) *t (mod m), t=0,1,2,...,(a,m) -1
-
-
-
-
-
同余式组的解法
同余式的解数
设𝑚1，𝑚2， ⋯ ，𝑚𝑠为两两互素的正整数，若对于1 ≤ 𝑖 ≤
𝑠，同余式𝑓𝑖(𝑥) ≡ 0(𝑚𝑜𝑑 𝑚𝑖)有𝐶𝑖个解，那么，同余式组
𝑓1(𝑥) ≡ 0(𝑚𝑜𝑑 𝑚1)
𝑓2(𝑥) ≡ 0(𝑚𝑜𝑑 𝑚2)
...
𝑓𝑠(𝑥) ≡ 0(𝑚𝑜𝑑 𝑚𝑠)
关于模𝑀 = 𝑚1𝑚2 ⋯ 𝑚𝑠有𝐶1𝐶2 ⋯ 𝐶𝑠个解
模同一素数的幂
设 𝑝 为素数 ，𝑖1 ≥ 𝑖2 ≥ ⋯ ≥ 𝑖𝑠，𝑏1，𝑏2， ⋯ ，𝑏𝑠 为任意整数，同余式组
𝑥 ≡ 𝑏1(𝑚𝑜𝑑 𝑝^𝑖1)
𝑥 ≡ 𝑏2(𝑚𝑜𝑑 𝑝^𝑖2)
...
𝑥 ≡ 𝑏𝑠(𝑚𝑜𝑑 𝑝^𝑖𝑠)
有解的充要条件是
𝑏1 ≡ 𝑏2(𝑚𝑜𝑑 𝑝^𝑖2)
𝑏1 ≡ 𝑏3(𝑚𝑜𝑑 𝑝^𝑖3)
...
𝑏1 ≡ 𝑏𝑠(𝑚𝑜𝑑 𝑝^𝑖𝑠)
如果有解，其解为𝑥 ≡ 𝑏1(𝑚𝑜𝑑 𝑝^𝑖1)
一般同余式求解
对于合数m,求同余式𝑓(𝑥) ≡ 0(𝑚𝑜𝑑 𝑚)的解等价于求同余式组
f(x) ≡ 0 (mod p1^ a1)
f(x) ≡ 0 (mod p2^ a2)
...
f(x) ≡ 0 (mod ps^ as)的解
-
高斯函数
剩余系的遍历
-
设𝑚，𝑛为正整数，(𝑚，𝑛) = 1，则当𝑥遍历模𝑛的一个完全剩余系，𝑦遍历模𝑚的一个完全剩余系时，𝑚𝑥 + 𝑛𝑦遍历模𝑚𝑛的一个完全剩余系；
当𝑥遍历模𝑛的一个简化剩余系，𝑦遍历模𝑚的一个简化剩余系
时，𝑚𝑥 + 𝑛𝑦遍历模𝑚𝑛的一个简化剩余系。
-
模为素数幂的高次同余式
-
设𝑝为素数，若𝑥 ≡ 𝑥1(𝑚𝑜𝑑 𝑝)是同余式𝑓(𝑥) ≡ 0(𝑚𝑜𝑑 𝑝)的一个解，且满足(f'(x1), p) = 1，那么对于任意正整数𝑘 > 1，𝑓(𝑥) ≡ 0(𝑚𝑜𝑑𝑝^𝑘)的满足𝑥 ≡ 𝑥1(𝑚𝑜𝑑 𝑝)的解𝑥𝑘可通过如下递推公式得到
𝑥(𝑖) ≡ 𝑥(𝑖−1) − f(x(i-1))*((f'(x1))^(-1)(mod p)) (mod p^i), i=2,3,...,k
中国剩余定理
设𝑚1，𝑚2， ⋯ ，𝑚𝑠为两两互素的正整数，𝑏1，𝑏2，⋯ ，𝑏𝑠为任意整数，那么同余式组
𝑥 ≡ 𝑏1(𝑚𝑜𝑑 𝑚1)
𝑥 ≡ 𝑏2(𝑚𝑜𝑑 𝑚2)
...
𝑥 ≡ 𝑏𝑠(𝑚𝑜𝑑 𝑚𝑠)
模𝑀 = 𝑚1𝑚2 ⋯ 𝑚𝑠有唯一解
𝑥 ≡ Σ(s)(i=1) b(i) (M/mi) (M/mi)^-1 (mod mi) (mod M)