同余

一.定理

• $ a \equiv b~ (mod ~m) ~ \Leftrightarrow~ a-b=mt $
• $ a \equiv b~ (mod ~m) ~ \Leftrightarrow~ b \equiv a~ (mod ~m) $
• $ a\equiv b ~ (mod~ m) ~ c\equiv b ~ (mod ~m) \iff a\equiv c ~ (mod ~m) $
• $ a\equiv b ~ (mod~ m) ~ c\equiv d ~ (mod ~m) \iff a+c\equiv b+d ~ (mod ~ m) $
• $ a\equiv b ~(mod ~ m) ~ c\equiv d ~ (mod ~m) \iff a-c\equiv b-d ~ (mod ~ m) $
• $ a \equiv b ~ (mod ~ m) ~ c\equiv d ~ (mod ~ m) \iff a * c \equiv b*d ~ (mod ~ m) $

二.推论

• 若 $ a \equiv b ~ (mod ~ m) $ ， $ n $为自然数 ，则 $ a*n \equiv b * n ~ (mod ~ m) $ 。

• 若 $ a \equiv b ~ (mod ~m) $ ，$ n $为自然数 ，则 $ a^n \equiv b^n ~ (mod ~ m) $ 。

• 若 $ c * a\equiv c * b ~ (mod ~ m) , gcd(c,m)=d $ ，且 $ a,b,c,m $为整数，则 $ a\equiv b ~(mod ~ \frac{m}{d}) $。

  证明 ：
  显然 $ m | c(a-b) \iff m|d * (c / d) * (a-b)$ 且 $ m \perp (c / d) $
  所以 $ \frac{m}{d}|a-b \iff a \equiv b~(mod ~ \frac{m}d) $

• 若 $ c * a\equiv c * b ~ (mod ~ m) , gcd(c,m)=1 $ ，且 $ a,b,c,m $为整数，则 $ a\equiv b ~(mod ~ {m}) $。

• 若 $ a\equiv b ~ (mod ~ m) ,\exists d|m $ ，则 $ a\equiv b ~(mod ~ {d}) $。
  证明：
  易得 $ m|a-b $
  由于 \(a-b\) 中必有m的全部因子，所以显然 $ d|a-b $
  所以 $ a\equiv b ~(mod ~ {d}) $

• 若 $ a\equiv b ~ (mod ~ m),a\equiv b ~ (mod ~ n) $，则 $ a\equiv b ~ (mod ~ lcm(n,m)) $
  证明：
  设 $ d=gcd(n,m) ~ m=x * d ~ n=y * d ~ lcm(n,m)=x * y * d $
  $ \iff x * d|a-b,y * d|a-b $
  $ \iff x * y * d|a-b $
  $ \iff lcm(n,m)|a-b $
  $ \iff a\equiv b ~(mod ~ lcm(n,m))$
• 若 $ a\equiv b ~ (mod ~ m_i),i=1,2,3,....,n $ 则 $ a\equiv b ~ (mod~lcm(m_1,m_2,..,m_n)) $

• $ a\equiv b ~ (mod ~ m) \Rightarrow a * k\equiv b * k ~(mod ~ m * k) $
  证明：
  $ \Rightarrow m|a-b \Rightarrow m * k|a * k-b * k \iff a * k\equiv b * k ~(mod ~ m * k) $

• $ a\equiv b ~ (mod~m) \Rightarrow gcd(a,m)=gcd(b,m) $
  证明：
  $ \gcd(a,m)=\gcd(m,a \bmod m) $ 且 $ \gcd(b,m)=\gcd(m,b \bmod m) $
  $ \because a\equiv b ~ (mod~m) $
  $ \therefore a%m=b%m $
  $ \therefore gcd(a,m)=gcd(b,m) $

6.完全平方数模的特征

• 完全平方数模 $ 4 $ 同余于 $ 0,1 $

• 完全平方数模 $ 8 $ 同余于 $ 0,1,4 $

• 完全立方数模 $ 9 $ 同余于 $ 0,1,-1 $

• 整数的四次幂模 $ 16 $ 同余于 $ 0,1 $