北京游记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. 欧拉函数的推论

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

  6. 欧拉定理

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

  7. 扩展欧拉定理

    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)

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

  9. 其他积性函数

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

  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 $