北京游记Day3

数论

1. 模方程

1. 线性同余方程

2. 线性同余方程组

3. 主要内容

   1. 考虑形如 $a^b\equiv c \mod m$ 的方程

下文模方程均为 $f(x)\equiv 0 \mod m$

1. 非线性同余方程

   1. 因式分解

2. 离散对数问题

   1. 考虑 $f(x)=a^x+c$ ,则问题演变为离散对数问题

   2. 求解方法

      1. m为质数

      2. a和m互质

      3. 一般情况

2. 原根

1. 定义

   考察方程 $a \cdot x ≡1(mod m)$，若 $gcd(a,m)=1$ ，则方程一定有解 $x=\varphi(m)$

   我们定义在上述情况下，方程最小的解为 $x=δ m (a)$ ，

   则显然有 $δ m (a)≤φ(m)$ ，若a满足条件 $δ m (a)=φ(m)$ ，我们就称a是模m的原根

2. 群论

   1. 定义

      G={S,⊕}

   2. 性质

      1. 封闭性

      2. $a⊕(b⊕c)=(a⊕b)⊕c$

      3. 存在单位元

      4. 存在逆元

3. 原根的应用

   1. 模数为指数的高次剩余问题 $x^a\equiv b \mod p$

3. 积性函数

1. Dirichlet特征

   1. 有周期

   2. 完全积性

   3. $f(1)=1$

2. 积性函数与完全积性函数

3. 常用积性函数

   1. 欧拉函数($\varphi$)：$\varphi(n)$ 表示1~n中与n互质的数的个数

   2. 莫比乌斯函数($\mu$)：$\mu(1)=1$ ，若 $n(n＞1)$ 含有多重质因数，则 $μ(n)=0$ ，否则 $μ(n)=(-1)^r$ ，$r$表示$n$的质因数个数(与容斥比较像)

   3. 除数函数($σ$)：一类函数，每个非负整数x都对应一个除数函数$σ x$，$σ x (n)$表示n的因数的x次方之和

4. 欧拉筛筛欧拉函数

5. 欧拉函数的推论

   当n>1时，1~n中与n互质的数的和为n*φ(n)/2

6. 欧拉定理

   若n,a∈N满足gcd(n,a)=1，则a^φ(n) ≡1(mod n)

7. 扩展欧拉定理

   设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)

8. 莫比乌斯函数的积性函数

9. 其他积性函数

   • 常函数(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
   • 值得一提的是，这些函数都是完全积性函数

10. 保留 狄利克雷

11. 两个重要推论

    1. $\mu \times 1=\varepsilon$

    2. $\varphi \times 1=id$

12. 莫比乌斯反演定理

    $f×1=g↔μ×g=f$

13. 四个卷积结论：

    1. $\varphi \times 1=id$

    2. $μ \times id=\varphi$

    3. $μ \times 1=\varepsilon$

    4. $\varepsilon \times1 =1$