转载请声明出处
目录说：我在右边
看了好多人的博客都不太全，励志做出最全的数论知识
持续更新中...
前置知识
质数与约数
浅谈gcd与exgcd
线性同余方程
形如(ax equiv c (mod b))的方程，称为线性同余方程，
等价于(ax + by=c), 因此有解条件为 ((a,b) mid c)
若 (gcd(a,b) = 1)，则 (x) 有唯一解 (x ≡ a^{−1} c(mod b))。
否则设 (gcd(a,b) = d,a = a ′ d,b = b ′ d,c = c ′ d)
那么有 (a ′ x + b ′ y = c ′) ，即 (a ′ x ≡ c ′ (mod b ′ ))
这里 (gcd(a ′ ,b ′ ) = 1)，因此有 (x ≡ (a ′ ) ^{−1} c ′ (mod b ′ ))
综上，任意的线性同余方程总可以判定为无解，或化为 (x ≡ a(mod m)) 的形式。
中国剩余定理
欧拉函数与欧拉定理