数论入门

持续更新中....

转载请声明出处

目录说：我在右边

看了好多人的博客都不太全，励志做出最全的数论知识

持续更新中...

前置知识

整除

计数原理

同余

质数与约数

质数与合数

筛法

约数个数定理与约数和定理

浅谈gcd与exgcd

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)\) 的形式。

中国剩余定理

欧拉函数与欧拉定理