数论
1. 模方程
线性同余方程
线性同余方程组
主要内容
- 考虑形如 ab≡cmodm 的方程
下文模方程均为 f(x)≡0modm
非线性同余方程
- 因式分解
离散对数问题
考虑 f(x)=ax+c ,则问题演变为离散对数问题
求解方法
m为质数
a和m互质
一般情况
2. 原根
定义
考察方程 a⋅x≡1(modm),若 gcd(a,m)=1 ,则方程一定有解 x=φ(m)
我们定义在上述情况下,方程最小的解为 x=δm(a) ,
则显然有 δm(a)≤φ(m) ,若a满足条件 δm(a)=φ(m) ,我们就称a是模m的原根
群论
定义
G={S,⊕}
性质
封闭性
a⊕(b⊕c)=(a⊕b)⊕c
存在单位元
存在逆元
原根的应用
- 模数为指数的高次剩余问题 xa≡bmodp
3. 积性函数
Dirichlet特征
有周期
完全积性
f(1)=1
积性函数与完全积性函数
常用积性函数
欧拉函数(φ):φ(n) 表示1~n中与n互质的数的个数
莫比乌斯函数(μ):μ(1)=1 ,若 n(n>1) 含有多重质因数,则 μ(n)=0 ,否则 μ(n)=(−1)r ,r表示n的质因数个数(与容斥比较像)
除数函数(σ):一类函数,每个非负整数x都对应一个除数函数σx,σx(n)表示n的因数的x次方之和
欧拉筛筛欧拉函数
欧拉函数的推论
1
当n>1时,1~n中与n互质的数的和为n*φ(n)/2
欧拉定理
1
若n,a∈N满足gcd(n,a)=1,则a^φ(n) ≡1(mod n)
扩展欧拉定理
1
2
3
4设a,b,n∈N,若:
• gcd(n,a)=1,则a^b ≡a^b mod φ(n) (mod n)
• gcd(n,a)≠1,b≤φ(n),则用快速幂计算
• gcd(n,a)≠1,b>φ(n),则a^b ≡a^(b mod φ(n))+φ(n) (mod n)莫比乌斯函数的积性函数
其他积性函数
1
2
3
4
5
6
7
8• 常函数(1):∀n∈N,1(n)=1
• 单位函数(id):∀n∈N,id(n)=n
• 幂函数(id k ):∀n∈N,id k (n)=n k
• 狄利克雷卷积单位函数(ε):ε(1)=1,∀n>1,ε(n)=0
• 元函数(e):这是一个由命题映射到N的特殊函数,
e[P]=1当且仅当P为真,否则e[P]=0
• 倒数函数(f):∀n∈N,f(n)=1/n
• 值得一提的是,这些函数都是完全积性函数保留 狄利克雷
两个重要推论
μ×1=ε
φ×1=id
莫比乌斯反演定理
f×1=g↔μ×g=f
四个卷积结论:
φ×1=id
μ×id=φ
μ×1=ε
ε×1=1
v1.5.2