第一章 整除、公因数公倍数

  1. 若$a\mid b$，则$\exist c$，使得$b=ac$

    若$p\mid ab$，则$p\mid a$或$p \mid b$

    若$a \mid mb$且$(a,b)=1$，则$a \mid m$ （单边消去）

  2. $am \mid bm ,\space m \ne 0\Leftrightarrow a \mid b$ （双边消去）

  3. $[a,b](a,b)=ab$

    $d =(a,b)$，则$(\frac ad,\frac bd)=1$

  4. a，b的最大公因数可以用辗转相除法求，例如$(78,108)=(78,30)=(18,30)=(18,12)=(6,12)=6$

第二章 同余关系

  1. $a\equiv b\mod m \Leftrightarrow m \mid a-b$ （证明mx+mx通过mm的完系时常用）

  2. 对于同余式组：

    $$ \begin{cases} a\equiv b\mod m\\ \alpha \equiv \beta \mod m \end{cases} $$

    有$a+\alpha \equiv b+\beta \mod m$；$a\cdot\alpha \equiv b \cdot\beta \mod m$；$f(a) \equiv f(b)\mod m$

  3. 威尔逊定理：$(p-1)!+1 \equiv 0\mod p$

    欧拉定理：$(a,m)=1,\space\space a^{\varphi(m)}\equiv1\mod m$

    费马小定理：$a^p\equiv a\mod p$

  4. 完全剩余系是包括0在内的，一定有n个元素，从0到n-1，例如8的一个完全剩余系为{0,1,2,3,4,5,6,7}

  5. 缩系是不包括0的，是完全剩余系中与n互素的数构成的集合，因此一定有$\varphi(n)$个元素，从1开始，例如8的一个缩系为{1,3,5,7}

同余式的解法

  1. 对于一次同余式$ax\equiv b\mod m$，先使用$\frac adx\equiv \frac bd \mod \frac md,d=(a,m)$将a和m化为互素的形式，然后再计算逆元即可

  2. 中国剩余定理

    $$ \begin{align} x\equiv M_1M_1^\prime a_1+M_2M_2^\prime a_2+\dots+M_iM_i^\prime a_i \nonumber \\ \nonumber \\ 其中 M_i=\frac m{m_i},M_i^\prime\equiv M_i^{-1}\mod m_i\nonumber \end{align} $$

    若$m_i$们不互素，则先将其素数分解、去重，然后再进行求解

  3. 解模数是素数幂的同余式，如$f(x)\equiv 0\mod p^3$

    1. 求出$f(x)\equiv 0 \mod p$的解$x_1$，一般是试出来的
    2. 求出$f^\prime(x_1)$备用
    3. 对于$f(x)\equiv 0 \mod p^2$，解$f^\prime(x_1)\cdot t_1 \equiv \frac {-f(x_1)}{p}\mod p$，最后得到$x_2=x_1+pt_1$
    4. 对于$f(x)\equiv 0\mod p^3$，解$f^\prime(x_1)\cdot t_2\equiv \frac{-f(x_2)}{p^2}\mod p$，最后得到$x_3=x_2+pt_2$

    注意求出来的**$f^\prime(x_1)$**是一直用的不会变，另外不会变的还有模数p

第三章 数论函数

  1. 对于素数p，若$p^m \mid n$，但$p^{m+1}\nmid n$，则有$pot_pn=m$

    关于$pot$函数的性质，类似于反过来的$log$函数，即“乘变加，除变减”

  2. 莫比乌斯函数

    $$ \mu(n)= \begin{cases} (-1)^s, & l_1=l_2=\dots=l_s \\ 0, & \exist l_i>1 \end{cases} $$$$ \sum_{d\mid n}\mu(d)=[\frac 1n]=I(n)= \begin{cases} 1, & n=1\\ 0, & n>1 \end{cases} $$

    可以看到，莫比乌斯函数的莫比乌斯变换函数是$I(n)$，即单位函数

  3. 欧拉函数

    计算公式：$\varphi(n)=n\cdot (1-\frac 1{p_1})\dots(1-\frac 1{p_s})$，另外n为素数时，$\varphi(n)=n-1$

    性质：$\varphi(mn)=\varphi(m)\varphi(n)\frac{d}{\varphi(d)}$，其中$d=(m,n)$

    $$ \begin{align} \sum_{d\mid n}\varphi(d)&=n\\ \sum_{d\mid n}\mu(d)\frac nd&=\varphi(n) \end{align} $$

    从（1）可以看出，欧拉函数的莫比乌斯变换函数是n

    从（2）可以看出，n的莫比乌斯逆变换函数是欧拉函数

  4. 狄利克雷乘积

    f(n)和g(n)的狄利克雷乘积为：

    $$ \sum_{d\mid n}f(d)g(\frac{n}{d}) $$

    满足交换律、结合律、逆元、幺元，满足$f(1)\ne0$的数论函数对狄利克雷乘积运算构成Abel群

  5. 莫比乌斯反演

    $$ \begin{align} 若f(n)&=\sum_{d\mid n}g(d), \nonumber \\ 则g(n)&=\sum_{d\mid n}\mu(d)f(\frac nd) \nonumber \end{align} $$

    f(n)称为g(n)的莫比乌斯变换（或认为是g(n)与1的狄利克雷乘积）

    g(n)称为f(n)的莫比乌斯逆变换（或认为是u(n)和f(n)的狄利克雷乘积）

  6. 积性函数：数论函数f(n)不恒等于0，且当(m,n)=1时，满足f(mn)=f(m)f(n)，则f(n)称为积性函数；

    如果对于任意的m、n，都有f(mn)=f(m)f(n)，则f(n)称为完全积性函数

第四章 二次剩余

  1. $x^2\equiv a\mod p$，p是奇素数，判断a是p的二次剩余还是二次非剩余

    若$a^{\frac{p-1}2}\equiv 1\mod p$，则a是p的二次剩余；

    若$a^{\frac{p-1}2}\equiv -1\mod p$，则a是p的二次非剩余

  2. 勒让德符号

    $$ \left(\frac ap\right)= \begin{cases} 1, & p\nmid a，a是p的二次剩余\\ -1, & p\nmid a，a是p的二次非剩余\\ 0, & p\mid a \end{cases} $$$$ \left( \frac ap \right)=1 \Leftrightarrow x^2\equiv a\mod p有解 $$

    所以计算勒让德符号其实就是计算a是p的二次剩余还是二次非剩余，算出来后如果等于1，则又能说明二次同余式有解

    性质：$(\frac ap)=(\frac {a+p}p)$；$(\frac{ab}p)=(\frac ap)(\frac bp)$，这两个性质都可以快速缩小上方的数

  3. 雅各比符号

    是勒让德符号的泛化，可以简化勒让德符号的计算

    $$ \left(\frac ap\right)=\left(\frac a{p_1}\right)\left(\frac a{p_2}\right)\dots\left(\frac a{p_s}\right) $$

    上式中左侧是雅各比符号，右侧是勒让德符号，p是素数，可以重复

    不难发现，雅各比符号的下方数也可以拆开，即上下均可拆，同时雅各比符号也可以快速缩小上方的数

  4. 解二次同余式

    目前仅能解p为特殊值的同余式

    • $p\equiv 3\mod 4$时，$x \equiv \pm a^{\frac{p+1}4}\mod p$

    • $p\equiv 5\mod 8$时：

      若$a^{\frac{p-1}4}\equiv 1\mod p$，则$x\equiv \pm a^{\frac{p+3}8}\mod p$；

      若$a^{\frac{p-1}4}\equiv -1\mod p$，则$x\equiv \pm (\frac p2)!a^{\frac{p+3}8}\mod p$

阶与原根

  1. 求n对p的阶数，也就是求使$n^l\equiv 1\mod p$成立的最小$l$值

    • 方法一：次数l一定是$\varphi(p)$的一个因子，先求$\varphi(p)$，然后一个个试$n^d\mod p$是否为1即可
    • 方法二：先将p作素数分解：$p=p_1^{l_1}p_2^{l_2}\dots p_s^{l_s}$，然后计算n对每一个$p_i^{l_i}$的阶数，最后求出这些阶数的最小公倍数即可

  2. 证明原根

    若有一个整数a与大于2的数m满足(a,m)=1，$\varphi(m)$的各不同素因子为****$p_1,p_2,\dots ,p_s$，则a是m的一个原根的充要条件是：

    $$ a^{\frac{\varphi(m)}{p_i}}\not \equiv1\mod m $$

  3. 求模m的所有原根，也就是求g，使得g对模m的阶数正好是$\varphi(m)$

    • 方法一：从2出发开始枚举（要与m互素），看是否满足模m与1同余的最小幂值恰好是$\varphi(m)$

    • 方法二：先猜出一个原根g1，然后基于这个g1生成其他g

      已知m的一个原根g，$\varphi(m)$的缩系为{ki}，则m的其余原根为$g^{k_i}\mod m$

  4. 已知m的原根g，求$m^\alpha$、$2\cdot m^\alpha$的原根：已经有定理了，只要检验一下条件即可

    • 只要满足$g^{\varphi(m^{\alpha-1})}\not\equiv 1\mod m^\alpha$，则g也是$m^\alpha$的一个原根；

      如果$g^{\varphi(m^{\alpha-1})}\equiv 1\mod m^\alpha$，则g+m是$m^\alpha$的一个原根

    • 只要m是奇数，g就也是$2\cdot m^\alpha$的一个原根

  5. 用m的原根g表示m的缩系：$\{1,g^1,g^2,\dots,g^{\varphi(m)-1}\}\mod m$