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

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

1,289 字 · 约 3 分钟

模的定义

当我们讨论r=a mod br = a \bmod b 时候实际上有 a=qb+ra = qb + r 其中qq为一个非负整数

同余定理

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

定理1:当a≡b(modm)a \equiv b\pmod m且 d≡0(modm)d \equiv 0\pmod m 时,有 a≡b(modd)a \equiv b \pmod d

poof:

∵a≡b(modm)设: qm+r=a,pm+r=b∵d≡0(modm)设: m=kd显然:a=qkd+r,b=pkd+r∴a≡b(modd)Q.E.D\begin{align*} \because a &\equiv b \pmod m\\ \text{设: }\quad qm + r &= a,pm + r = b \\ \because d &\equiv 0\pmod m \\ \text{设: }\qquad \quad m &= kd \\ \text{显然:}\qquad \quad a &= qkd + r , b = pkd + r \\ \therefore a &\equiv b \pmod d\\ \mathbb{Q.E.D} \end{align*}

定理2:当 a≡b(modm)andc≡d(modm)a \equiv b \pmod m \quad \text{and} \quad c \equiv d \pmod m 时,有:

(1)a+c≡b+d(modm)(2)a−c≡b−d(modm)(3)a×c≡b×d(modm)\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

∵a≡b(modm) , c≡d(modm)设: a=kam+r,b=kbm+r,c=kcm+w,d=kdm+wpoof(1):a+c=kam+kcm+r+wb+d=kbm+kdm+r+w(a+c) mod m=(r+w) mod m(b+d) mod m=(r+w) mod m∴a+c≡b+d(modm)poof(2):同(1)有: (a−c) mod m=(r−w) mod m(b−d) mod m=(r−w) mod m∴a−c≡b−d(modm)poof(3):ac=(kam+r)(kcm+w) , bd=(kbm+r)(kdm+w)ac=kakcm2+(kaw+kcr)m+wrbd=kbkdm2+(kbw+kdr)m+wrab mod m=wr mod mcd mod m=wr mod ma×c≡b×d(modm)Q.E.D\begin{align*} \because a &\equiv b \pmod m \ , \ c \equiv d \pmod 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) \bmod m &= (r + w) \bmod m\\ (b + d) \bmod m &= (r + w) \bmod m\\ \therefore a+c &\equiv b+d \pmod m\\ \\ poof(2): \\ \text{同(1)有: } (a - c) \bmod m &= (r - w) \bmod m\\ (b - d) \bmod m &= (r -w) \bmod m \\ \therefore a - c &\equiv b - d \pmod 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 \bmod m &= wr \bmod m \\ cd \bmod m &= wr \bmod m\\ a \times c &\equiv b \times d \pmod m\\ \\ \mathbb{Q.E.D}\\ \end{align*}

定理3: 当 ac≡bc(modm)ac \equiv bc \pmod m 且 gcd⁡(c,m)=1\gcd{(c,m)} = 1 时,有 a≡b(modm)a \equiv b \pmod m

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

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

定理4: 当 a≡b(modm)a \equiv b \pmod m 时,对于任意的 c≠0c \ne 0 有 ac≡bc(modm)ac \equiv bc \pmod m

poof:

  • a≡b(modm)⇒a−b=k1ma \equiv b \pmod m \Rightarrow a - b = k_{1}m
  • ac≡bc(modm)⇒c(a−b)=k2mac \equiv bc \pmod m \Rightarrow c(a - b) = k_{2}m
    • 有a−b=k2cma - b = \frac{k_{2}}{c}m
  • 在模运算下我们不关心mm前的系数,即 a−b=k2cm  ⟺  a≡b(modm)a - b = \frac{k_{2}}{c}m \iff a \equiv b \pmod m

定理5: 当 a≡b(modm)a \equiv b \pmod m时,对任意正整数kk,有 ak≡bk(modm)a^{k} \equiv b ^{k} \pmod m

poof:

  • 由定理3: a≡b(modm)⇒a⋅a≡b⋅b(modm)a \equiv b \pmod m \Rightarrow a \cdot a \equiv b \cdot b \pmod m
  • 扩展可得: ak≡bk(modm)a^{k} \equiv b^{k} \pmod m

定理6: 当 a≡b(modm)a \equiv b \pmod m时,存在整数kk,使a−b=kma - b = km

poof:

  • a=k1m+r,b=k2m+ra = k_{1}m + r,b = k_{2}m+r
  • 显然存在 k=k1−k2k = k_{1} - k_{2} 有 a−b=kma-b = km

在模意义下的四则运算

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

加法:

a+b⇒(a+b)%MODa + b \Rightarrow (a + b)\% \text{MOD}
减法:
a−b⇒(a−b+MOD)%MODa - b \Rightarrow (a -b+\text{MOD})\%\text{MOD}
乘法:
a×b⇒(a×b)%MODa \times b \Rightarrow (a \times b)\%\text{MOD}
除法(整除意义下):
ab⇒a×b−1%MOD\frac{a}{b} \Rightarrow a \times b^{-1} \% \text{MOD}
其中:b−1b^{-1}为bb的乘法逆元