同余

基本定义 \(a\ \%\ m=b\ \%\ m\)，同余式为 \(a\equiv{b}\pmod{m}\)

基本定理

1. \(a\equiv{b}\pmod{m}\)，当且仅当 \(m\ |\ (a-b)\)
2. \(a\equiv{b}\pmod{m}\)，当且仅当存在整数 \(k\)，使得 \(a=b+k\cdot{m}\)

3. 同余关系是等价关系

   自反：\(a\equiv{a}\pmod{m}\)

   对称性：\(a\equiv{b}\pmod{m}\)，则 \(b\equiv{a}\pmod{m}\)

   传递性：\(a\equiv{b}\pmod{m},b\equiv{c}\pmod{m}\)，则 \(a\equiv{c}\pmod{m}\)

4. 若 \(a\equiv{b}\pmod{m},c\equiv{d}\pmod{m}\)，则

   \(a*x+c*y\equiv b*x+d*y\pmod m\)

   \(a*c\equiv b*d\pmod m\)

   \(a^n\equiv b^n\pmod m\)

   \(f(a)\equiv f(b)\pmod m\)

结论

（1）对任意整数 \(n\) , \(n^2\) 模 \(3\) 或 \(4\) 的结果只能是 \(0\) 或 \(1\)

（2）对任意整数 \(n\) , \(n^2\) 模 \(8\) 的结果只能是\(0\)、\(1\) 或 \(4\)

（3）对任意整数 \(n\) , \(n\) 与 \(n\) 各数位上的数字之和模 \(9\) 同余

扩展欧几里得算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

template<class T> T Exgcd(const T a, const T b, T &x, T &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    T d = Exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

线性同余方程

\(a*x\equiv b\pmod n\)