相关文章：

模运算规则（加法）

证明： $(a_1 + a_2)\ mod\ b = (a_1\ mod\ b + a_2\ mod\ b)\ mod\ b$

这个好像没啥好证明的。。。

模运算规则（乘法）

证明： $(a_1 \times a_2)\ mod\ b = (a_1\ mod\ b \times a_2\ mod\ b) mod\ b$

设 $a_1 = k_1 b + c_1; a_2 = k_2 b + c_2, 其中\ {k_1, k_2} \in \mathbb{Z}$

代入公式可得，并通过加法规则可知：

\[\begin{align*} \Rightarrow (a_1 \times a_2)\ mod\ b &= (k_1b + c_1) \times (k_2b + c_2)\ mod\ b \\ &= (k_1b \times k_2b + k_1b \times c_2 + c_1 \times k_2b + c_1 \times c_2 )\ mod\ b \\ &= ((k_1b \times k_2b)\ mod\ b + (k_1b \times c_2)\ mod\ b + (c_1 \times k_2b)\ mod\ b + (c_1 \times c_2 )\ mod\ b)\ mod\ b \end{align*} \\\]

其中如果是 $b$ 的倍数，则 $mod b$ 结果为0，包括

\[\begin{align*} \because (k_1b \times k_2b )\ mod\ b &= 0 \\ (k_1b \times c_2)\ mod\ b &= 0 \\ (c_1 \times k_2b)\ mod\ b &= 0 \end{align*}\]

所以，我们能得到如下公式：

\[\begin{align*} \Rightarrow (a_1 \times a_2)\ mod\ b &= (c_1 \times c_2)\ mod\ b, (其中c_1 = a_1\ mod\ b; c_2 = a_2\ mod \ b ) \\ &= ((a_1 \ mod \ b) \times (a_2 \ mod\ b)) mod\ b \end{align*}\]