Summary

这一篇就都是同余定理的理论芝士了呢 qwq.

Problems

• 洛谷 P1082 同余方程

Text

相关定义定理和推论 (背吧!

定义

用给定的正整数 m 分别除整数 a,b, 如果所得的余数相等, 则称 a,b 对模 m 同余, 记作 $a\equiv b (mod\ m)$.

定理 1

$a\equiv b (mod\ m)$ 的充要条件是 a - b 能被 m 整除 (即 $m|a-b$).

推论

$a\equiv b (mod\ m)$ 的充要条件是 $a=mt+b , t\in Z$.

定理 2

同余关系具有反身性, 对称性与传递性, 即:

• $a\equiv a (mod\ m)$;
• $a\equiv b (mod\ m) \Leftrightarrow b\equiv a (mod\ m)$;
• $a\equiv b (mod\ m) , b\equiv c (mod\ m) \Rightarrow a\equiv c (mod\ m)$.

定理 3

$a\equiv b (mod\ m) , c\equiv d (mod\ m) \Rightarrow$

• $a+c\equiv b+d (mod\ m)$;
• $a-c\equiv b-d (mod\ m)$;
• $a\cdot c\equiv b\cdot d (mod\ m)$.

推论

$a\equiv b (mod\ m) , n\in N \Rightarrow a\cdot n\equiv b\cdot n (mod\ m)$.

定理 4

$c\cdot a\equiv c\cdot b (mod\ m) , gcd(c,m)=d , a,b\in Z \Rightarrow a\equiv b (mod\ \frac{m}{d})$.

推论

$c\cdot a\equiv c\cdot b (mod\ m) , gcd(c,m)=1 , a,b\in Z \Rightarrow a\equiv b (mod\ m)$.

定理 5

$a\equiv b (mod\ m) , a\equiv b (mod\ n) \Rightarrow a\equiv b (mod\ lcm(m,n))$.

推论

$a\equiv b (mod\ m_i) , i=1,2,\dots,n \Rightarrow a\equiv b (mod\ lcm(m_1,m_2,\dots,m_n))$.

线性同余方程 (组)

可以结合 例题 1观看.

最大公约数

求 $gcd$ 的算法:
显然有更好的这里就不写了.
求 $exgcd$ 的算法(背吧!:

long long exgcd(long long a, long long b, long long &x, long long &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    long long q = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return q;
}

记得开long long.

题面 / 形式

给定 $a,b,m\in Z$, 求 $x\in Z$ 使 $a\cdot x\equiv b (mod\ m)$.

线性同余方程的解法

将原方程转化为 $a\cdot x+m\cdot y=b$, 则有解当且仅当 $gcd(a,m)|b$. 在有解的时候用exgcd求出一组 $x_0,y_0$, 则有

$$ x=\frac{x_0\cdot b}{gcd(a,m)} $$

中国剩余定理 (背吧!

假设 $m_1,m_2,\dots,m_n$ 两两互素, 则对于 $a_1,a_2,\dots,a_n$, 有

$$ \left\{\begin{aligned}x\equiv a_1 (mod\ m_1)\\x\equiv a_2 (mod\ m_2)\\\dots\\x\equiv a_n (mod\ m_n)\end{aligned}\right. $$

则有

$$ x\equiv \sum_{i=1}^n\frac{a_i\cdot\prod_{j=1}^nm_j}{m_i}\cdot $$