黄博士网: 在线数学手册计算器软件,电化学虚拟实验室,虚拟电化学工作站,电化学软件 关于 | 科学 | 数学 | 手册 | 软件 | 计算器 | 电化学 | 虚拟实验室 | 帮助 | 论坛 | 联系 | English

孙子定理

孙子定理

外国书刊中称孙子定理为中国剩余定理。我国古代在《孙子算经》“物不知其数”一问中对此类问题的解法已作叙述。

若\( \left( {m_i ,m_j } \right) = 1,i \ne j \),则同余方程组\[ x \equiv a_i \left( {\bmod m_i } \right),i \le i \le n \] 有唯一解,\( \left( {\bmod m_1 m_2 \cdots m_n } \right) \) 同余方程组的解法如下:

因为\( \left( {m_i ,m_j } \right) = 1 \),所以可由辗转相除法求出\( z_i ,\omega _i \),满足 \[ z_i \prod\limits_{j \ne i} {m_j - \omega _i m_i = 1\left( {1 \le i \le n} \right)} \] 记 \( y_i = z_i \prod\limits_{j \ne i} {m_j } \left( {1 \le i \le n} \right) \) 于是\[ \left\{ \begin{array}{l} y_i \equiv 0\left( {\bmod m_j ,j \ne i} \right) \\ y_i \equiv 1\left( {\bmod m_i } \right) \\ \end{array} \right. \] 最后计算 \[ x = \sum\limits_{i = 1}^n {a_i y_i } \] 它就是同余方程组的唯一解\[ \left( {\bmod m_1 m_2 \cdots m_n } \right) \] .




参阅


Copyright 2000-2017 DrHuang.com