模线性方程组（中国剩余定理+通用解法）

2019-04-13 12:21发布生成海报

站内文章 / 模拟电子

13003 0

求解

{\begin{cases} x \equiv a_{1} (m o d m_{1}) \\ x \equiv a_{2} (m o d m_{2}) \\ x \equiv a_{3} (m o d m_{3}) \\ . . . \\ x \equiv a_{n} (m o d m_{n}) \end{cases}

中国剩余定理

若

m_{1}, m_{2}, m_{3}, . . ., m_{n}

两两互质，则可用中国剩余定理设

M = \prod_{i = 1}^{n} m_{i}

，

M_{i} = M / m_{i}

，

t_{i}

为

M_{i}

在

(m o d m_{i})

意义下的逆元，那么通解为

x = k M + \sum_{i = 1}^{n} a_{i} t_{i} M_{i}

解释一下： ~~懒得证~~
因为

t_{i} M_{i} \equiv 1 (m o d m_{i})

，而

M_{j} \equiv 0 (m o d m_{i}) (j \neq i)

，所以整个求和式子中，模

m_{i}

有用的就只剩下

a_{i} t_{i} M_{i} \equiv a_{i} (m o d m_{i})

，对每一个

m_{i}

都如此，满足所有条件。

通用解法

不要求

m_{1}, m_{2}, m_{3},

Ta的文章更多 >>

热门文章