同余运算及其基本性质（证明）

Post author:xfxia
Post published:2023年8月29日
Post category:其他

首先一点是，

$a \equiv b\quad\pmod m$
的原型是

$a\mod m=b$

线性运算

a \equiv b (mod m) c \equiv d (mod m)} \Rightarrow {a \pm c \equiv b \pm d (mod m) a \times c \equiv b \times d (mod m)

$\left. \begin{array}{} a\equiv b\quad \pmod m\;\\ c\equiv d \quad \pmod m \end{array} \right \}\Rightarrow \left \{ \begin{array}{} a\pm c\equiv b\pm d\quad\pmod m\\ a\times c\equiv b\times d\quad \pmod m \end{array} \right.$

证明：

m | a - b, m | c - d \Rightarrow m | [(a - b) \pm (c - d)] \Rightarrow m | [(a \pm c) - (b \pm d)] \Rightarrow a \pm c \equiv b \pm d (mod m)

$m|a-b,m|c-d\;\Rightarrow\;m|[(a-b)\pm (c-d)]\;\Rightarrow\; m|[(a\pm c)-(b\pm d)]\;\Rightarrow\;a\pm c\equiv b\pm d\quad \pmod m$

a c - b d = a c - b c + b c - b d = (a - b) c + (c - d) b m | (a - b), m | (c - d) \Rightarrow m | (a c - b d) \Rightarrow a c \equiv b d (mod m)

$ac-bd=ac-bc+bc-bd=(a-b)c+(c-d)b\\ m|(a-b),m|(c-d)\;⇒\; m|(ac-bd)\;⇒\;ac \equiv bd\quad\pmod m$

一个小推论，

a \equiv b (mod m) \Leftrightarrow k a \equiv k b (mod m) a mod m = b \Leftrightarrow k a mod m = k b

$a\equiv b\quad\pmod m\;\Leftrightarrow\;ka\equiv kb\quad\pmod m\\ a\mod m=b\;\Leftrightarrow\;ka\mod m=kb$

线性运算的一个自然推论

a \equiv b (mod m) \Rightarrow {a n \equiv b n a n \equiv b n (mod m), \forall n \in Z (mod m), \forall n \in Z

$a\equiv b\pmod m\Rightarrow\left \{ \begin{array}{ll} an\equiv bn &\pmod m,\forall n\in \mathbb Z\\ a^n\equiv b^n&\pmod m,\forall n \in \mathbb Z \end{array} \right.$

移项

a + b \equiv c (mod m) ⇓ a \equiv c - b (mod m)

$a+b\equiv c\pmod m\\ \Downarrow\\ a\equiv c-b\pmod m$

证明如下：

a + b \equiv c (mod m) ⇓ m | a + b - c ⇓ m | a - (c - b) ⇓ a \equiv c - b (mod m)

$a+b\equiv c\pmod m\\ \Downarrow\\ m|a+b-c\\ \Downarrow\\ m|a-(c-b)\\ \Downarrow\\ a\equiv c-b\pmod m$

原文链接：https://blog.csdn.net/lanchunhui/article/details/50591912

线性运算

线性运算的一个自然推论

移项

你可能也喜欢