证明模运算的分配性

作者: 人类发展观察者 | 来源:发表于2019-06-18 21:50 被阅读0次

一. 证明:

$(x_{1} + x_{2} + ... + x_{n} ) \bmod m =( (x_{1} \bmod m) + (x_{2} \bmod m) + ... + (x_{n} \bmod m)) \bmod m$

任何整数都可以表示为:

$z = m \times k + r, ( m,k,r \in Z_{\geq 0})$ (1)

则:

$r = z \bmod m$ (2)

若 r 等于 0，则 z mod m = 0;

领:

$\begin{align*}x_{1} &= m \times k_{1} + r_{1}\\x_{2} &= m \times k_{2} + r_{2}\\...\\x_{n} &= m \times k_{n} + r_{n}\\\end{align*}$

则:

$\begin{align*}&x_{1} + x_{2} + ... + x_{n} \\&= (m \times k_{1} + r_{1}) +(m \times k_{2} + r_{2}) + ... + (m \times k_{n} + r_{n}) \\&= m \times (k_{1} + k_{2} + ... + k_{n}) + (r_{1} + r_{2} + ... + r_{n}) \\\end{align*}$

根据 (1)、(2), 两边取模 m 得到:

$\begin{align*}&(x_{1} + x_{2} + ... + x_{n}) \bmod m \\&= (r_{1} + r_{2} + ... + r_{n}) \bmod m \\\end{align*}$

由（2）得到:

$\begin{align*}&(x_{1} + x_{2} + ... + x_{n}) \bmod m \\&= ((x_{1} \bmod m) + (x_{2} \bmod m) + ... + (x_{n} \bmod m)) \bmod m \\\end{align*}$

证毕

二. 证明:

$(x_{1} \times x_{2} \times ... \times x_{n} ) \bmod m =( (x_{1} \bmod m) \times (x_{2} \bmod m) \times ... \times (x_{n} \bmod m)) \bmod m$

任何整数都可以表示为:

$z = m \times k + r, ( m,k,r \in Z_{\geq 0})$ (1)

则:

$r = z \bmod m$ (2)

若 r 等于 0，则 z mod m = 0;

领

$\begin{align*}x_{1} &= m \times k_{1} + r_{1}\\x_{2} &= m \times k_{2} + r_{2}\\...\\x_{n} &= m \times k_{n} + r_{n}\\\end{align*}$

则:

$\begin{align*}&x_{1} \times x_{2} \times ... \times x_{n} \\&= (m \times k_{1} + r_{1}) \times (m \times k_{2} + r_{2}) \times ... \times (m \times k_{n} + r_{n}) \\&= m \times (所有含m项...)+ (r_{1} \times r_{2} \times ... \times r_{n}) \\\end{align*}$

根据 (1)、(2), 两边取模 m 得到:

$\begin{align*}&(x_{1} \times x_{2} \times ... \times x_{n}) \bmod m \\&= (r_{1} \times r_{2} \times ... \times r_{n}) \bmod m \\\end{align*}$

由（2）得到:

$\begin{align*}&(x_{1} \times x_{2} \times ... \times x_{n}) \bmod m \\&= ((x_{1} \bmod m) \times (x_{2} \bmod m) \times ... \times (x_{n} \bmod m)) \bmod m \\\end{align*}$

证毕

ps:年纪大了, 现在巩固一下数学知识，若有错望留言。

证明模运算的分配性

一. 证明:

二. 证明:

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读