\(\huge 4\) 数论
4.1 整除性
定义
整除
如果 \(m>0\) 且 \(n/m\) 是一个整数，就说 \(m\) 整除 \(n\) （或者 \(n\) 被 \(m\) 整除）.记为
\[m|n \Leftrightarrow m>0 \text{且对某个整数}\ k\ \text{有}\ n=mk\ .\ \ \ \ (4.1)
\]
整除 \(\mid\) 不整除 \(\nmid\)
\(n\) 是 \(m\) 的倍数在 \(m\le 0\) 的时候仍然适用，但整除不行。
最大公因子
两个整数 \(m\) 和 \(n\) 的最大公因子是能整除它们两者的最大整数。
\(gcd(m,n)=max\{k\mid k|m\ \text{且}\ k|n\}\)
\(gcd(0,n)=n,gcd(0,0)\) 无定义.
最小公倍数
\(lcm(m,n)=min\{k\mid k>0,m|k\ 且\ n|k\}\)
欧几里得算法
欧几里得算法
\[ \begin{aligned}
&gcd(0,n)=n;\\
&gcd(m,n)=gcd(n\bmod m,m),&m>0.
\end{aligned}
\]
拓展欧几里得算法
算法
解 \(m'm+n'n=gcd(m,n)\ \ \ \ (4.5)\)
具体算法：
\(m=0\) 时，直接取 \(m'=0,n'=1\)
否则，令 \(r=n\bmod m\) ，用 \(r\) 和 \(m\) 替换 \(m\) 和 \(n\) ，计算出 \(\overline r,\overline m\),使得
\(\overline r r+\overline m m=gcd(r,m)\)
由于 \(r=n-\lfloor n/m\rfloor m,且gcd(r,m)=gcd(m,n)\)
所以
\(\overline r (n-\lfloor n/m\rfloor m)+\overline mm=gcd(m,n)\)
\((\overline m-\lfloor n/m\rfloor \overline r )m+\overline r n=gcd(m,n)\)
所以 \(m'=\overline m-\lfloor n/m\rfloor \overline r ,n'=\overline r\)
小结论
\[ k|m 和 k|n \Leftrightarrow k|gcd(m,n)
\]
trick
\[ \sum_{m|n} a_m=\sum_{m|n} a_{n/m}
\]
\[ \sum_{m|n} a_m=\sum_k \sum_{m>0} a_m[n=mk]
\]
\[ \sum_{m|n} \sum_{k|m} a_{k,m}=\sum_{k|n} \sum_{l|(n/k)} a_{k,kl}
\]
4.2 素数
如果一个正整数 \(p\) 恰好只有两个因子，即 \(1\) 和 \(p\) ，那么这个数就称为素数。
算数基本定理
\[ n=p_1...p_m=\prod_{k=1}^m p_k,p_1\le p_2\le...\le p_m
\]
或
\[ n=\prod_p p^{n_p}
\]
内容
有且仅有一种方式将 \(n\) 按照素数非减的次序写成素数的乘积。
证明
假设有两种方法。
1肯定只有一种方法。
\(n=p_1...p_m=q_1...q_k,p_1\le...\le p_m,q_1\le...\le q_k\)
要证明 \(p_1=q_1\)
如果 \(p_1 由于 \(p_1,q_1\) 为素数，所以 \(gcd(p_1,q_1)=1\) \(ap_1+bq_1=1\) \(ap_1q_2...q_k+bq_1q_2...q_k=q_2...q_k\) ∵ \(q_1...q_k=n\) 所以 \(p_1|\) 左边两项，因此 \(p_1|q_2...q_k\) \(\frac {q_2...q_k} {p_1}\) 为整数， \(p_1\) 在 \(q_2...q_k\) 的一个素因子分解式中出现。 但是 \(q_2...q_k 因此 \(p_1\) 一定等于 \(q_2\) 或者...或者 \(q_k\) 。而 \(q_1\) 比他们都小，这个矛盾表明 \(p_1\) 一定等于 \(q_1\) 。 这样一来，就能用 \(p_1\) 除两边。 \(p_2...p_m=q_2...q_k 应用(?) \[ k=gcd(m,n) \Leftrightarrow k_p=min(m_p,n_p) ，对所有p\\ k=lcm(m,n)\Leftrightarrow k_p=max(m_p,n_p)，对所有 p \] 4.3 素数的例子 有无穷多个素数。 欧几里得数 欧几里得数： \(e_{k+1}=2*3*5*...*p_k+1\) 不一定是质数。反例 \(e_5=1807=13*139\) \(gcd(e_m,e_n)=1\) 可以用欧几里得算法证明： \(gcd(e_m,e_n)=gcd(1,e_n)=gcd(0,1)=1\) \(e_n=e_1..e_{n-2}e_{n-1}+1=(e_{n-1}-1)e_{n-1}=e_{n-1}^2-e_{n-1}+1\) $e_n=\lfloor E{2n}+\frac 1 2\rfloor $ 常数 \(E≈1.264\) \(p_n=\lfloor P^{3^n} \rfloor\) \(P\) 为常数。 梅森数 梅森数： \(2^p-1\) 许多素数是梅森数。 当 \(n\) 为合数时，$2^n-1 $ 不可能是素数，因为 \(2^{km}-1=(2^m-1)(2^{m(k-1)}+2^{m(k-2)}+...+1)\) 但 \(n\) 为质数时， \(2^n-1\) 不总为素数，最小的例子是 \(2^{11}-1=23*89\) 素数分布 第 \(n\) 个素数 \(P_n\)~\(n\ln n\) 不超过 \(x\) 的素数个数 \(\pi (x)\)~\(\frac x {\ln x}\) 更为精确的： \[ \ln x -\frac 3 2<\frac x {\pi (x)}<\ln x-\frac 1 2,x\ge 67;\\ n(\ln x+\ln\ln n-\frac 3 2) \] 孪生素数：\(p\) 和 \(p+2\) 埃氏筛 4.4 阶乘的因子 定义 \[ n!=\prod_{k=1}^n k,整数 n\ge0 \] \(0!=1\) \(n!=(n-1)!n\) 增长速度 \[ n!^2=(1*2*3*...*n)*(n*(n-1)*...*1)=\prod_{k=1}^n k(n+1-k) \] \(k(n+1-k)=\frac 1 4(n+1)^2-(k-\frac 1 2(n+1))^2\) 在 \(k=1\) 和 \(k=n\) 时取最小值，在 \(k=\frac 1 2(n+1)\) 时取最大值。 于是 \(n\le k(n+1-k)\le \frac 1 4 (n+1)^2\) \[ \prod_{k=1}^n n\le n!^2\le \prod_{k=1}^n \frac {(n+1)^2} 4\\ n^{\frac n 2} \le n!\le \frac {(n+1)^n} {2^n} \] 阶乘以指数方式增长。 斯特林公式 \(n!\)~\(\sqrt {2\pi n}(\frac n e)^n\) 误差约 \(\frac 1 {12n}\) 素数与阶乘 \(\varepsilon_p(n)\) 是能整除 \(n!\) 的 \(p\) 的最大幂。 直尺函数 \(\rho (i)=\sum_i [n! \bmod {p^i}=0]\) \[ \varepsilon_p (n!)=\lfloor \frac n {p}\rfloor +\lfloor \frac n {p^2}\rfloor +\lfloor \frac n {p^3}\rfloor +...=\sum_{k\ge 1} \lfloor \frac n {p^k} \rfloor \] 上界： \[ \begin{aligned} \varepsilon_p (n!)&<\frac n p+\frac n {p^2}+...\\ &=\frac n p (1+\frac 1 p+...)\\ &=\frac n p (\frac p {p-1})\\ &=\frac n {p-1} \end{aligned} \] \(p^{\varepsilon_p(n!)} ∵ \(p\le 2^{p-1}\) ∴ \(p^{n/(p-1)}\le2^n\) 任何素数对 \(n!\) 的贡献都小于 \(2^n\) 利用这个可以证明有无穷多个素数。如果只有 \(k\) 个素数 \(2,3,...,p_k\) ，每个素数至多贡献一个因子 \(2^n-1\)，\(n!<(2^n)k=2^{nk}\) ，但选取足够大的 \(n\) ，例如 \(n=2^{2k}\) 时会和 \(n!<2^{nk}\) 产生矛盾。 \(n!<2^{nk}=2^{2^{2k}k}=n^{\frac n 2}\) 与 \(n!\ge n^{\frac n 2}\) 矛盾。因此有无穷多个素数。 \[ n!<2^{n\pi(n)} \] 用斯特林数（它是下界）近似代替 \(n!\) \[ \sqrt {2\pi n}(\frac n e)^n<2^{n\pi(n)} \] 取对数 \(\lg\) 是 2 为底数的。 \[ n\pi(n)>n\lg (n/e)+\frac 1 2 \lg(2\pi n)\\ \pi(n)>\lg (n/e) \] 4.5 互素 定义 当 \(gcd(m,n)=1\) 时，整数 \(m\) 和 \(n\) 没有公共的素因子，我们就称他们是互素的。 符号 $\perp $ \[ m\perp n \Leftrightarrow m,n是整数，且gcd(m,n)=1 \] 性质 \[\frac m {gcd(m,n)}\perp \frac n {gcd(m,n)} \] 可以由 \(gcd(km,kn)=kgcd(m,n)\) 推导而来。 \[m\perp n\Leftrightarrow min(m_p,n_p)=0,对所有p. \] \[m\perp n\Leftrightarrow m_pn_p=0,对所有p. \] \[k\perp m且 k\perp n \Leftrightarrow k\perp mn \] 另一种说法：当 \(m_p\) 与 \(n_p\) 非负时， \(k_pm_p=0\) 且 \(k_pn_p=0\) 当且仅当 \(k_p(m_p+n_p)=0\) Stern-Brocot 树 定义、构造及证明 一个构造满足 \(m\perp n\) 的全部非负分数 \(m/n\) 组成的集合的方法，Stern-Brocot树。 从 \((\frac 0 1,\frac 1 0)\) 出发，按照希望的次数重复以下操作： 在两个相邻的分数 \(\frac mn\) 和 \(\frac {m'} {n'}\) 之间插入 \(\frac {m+m'} {n+n'}\) 证明： 如果 \(m/n\) 和 \(m'/n'\) 是这个构造中任何一个阶段的相邻分数，我们就有 \(m'n-mn'=1\) 这个关系式开始时是正确的 \((1*1-0*0=1)\) 当插入一个新的中位分数 \((m+m')/(n+n')\) 时， \[(m+m')n-m(n+n')=1;\\ m'(n+n')-(m+m')n'=1. \] 这两个等式都等价于它们所替代的原始条件。 此外，如果 \(m/n \[m/n<(m+m')/(n+n') \] 如果在某个阶段 \(\frac m n <(\frac a b)<\frac {m'} {n'}\) \((m+m')/(n+n')=a/b\) \(m/n\rightarrow (m+m')/(n+n')\) \({m'}/{n'} \rightarrow (m+m')/(n+n')\) \[\frac a b-\frac m n>0和\frac {m'} {n'} -\frac a b>0\\ 蕴含 an-bm\ge 1 和 bm'-an'\ge 1\\ 从而\\ (m'+n')(an-bm)+(m+n)(bm'-an')\ge m+m'+n+n'\\ a+b\ge m+n+m'+n' \] 每一步右边都在增加，所以至多 \(a+b\) 步后会得到 \(a/b\) 法里级数 定义 \(\mathcal{F}_N\) 介于0和1之间分母不超过 \(N\) 的最简分数组成的集合。递增排列。 构造 从Stern-Brocot 树里选 \(\mathcal F_{N-1}\)在分母之和等于 \(N\) 的相邻分数之间插入分数 \((m+m')/N\) 应用 \(ma-nb=1\) 在 \(m\perp n且0 法里级数给出了另一个证明，设 \(b/a\) 是 \(\mathcal{F}_N\) 中位于 \(m/n\) 之前的分数， 这样 \(m'm+n'n=gcd(m,n)\) 等价于 \(m'n-mn'=1\) \(3a-7b=1\) 的一个解是 \(a=5,b=2\) 如果 \(0 同样的，\(0\le n 其他性质 将 Stern-Brocot 树 看成一个表示有理数的数系。因为每个正的最简分数都恰好出现一次。 我们用字母 \(L\) 和 \(R\) 表示从这棵树的树根走到一个特定的分数时向左下方或者右下方的分支前进，这样一串 \(L\) 和 \(R\) 就唯一确定了树中唯一一个位置。每个正的分数都表示成了唯一的一串 \(L\) 和 \(R\) 。 \(\frac 1 1\) 与空字符串对应，用 \(I\) 表示，代表“单位元”。 给定一个由 \(L\) 和 \(R\) 组成的字符串 \(S\) ，与它对应的分数是什么？ 如果 \(m/n\) 和 \(m'/n'\) 是这棵树上一层与他相邻的二分数，那么它会变为 \((m+m')/(n+n')\) 初始 \(m/n=0/1,m'/n'=1/0\) \[M(I)= \begin{pmatrix} 1 & 0 \\ 0& 1 \end{pmatrix} \quad\\ M(s)= \begin{pmatrix} n & n' \\ m & m' \end{pmatrix} \quad\\ 向左一步用 n+n' 代替 n'，用m+m'代替m'，从而\\ \begin{aligned} M(SL)&= \begin{pmatrix} n & n+n' \\ m & m+m' \end{pmatrix} \quad\\ &=\begin{pmatrix} n & n' \\ m & m' \end{pmatrix} * \begin{pmatrix} 1& 1 \\ 0 & 1 \end{pmatrix} \quad\\ &=M(S)*\begin{pmatrix} 1& 1 \\ 0 & 1 \end{pmatrix} \end{aligned} 同理\\ M(SR)=M(S)*\begin{pmatrix} 1& 1 \\ 1 & 0 \end{pmatrix} \\ M(L)=\begin{pmatrix} 1& 1 \\ 0 & 1 \end{pmatrix},M(R)=\begin{pmatrix} 1& 1 \\ 1 & 0 \end{pmatrix} \] 给定 \(m\perp n\) 的正整数 \(m\) 和 \(n\) ，与 \(m/n\) 对应的由 \(L\) 和 \(R\) 的字符串是什么？ 由前一个问题，可以“二叉搜索” S:=I while m/n != f(S) do if m/n else (output(R); S:=SR) 发现 \[f(RS)=\frac m n 时， \Leftrightarrow \frac {m-n} n = f(S)\\ f(LS)=\frac m n 时，\Leftrightarrow \frac m {n-m}=f(S) \] while m!=n do if m else(output(R);m:=m-n) 可以试试找 \(e\)， \(e=RL^0RLR^2LRL^4RLR^6LRL^8...\) 可以用这个估算，前16个字母得到的分数的准确度和 \(e\) 的二进制表示法的十六位准确度相当。 用以估算无理数的程序 while 1 do if a<1 then(output(L); a:=a/(1-a)) else(output(R); a:=a-1) a 视为 a/1,即 m=a,n=1 如果算有理数将会导致在右侧增加 \(RLLLLLLLLLLLLL...\) 发现欧几里得算法与有理数 Stern-Brocot 表示之间的关系： 给定 \(\alpha=m/n\) ，先得到 \(\lfloor m/n\rfloor\) 个 \(R\)，再得到 \(\lfloor n/(m\bmod n)\rfloor\) 个 \(L\)，再得到 \(\lfloor (m\bmod n)/(n\bmod (m\bmod n))\rfloor\)，以此类推，恰好是欧几里得算法中检验的那些值。 4.6 同余关系 \(d\) 与 \(m\) 互素时， \(ad\equiv bd \Leftrightarrow a\equiv b\bmod m,a,b,d,m是整数,d\perp m\) 证明： \(d'd+m'm=1\) 欧几里得找出 \(d'\) 所以 \(d'd\equiv 1\) \[ add'\equiv bdd'\\ a\equiv b\\ \] \(d'\) 的作用类似 \(1/d\) 称其为逆元。 \[ad\equiv bd \mod{md}\Leftrightarrow a\equiv b\bmod m ，d是整数 \] \[ad\equiv bd \bmod m\Leftrightarrow a\equiv b \bmod \frac m {gcd(d,m)},a,b,d,m是整数 \] \[a\equiv b \bmod m ,a\equiv b \bmod n\Leftrightarrow a\equiv b \bmod {lcm(m,n)}, 整数m,n>0 \] \[a\equiv b \bmod m ,a\equiv b \bmod n\Leftrightarrow a\equiv b \bmod {mn}, 整数m,n>0,m\perp n （中国剩余定理） \] \[a\equiv b \bmod m ,a\equiv b \bmod m\Leftrightarrow a\equiv b \bmod {\bmod p^{m_p}},对所有p \] 4.7 独立剩余 剩余系： 整数 \(x\) 表示成为关于一组互素的模的剩余（余数）序列： \[Res(x)=(x\bmod m_1,...,x\bmod m_r), 对1\le j \] 知道 \(x\bmod m_1,...x\bmod m_r\) 可以确定 \(x\bmod m,m=\prod m_i\) \(\bmod 3\) 和 \(\bmod 5\) 推出 \(\bmod 15\) 举例：\(7=(1,2),13=(1,3)\) \(7*13=(1,1)\) 推出其 \(\bmod 15=1\) 可以用几个大素数确定一个数。 甚至可以用于除法，用几个大素数，\(D\bmod p_k=D_k\) 如果恰好整除了就换一个素数。 考虑如何从 \((x\bmod m_1,...,x\bmod m_r)\) 举例：\((x\bmod 3,x\bmod 5)\) 如果 \(a=(1,0),b=(0,1)\)，\((x,y)=(ax+by)\bmod 15\) \[a\bmod m=1,a\bmod n=0,b\bmod m=0,b\bmod n =1 \] \(mm'+nn'=1\) 欧几里得算法。取 \(a=nn',b=mm'\) 尝试求解 \(x^2\equiv 1\bmod m\) \[(x-1)(x+1)\equiv 0 \bmod p^k \] \(p\neq2\) 时，\(p^k|(x-1)(x+1) \Leftrightarrow p^k|(x-1)或p^k|(x+1)\)，恰有两个解 \(x\equiv1\) 和 \(x\equiv -1\) \(p=2\) 时，显然其中一个被4整除，另一个被 \(2^{k-1}\) 整除，\(k\ge 3\) 时有四个解， \(x\equiv 1或 x\equiv -1\) 或 \(x\equiv 2^{k-1}+1\) 或 \(x\equiv 2^{k-1}-1\) 精确的解数是 \(2^{r+[8|m]+[4|m]-[2|m]}\) （\(m=2\) 时，考虑 \(k\) 的数值。） 4.8 进一步的应用 第三章企图证明 \[0\bmod m,n\bmod m,2n\bmod m,...,(m-1)n\bmod m \] 按照某种次序恰好组成 \(m/d\) 个数。 \[0,d,2d,...,m-d \] 的 \(d\) 份复制，其中 \(d=gcd(m,n)\) e.g. \(m=12,n=8\) 时， \(d=4\)， \(0,8,4,0,8,4,0,8,4,0,8,4\) 证明 得到前面的 \(m/d\) 个数的 \(d\) 份复制是显然的。因为 \[jn\equiv kn \bmod m \Leftrightarrow j(n/d)\equiv k(n/d) \bmod(m/d) \] 从而当 \(0\le k 需要证明这 \(m/d\) 个数是 \(\{0,d,2d,...,m-d\}\) 的某个排列。 记 \(m=m'd,n=n'd\) ，根据分配律， \[kn \bmod m=d(kn'\bmod m') \] 所以 \(0\le k