数学-初等数论

Posted by

数论是纯粹数学的分支之一,主要研究整数的性质。

整除

定义

带余除法中商为\(0\)的特殊情况,若\(b\div a=d\ldots 0\),则称\(b\)是\(a\)的约数(因数),\(a\)是\(b\)的倍数。\(b|a\)表示\(a\)能被\(b\)整除,\(b\not|a\)表示表示\(a\)不能被\(b\)整除。

有关概念

  1. 带余除法:商必须为整数的除法,\(c\div b=a\ldots d\)时,\(c=a\times b+d\);

  2. 向下取整:不大于该数的最大的整数,数学中一般记做\(\lfloor x\rfloor\),计算机科学中一般记做\(floor(x)\);

  3. 向下取整:不小于该数的最小的整数,数学中一般记做\(\lceil x\rceil\),计算机科学中一般记做\(ceil(x)\);

性质

  1. 整除的性质:

    (1) \(a|b,b|c\Rightarrow a|c\);

    (2) \(a|c,b|c,gcd(a,b)=1\Rightarrow ab|c\);

    (3) \(a|bc,gcd(a,b)=1\Rightarrow a|c\);

    (4) \(p|ab\Rightarrow p|a或p|b\)。

  2. 取整的性质:

    (1) \(\lceil\frac ab\rceil=\lfloor\frac{a+b−1}b\rfloor\);

    (2) \(\lfloor\frac ab\rfloor=\lceil\frac{a-b+1}b\rceil\);

    (3) \(a>\lfloor\frac cb\rfloor\Leftrightarrow ab>c\);

    (4) \(a<\lceil\frac cb\rceil\Leftrightarrow ab < c\);

    (5) \(a\leq\lfloor \frac cb\rfloor\Leftrightarrow ab\leq c\);

    (6) \(a<\lfloor\frac cb\rfloor\Leftrightarrow ab < c-b+1\);

    (7) \(a\geq\lceil \frac cb\rceil\Leftrightarrow ab\geq c\);

    (8) \(a>\lceil\frac cb\rceil\Leftrightarrow ab>c+b-1\)。

最大公因数 最小公倍数

定义

最大公因数指两个或多个整数共同具有的最大因数,记做\((a_1,a_2,\ldots ,a_n)\)或\(gcd(a_1,a_2,\ldots ,a_n)\);

最小公倍数指两个或多个整数共同具有的最小倍数,记做\(lcm(a_1,a_2,\ldots ,a_n)\)。

性质

  1. \(lcm(a,b)=\frac{ab}{gcd(a,b)}\);
  2. \(lcm(a_1,a_2,\ldots ,a_n)=\frac{a_1a_2\ldots a_n}{gcd(a_1,a_2,\ldots ,a_n)^{n-1}}\)。

求解算法

  1. 欧几里得算法
  2. 更相减损术(主要用于高精度求gcd):

\(gcd(a,b)=gcd(a,a-b),gcd(2a,2b)=gcd(a,b),gcd(2a,b)=gcd(a,b)\);

同余

定义

定义模运算:\(a\ mod\ b=a-\lfloor \frac ab \rfloor\cdot b\),即\(a\div b\)的余数。

同余:\(a\equiv b\quad (mod\ p)\Leftrightarrow a\ mod\ p=b\ mod\ p\)。

性质

  1. \(a\equiv b\quad (mod\ m)\Leftrightarrow b\equiv a\quad (mod\ m)\);
  2. \(a\equiv b\quad (mod\ m),b\equiv c\quad (mod\ m)\Rightarrow a\equiv c\quad (mod\ m)\);

  3. \(a\equiv b\quad (mod\ m)\Leftrightarrow a\pm c\equiv b\pm c\quad (mod\ m)\);

  4. \(a\equiv b\quad (mod\ m)\Leftrightarrow a\cdot c\equiv b\cdot c\quad (mod\ m)\);

  5. \(a\equiv b\quad (mod\ m),c\equiv d\quad (mod\ m)\Leftrightarrow a\cdot c\equiv b\cdot d\quad (mod\ m)\);

  6. \(a\equiv b\quad (mod\ m)\Leftrightarrow a^c\equiv b^c\quad (mod\ m)\);

  7. \(a\equiv b\quad (mod\ m)\Leftrightarrow m|(b-a)\);

  8. \(gcd(k,m)=d,ka\equiv ka’\quad (mod\ m)\Rightarrow a\equiv a’\quad (mod\ \frac md)\);

  9. 消去律:\(gcd(c,n)=1,ac\equiv bc\quad (mod\ n)\Rightarrow a\equiv b\quad (mod\ n)\)。

快速幂和快速乘法

思路

令\(b=\sum_i 2^{k_i}\),则\(a^b=a^{\sum_{i} 2^{k_i}}=\prod_{i} a^{2^{k_i}},a\cdot b=a\cdot {\sum_{i} 2^{k_i}}=\sum_{i} (a\cdot 2^{k_i})\)。

实现

类欧几里得算法

类欧几里得算法

扩展欧几里得算法

扩展欧几里得算法

素数(质数)

定义

除了\(1\)和它自身外,不能被其他自然数整除的大于\(1\)的自然数。

性质

  1. 素数的个数是无穷的;
  2. 若\(a\)为大于\( 1 \)的整数,在区间\((a, 2a] \)中必存在至少一个质数;

  3. 若\( n\)为正整数,在\(n^2 \)到\( (n + 1)^2 \)之间至少有一个质数;

  4. 若\(n \)为大于\(1 \)的整数,在\(n \)到\(n! \)之间至少有一个质数;

  5. 质数的个数公式\( \pi(n) \)约等于\(\frac{n}{\log n}\)。

乘法逆元

乘法逆元

中国剩余定理

中国剩余定理

素数相关定理

  1. 算术基本定理(唯一分解定理):对于任何一个大于\(1\)的自然数\(N\),如果\(N\)不为质数,那么\(N\)可以唯一分解成有限个质数的乘积\(p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots p_n^{a_n}\),其中\(p_1^{a_1}< p_2^{a_2}< p_3^{a_3}< \ldots < p_n^{a_n}\)均为质数,\(a_i\)为正整数。
  2. 威尔逊定理:\((p-1)!\equiv -1\quad(mod\ p)\)成立,当且仅当\(p\)是质数。

欧拉函数 欧拉定理 扩展欧拉定理 费马小定理

欧拉函数

剩余类与剩余系

所有与整数\(a\)模\(n\)同余的整数构成的集合叫做模\(n\)的一个剩余类,记做\([a]\),\(a\)称作剩余类\([a]\)的一个代表元。

从模\(n\)的每个剩余类中各取一个数组成的集合,叫做模\(n\)的一个完全剩余系。

从模\(n\)的每个互质剩余类中各取一个数组成的集合,叫做模\(n\)的一个简化剩余系(缩系),有\(\varphi(n)\)个元素。

素数判定

  1. 定义法(\(O(n)\))。
  2. 试除法(\(O(\sqrt n)\)):

    枚举\(2\sim\sqrt n\)范围内的数,判定能否整除\(n\)。

  3. Miller_Rabbin算法

整数分解(分解质因子)

  1. 试除法(\(O(\sqrt n)\))

  2. 费马因数分解:

    首先将\(n\)的所有\(2\)因子提取出来,使得\(n\)是一个奇数,这时可以将\(n\)表示为\(c\cdot d\),且\(c,d\)均为整数,设\(c > d\);

    设\(a=\frac{c+d}2,b=a=\frac{c-d}2\),于是\(c=a+b,d=a-b\),于是\(n=a^2-b^2\);

    又根据\(a \geq \sqrt{c\cdot d}=\sqrt n\),我们可以枚举大于\(n\)的完全平方数\(a\),判断\(a^2-n\)是否为完全平方数,求出\(c,d\)然后递归分解即可。

  3. Pollard_rho算法

素数筛

素数筛

阶和原根

定义

若\((a,p)=1,p > 1\),使得\(a^x\equiv 1\quad(mod\ p)\)成立的最小正整数\(x\)称为\(a\)模\(p\)的阶,记为\(\delta_pa\)。

性质

  1. 若\((a,p)=1,p > 0\),那么正整数\(x\)是同余式\(a^x\equiv 1\quad(mod\ p)\)的一个解当且仅当\(\delta_pa|x\);

  2. 若\((a,p)=1,p > 0\),则\(\delta_pa|\varphi(p)\);

  3. 若\((a,p)=1,p > 0\),那么正整数\(a^i\equiv a^j\quad(mod\ p)\),当且仅当\(i\equiv j\quad(mod\ \delta_pa)\),其中\(i,j \geq 0\);

  4. \(\delta_p{(a^k)}=\frac{\delta_pa}{(\delta_pa,k)}\);

  5. \((\delta_pa,k)=1\)时,\(\delta_p{(a^k)}=\delta_pa\)。

求解算法

暴力枚举\(\varphi(p)\)的因数。

原根

定义

满足\(\delta_pa=\varphi(p)\)的\(a\)称为模\(p\)的原根。

性质

  1. 只有\(2,4,p^k,2p^k\)存在原根,其中\(p\)为奇质数,\(k\)为任意自然数;

  2. 当正整数\(p\)存在原根时,它就有\(\varphi(\varphi(p))\)个原根;

  3. 若\((a,p)=1,p > 0\),如果\(a\)是模\(p\)的一个原根,则\(a^0,a^1,\ldots,a^{\varphi(p)-1}\)模\(p\)两两不同余,即\(\{a^0,a^1,\ldots,a^{\varphi(p)-1}\}\)构成模\(p\)的缩系;

  4. 如果\(a\)是模\(p\)的原根,那么\(a^{p-1}\equiv 1\quad(mod\ p)\)当且仅当指数为\(p-1\)的时候成立(\(p\)是素数);

求解算法

求模\(p\)的原根\(a\):

从小到大枚举\(a\),判断是否为原根:

令\(\varphi(p)=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}\),若恒有\(a^{\frac{\varphi(p)}{p_i}}\not=1\quad(mod\ p)\),则\(a\)是模\(p\)的原根。

证明:

如果\(a\)不是模\(p\)的原根,那么存在\(t < \varphi(p)\)使得\(a^t\equiv 1\quad(mod\ p)\);

根据裴蜀定理,一定存在一组\(k,r\)使得\(kt+r\varphi(p)=gcd(t,\varphi(p))\);

于是:

\(\begin{align}1 & \equiv a^t \\ & \equiv a^{kt} \\ & \equiv a^{gcd(t,\varphi(p))-r\varphi(p)}\\ & \equiv a^{gcd(t,\varphi(p))}\quad(mod\ p)\end{align}\)

又\(t < p-1\),于是\(gcd(t,\varphi(p)) < p-1\);

又\(gcd(t,\varphi(p)) | p-1\),故\(gcd(t,\varphi(p))\)至少整除\(\frac{\varphi(p)}{p_1},\frac{\varphi(p)}{p_2},\ldots,\frac{\varphi(p)}{p_k}\)其中之一,假设\(gcd(t,\varphi(p))|\frac{\varphi(p)}{p_i}\);

于是\(a^{\frac{\varphi(p)}{p_i}}\equiv {a^{gcd(t,\varphi(p))}}^s\equiv 1^s\equiv 1\quad(mod\ p)\)。

二次剩余

二次剩余

BSGS exBSGS

BSGS算法

数论函数(算术函数)

定义

指定义域为正整数、陪域为复数的函数。

有关概念

  1. 积性函数:有如下性质的,定义域为正整数的数论函数:\(f(1)=1\),且当\(a\)和\(b\)互质时,\(f(ab)=f(a)f(b)\),若对于任意\(a,b\)都满足上述性质,则称其为完全积性函数;

  2. 狄利克雷卷积:设\(f\),\(g\)是两个数论函数,则卷积运算\(f\ast g\)定义为:\[(f\ast g)(n) = \sum_{d|n}{f(d)g(\frac nd)}\]

    卷积运算满足:

    (1) 交换律:\(f\ast g=g\ast f\);

    (2) 结合律:\((f\ast g)\ast h=f\ast(g\ast h)\)。

    (3) 分配律:\(f\ast (g+h)=f\ast g+f\ast h=(g+h)\ast f\)

举例

  1. \(\varphi(n)\),欧拉函数;

  2. \(e(n)\),元函数,定义为\(e(n)=[n=1]\);

  3. \(1(n)\) ,不变的函数,定义为\(1(n)=1\)(完全积性);

  4. \(Id(n)\),单位函数,定义为\(Id(n)=n\)(完全积性);

  5. \(d(n)\),\(n\)的因数个数,定义为\(d(n)=\sum_{d|n} 1\);

  6. \(\varepsilon(n)\),狄利克雷卷积单位元,定义为\(\varepsilon(n)=\begin{cases}1,\quad n=1\\0,\quad n\not=1\end{cases}\)(完全积性);

    易得:\((\varepsilon\ast f)(n) = \sum_{ij=n} \varepsilon(i)f(j)\),即\(\varepsilon\ast f=f\);

  7. \(gcd(n,k)\),最大公因数,当\(k\)固定的情况;

  8. \(\sigma(n)\),\(n\)的正因子之和,定义为\(\sigma(n)=\sum_{d|n} d\);

  9. \(\sigma_k(n)\),除数函数,定义为\(\sigma_k(n)=\sum_{d|n} d^k\);

  10. \((\frac np)\),勒让德符号,当\(p\)是固定质数的情况(完全积性);

  11. \(\mu(n)\),莫比乌斯函数。

性质

如果\(f(n),g(n)\)是积性函数,那么下列函数也是积性函数:

  1. \(h(n)=f(n^k)\);

  2. \(h(n)=f^k(n)\);

  3. \(h(n)=f(n)g(n)\);

  4. \(h(n)=\sum_{d|n} f(d)g(\frac nd)\)。

莫比乌斯函数 莫比乌斯反演

莫比乌斯函数及莫比乌斯反演

线性筛

线性筛

One comment

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注