同余定理与简单模运算定理

模的定义

当我们讨论$r=a\mathrm{mod}b$ 时候实际上有 $a=qb+r$ 其中$q$为一个非负整数

同余定理

下面我们会给出模数的几个重要性质，即同余定理并且尝试证明

定理1:当$a\equiv b(\mathrm{mod}m)$且 $d\equiv 0(\mathrm{mod}m)$ 时，有 $a\equiv b(\mathrm{mod}d)$

poof:

$$\begin{array}{rl}\because a& \equiv b(\mathrm{mod}m)\\ \text{设: }qm+r& =a,pm+r=b\\ \because d& \equiv 0(\mathrm{mod}m)\\ \text{设: }m& =kd\\ \text{显然：}a& =qkd+r,b=pkd+r\\ \therefore a& \equiv b(\mathrm{mod}d)\\ \mathbb{Q}.\mathbb{E}.\mathbb{D}& \end{array}$$

定理2:当 $a\equiv b(\mathrm{mod}m)\text{and}c\equiv d(\mathrm{mod}m)$ 时，有：

\begin{align*} (1) \quad a+c \equiv b+d \pmod m \\ (2)\quad a - c \equiv b - d \pmod m \\ (3) \quad a \times c \equiv b \times d \pmod m \end{align*}

poof

$$\begin{array}{rl}\because a& \equiv b(\mathrm{mod}m),c\equiv d(\mathrm{mod}m)\\ \text{设： }a=k_{a}m+r& ,b=k_{b}m+r,c=k_{c}m+w,d=k_{d}m+w\\ & \\ poof(1):& \\ a+c& =k_{a}m+k_{c}m+r+w\\ b+d& =k_{b}m+k_{d}m+r+w\\ (a+c)\mathrm{mod}m& =(r+w)\mathrm{mod}m\\ (b+d)\mathrm{mod}m& =(r+w)\mathrm{mod}m\\ \therefore a+c& \equiv b+d(\mathrm{mod}m)\\ & \\ poof(2):& \\ \text{同(1)有： }(a-c)\mathrm{mod}m& =(r-w)\mathrm{mod}m\\ (b-d)\mathrm{mod}m& =(r-w)\mathrm{mod}m\\ \therefore a-c& \equiv b-d(\mathrm{mod}m)\\ & \\ poof(3):& \\ ac& =(k_{a}m+r)(k_{c}m+w),bd=(k_{b}m+r)(k_{d}m+w)\\ ac& =k_a{k}_c{m}^2+(k_{a}w+k_{c}r)m+wr\\ bd& =k_b{k}_d{m}^2+(k_{b}w+k_{d}r)m+wr\\ ab\mathrm{mod}m& =wr\mathrm{mod}m\\ cd\mathrm{mod}m& =wr\mathrm{mod}m\\ a\times c& \equiv b\times d(\mathrm{mod}m)\\ & \\ \mathbb{Q}.\mathbb{E}.\mathbb{D}& \end{array}$$

定理3: 当 $ac\equiv bc(\mathrm{mod}m)$ 且 $\gcd (c,m)=1$ 时，有 $a\equiv b(\mathrm{mod}m)$

由于LaTeX太难打了，下面证明采用更简单的方式呈现
poof:

• 因为$\gcd (c,m)=1$即存在$c^{-1}$使得$c\cdot c^{-1}\equiv 1(\mathrm{mod}m)$
• 显然$ac\cdot c^{-1}\equiv bc\cdot c^{-1}(\mathrm{mod}m)$
• 既: $a\equiv b(\mathrm{mod}m)$
• $\mathbb{Q}.\mathbb{E}.\mathbb{D}$

定理4: 当 $a\equiv b(\mathrm{mod}m)$ 时,对于任意的 $c\ne 0$ 有 $ac\equiv bc(\mathrm{mod}m)$

poof:

• $a\equiv b(\mathrm{mod}m)\Rightarrow a-b=k_{1}m$
• $ac\equiv bc(\mathrm{mod}m)\Rightarrow c(a-b)=k_{2}m$
  • 有$a-b=\frac{k_2}{c}m$
• 在模运算下我们不关心$m$前的系数,即 $a-b=\frac{k_2}{c}m⟺a\equiv b(\mathrm{mod}m)$

定理5: 当 $a=b(\mathrm{mod}m)$时,对任意正整数$k$,有 $a^k\equiv b^k(\mathrm{mod}m)$

poof:

• 由定理3: $a\equiv b(\mathrm{mod}m)\Rightarrow a\cdot a\equiv b\cdot b(\mathrm{mod}m)$
• 扩展可得: $a^k\equiv b^k(\mathrm{mod}m)$

定理6: 当 $a\equiv b(\mathrm{mod}m)$时,存在整数$k$,使$a-b=km$

poof:

• $a=k_{1}m+r,b=k_{2}m+r$
• 显然存在 $k=k_1-k_2$ 有 $a-b=km$

在模意义下的四则运算

在模意义下,四则运算的处理应该谨慎,下面给出四则运算处理方式

加法:

$$a+b\Rightarrow (a+b)\%\text{MOD}$$

减法:

$$a-b\Rightarrow (a-b+\text{MOD})\%\text{MOD}$$

乘法:

$$a\times b\Rightarrow (a\times b)\%\text{MOD}$$

除法(整除意义下):

$$\frac{a}{b}\Rightarrow a\times b^{-1}\%\text{MOD}$$

其中:$b^{-1}$为$b$的乘法逆元