数论学习笔记-526互联

前言
数论基础

1.1 整除

1.2 带余除法，同余
质数

2.1 唯一分解定理

2.2 质数筛（线性筛）

2.3 欧拉函数
最大公因数/最小公倍数

3.1 辗转相除法

3.2 裴蜀定理

3.2 扩展欧几里得算法
线性同余方程

4.1 费马小定理

4.2 欧拉定理

4.3 逆元

4.4 求解线性同余方程

4.5 中国剩余定理
威尔逊定理
卢卡斯定理

0. 前言

数论太差了，恶补一下。

学一点更一点。

1.数论基础

1.1 整除

设 $a\in \N^+$ ，$b\in \Z$ ，若存在整数 $q$ 使得 $b=a\times q$ ，则称 $b$ 可被 $a$ 整除，记作 $a|b$ ，称 $a$ 为 $b$ 的因数，$b$ 为 $a$ 的倍数。

整除的性质：

若 $a|b$ 且 $b|c$ ，则 $a|c$。
若 $a|b$ 且 $a|c$ ，则满足 $a|(b\times x+c\times y)$ ，其中 $b,c$ 为整数。
若 $m \neq 0$，则 $a\,|\,b \iff am\,|\,bm$
若整数 $x,y$ 满足 $ax+by=1$ 且 $a\,|\,n,b\,|\,n$ ，则 $a\times b\,|\,n$
若 $b=k\times d+c$ ，则 $d\,|\,b \iff c\,|\,b$

1.2 带余除法，同余

若存在整数 $a,b$，$d$ 为给定的整数，满足 $b=q\times a+r,d\leq r <d+|a|$ ，则称 $r$ 为 $b$ 除以 $a$ 的余数。

也可以记作 $b\equiv r\,(\text{mod}\,\,a)$ 。意味 $b$ 与 $r$ 在取模 $a$ 意义下相等。

同余的性质：

$a\equiv b\pmod m,b\equiv c\pmod m$ ，则 $a\equiv c\pmod m$
$a\equiv b\pmod m$ 则 $a+c\equiv b+c \pmod m$
$a\equiv b\pmod m$ 且 $c\equiv d\pmod m$ ，则 $a\times c\equiv b\times d\pmod m$
$a\times b \equiv k=$ $(a\bmod k)\times(b\bmod k)$
若 $\gcd(p,q)=1, a\equiv b\pmod p,a\equiv b\pmod q$ ，则 $a\bmod pq=b$

2. 质数

设整数 $p\neq 0,\pm1 $，且 $p$ 没有除 $1$ 外的其它因数，则称 $p$ 为质数。

任何一个大于 $3$ 的质数都可以表示为 $6k+1$ 的形式

2.1 唯一分解定理

引理：若质数 $p\,|\,ab$ 则 $p\,|\,a$ 或 $p\,|\,b$ 满足其一。

设正整数 $a$ ，则必有：

\[a=p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n} \]

其中 $p_i$ 为质数，$e_i$ 为该质数的次数。

在不计次序的情况下，该表示唯一。

2.2 质数筛（线性筛）

我们记 $f_i$ 标记 $i$ 是否为质数，$p_i$ 为已经筛出来的质数。

对于每一个筛出来的质数，我们将它乘上之前筛出的每一个质数，即可筛出所有质数。

为了优化时间，当我们发现这个数曾被筛过便直接跳出循环。

时间复杂度：$O(n)$

void work(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!f[i])
            p[++tot]=i;
        for(int j=1;j<=tot;j++)
        {
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

2.3 欧拉函数

定义：$\varphi(n)=\sum_{i-1}^n [\gcd(i,n)=1]$。

性质：

当 $n$ 为质数时，$\varphi(n)=n-1$。
$\varphi(ab)=\varphi(a)\times\varphi(b)$
当 $n$ 为奇数时，$\varphi(n)=\varphi(2n)$
$n=\sum_{d|n} \varphi(d)$
将 $n$ 唯一分解后，$n=\prod p_i^{e_i}$ 则 $\varphi(n)=n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$