同余

主要内容：

1. 同余
2. 同余方程
3. 特性

1、同余

如果a和b除以m的余数相同，就说a和b关于模m同余，记作a ≡ b (mod m)。

a ≡ b (mod m) 等价于m整除 a-b，即 m | (a-b)，也即a = m*t + b。

2、同余方程

例如ax≡y(mod m)，就称为同余方程。

基于同余的定义，ax = mt + y => ax - mt = y

就转换成了二元一次方程。

3、特性

基于同余的特性，就可以用来将运算结果求余转换为先求余再运算，从而用于大数计算。

3.1 基础特性

• 自反性：a ≡ a (mod m)
• 对称性：a ≡ b (mod m) <=> b ≡ a (mod m)
• 传递性：a ≡ b (mod m)，b ≡ c (mod m) => a ≡ c (mod m)

3.2 运算特性

• 同加性：a ≡ b (mod m) => a+c ≡ b+c (mod m)
• 同乘性：
  • a ≡ b (mod m) -> a * c ≡ b * c (mod m)
  • a ≡ b (mod m) ，c ≡ d (mod m) => a * c ≡ b * d (mod m)
• 同幂性：a ≡ b (mod m) => a^n ≡ b^n (mod m)
• 同除性：a * c ≡ b * c (mod m)，若(c, m) = 1，则 a ≡ b (mod m)
  • 推广：若(c, m) = k，则a ≡ b (mod m/k)

3.3 大数应用

• 乘法分解：(a * b) %m =( (a%m) * (b%m)) % m
• 加法分解：(a+b)%m =( (a%m) + (b%m)) % m
• 除法分解：不能直接同除，需要用到乘法逆元。

除法反例：

(100/50) % 20 = 2
(100%20) / (50%20) = 0