====== 数论概论学习小结 ====== ===== 第5章 整除性与最大公因数 ===== === 定理 5.1 （欧几里得算法） === 要计算两个整数 $a$ 与 $b$ 的最大公因数，先令 $r_{-1}=a$ 且 $r_{0}=b$， 然后计算相继的商和余数 $$ r_{i-1}=q_{i+1} \times r_i+r_{i+1} (i = 0,1,2,\dots) $$ 直到某余数 $r_{n+1}$ 为 $0$. 最后的非零余数 $r_n$ 就是 $a$ 与 $b$ 的最大公因数. ===== 第6章 线性方程与最大公因数 ===== === 定理 6.1 （线性方程定理） === 设 $a$ 与 $b$ 是非零整数， $g=gcd(a,b).$ 方程 $$ax+by=g$$ 总是有一个整数解 $(x_1,y_1)$，它可由前面叙述的欧几里得算法得到. 则方程的每一个解可由 $$( x_1+k\cdot\frac{b}{g},y_1-k\cdot\frac{a}{g} )$$得到, 其中 $k$ 可为任意整数. ===== 第7章 因数分解与算术基本定理 ===== === 断言 7.1 === 令 $p$ 是素数, 假设 $p$ 整除乘积 $ab$ , 则 $p$ 整除 $a$ 或 $p$ 整除 $b$ (或者 $p$ 既整除 $a$ 也整除 $b$ ) === 定理 7.2 (素数整除性质) === 假设素数 $p$ 整除乘积 $a_1a_2\dots a_r$, 则 $p$ 整除 $a_1,a_2,\dots,a_r$ 中至少一个因数 === 定理 7.3 (算术基本定理) === 每个整数 $n \ge 2$可唯一分解成素数乘积 $$ n=p_1p_2\dots p_r $$ ===== 第8章 同余式 ===== 如果 $m$ 整除 $a-b$ , 我们就说 $a$ 与 $b$ 模 $m$ 同余并记之为 $$ a \equiv b \pmod{m} $$ 数 $m$ 叫做同余式的模. 具有相同模的同余式在许多方面表现得很像通常的等式.如果 $$ a_1 \equiv b_1 \pmod{m}, a_2 \equiv b_2 \pmod{m} $$ 则 $$ a_1 \pm a_2 \equiv b_1 \pm b_2 \pmod{m}, a_1a_2 \equiv b_1b_2 \pmod{m} $$ **提醒**: 用数除同余式并非总是可能的. 换句话说, 如果 $ac \equiv bc \pmod{m}$, 则 $a \equiv b \pmod{m}$ 未必成立. 然而, 如果 $gcd(c,m)=1$, 则可从同余式 $ac \equiv bc \pmod{m}$ 两边消去 $c$. === 定理 8.1 (线性同余式定理) === 设 $a$, $c$ 与 $m$ 是整数, $m \ge 1$, 且设 $g=gcd(a,m)$. (a)如果 $g \nmid c$, 则同余式 $ax \equiv c \pmod{m}$ 没有解 (b)如果 $g \mid c$, 则同余式 $ax \equiv c \pmod{m}$ 恰好有 $g$ 个不同的解. 要求这些解, 首先求线性方程 $$ au+mv=g $$ 的一个解 $(u_0, v_0)$ (第6章叙述了解这个方程的方法). 则 $ x_0=cu_0/g $ 是 $ax \equiv c \pmod{m}$ 的解, 不同余解的完全集由 $$ x \equiv x_0 + k \cdot \frac{m}{g} \pmod{m}, k=0,1,2,\dots,g-1 $$ 给出. ===== 第9章 同余式、幂与费马小定理 ===== === 定理 9.1 (费马小定理) === 设 $p$ 是素数, $a$ 是任意整数且 $a \equiv\mkern-17mu/$ $0 \pmod{p}$, 则 $$ a^{p-1} \equiv 1 \pmod{p}. $$ === 断言 9.2 === 设 $p$ 是素数, $a$ 是任何整数且 $a \equiv\mkern-16mu/$ $0 \pmod{p}$, 则数 $$ a,2a,3a,\dots,(p-1)a \pmod{p} $$ 与数 $$ 1,2,3,\dots,(p-1) \pmod{p} $$ 相同, 尽管它们的次序不同. ===== 第 10 章 同余式、幂与欧拉公式 ===== 在 $0$ 与 $m$ 之间且与 $m$ 互素的整数个数是个重要的量, 我们赋予这个量一个名称: $$ \phi(m)=\#\{a:1\le a \le m, gcd(a,m)=1 \}. $$ 函数 $\phi$ 叫做欧拉函数. === 定理 10.1 (欧拉公式) === 如果 $gcd(a,m)=1$, 则 $$ a^{\phi (m)} \equiv 1 \pmod{m} $$ === 断言 10.2 === 如果 $gcd(a,m)=1$, 则数列 $$ b_1a,b_2a,b_3a, \dots , b_{\phi (m)}a \pmod{m} $$ 与数列 $$ b_1,b_2,b_3,\dots,b_{\phi (m)}\pmod{m} $$ 相同, 尽管它们可能次序不同 ===== 第 11 章 欧拉 $\phi$ 函数与中国剩余定理 ===== === 定理 11.1 ( $\phi$ 函数公式) === - 如果 $p$ 是素数且 $k\ge1$, 则 $$ \phi(p^k)=p^k-p^{k-1}. $$ - 如果 $gcd(m, n)=1$, 则 $\phi(mn)=\phi(m)\phi(n)$. === 定理 11.2 (中国剩余定理) === 设 $m$ 与 $n$ 是整数, $gcd(m,n)=1$, $b$ 与 $c$ 是任意整数. 则同余式组 $$ x \equiv b\pmod{m} \ \ 与\ \ x \equiv c\pmod{n} $$ 恰有一个解 $0\le x\le mn.$ ===== 第 12 章 素数 ===== === 定理 12.1 (无穷多素数定理) === 存在无穷多个素数. === 定理 12.2 (模 4 余 3 的素数定理) === 存在无穷多个模 4 余 3 的素数. === 定理 12.3 (算术级数的素数狄利克雷定理) === 设 $a$ 与 $m$ 是整数, $gcd(a,m)=1.$ 则存在无穷多个素数模 $m$ 余 $a$ , 则存在无穷多个素数 $p$ 满足 $$ p \equiv a \pmod{m} $$ ===== 第 13 章 素数计数 ===== $$ \pi(x)=\#\{素数p|p \le x \}. $$ === 定理 13.1 (素数定理) === 当 $x$ 很大时, 小于 $x$ 的素数个数近似等于 $x/\ln(x)$. 换句话说, $$ \lim_{x \rightarrow \infty}\frac{\pi(x)}{x/\ln(x)}=1 $$ ===== 第 14 章 梅森素数 ===== === 命题 14.1 === 如果对整数 $a \ge 2$ 与 $n \ge 2$, $a^n-1$ 是素数, 则 $a$ 必等于 $2$ 且 $n$ 一定是素数 形如 $2^p-1$ 的素数叫做//梅森素数// ===== 第 15 章 梅森素数与完全数 ===== //完全数//是等于其真因数之和的数 === 定理 15.1 (欧几里得完全数公式) === 如果 $2^p-1$ 是素数, 则 $2^{p-1}(2^p-1)$ 是完全数 === 定理 15.2 (欧拉完全数定理) === 如果 $n$ 是完全数, 则 $n$ 是 $$ n=2^{p-1}(2^p-1) $$ 形式, 其中 $2^p-1$ 是梅森素数 $$ \sigma(n)=n 的所有因数之和(包括 1 与 n). $$ === 定理 15.3 ($\sigma$函数公式) === - 如果 $p$ 是素数, $k \ge 1$, 则 $$ \sigma(p^k)=1+p+p^2+\dots+p^k=\frac{p^{k+1}-1}{p-1} $$ - 如果 $gcd(m, n)=1$, 则 $$ \sigma(mn)=\sigma(m)\sigma(n). $$ ===== 第 16 章 幂模 m 与逐次平方法 ===== === 算法 16.1 (逐次平方计算 $a^k \pmod{m}$ ) === 用下述步骤计算 $a^k \pmod{m}$ 的值: - 将 $k$ 表成 $2$ 的幂次和: $$ k=u_0+u_1\cdot2+u_2\cdot2^2+u_3\cdot2^3+\dots+u_r\cdot2^r $$ 其中每个 $u_i$ 是 $0$ 或 $1$. (这种表示式叫做 $k$ 的二进制展开.)
  1. 使用逐次平方法制作模 $m$ 的 $a$ 的幂次表.
$$ a^1\equiv A_0 \pmod{m}\\ a^2\equiv (a^1)^2\equiv A_0^2\equiv A_1 \pmod{m}\\ a^4\equiv (a^2)^2\equiv A_1^2\equiv A_2 \pmod{m}\\ a^8\equiv (a^4)^4\equiv A_2^2\equiv A_3 \pmod{m}\\ \vdots \\ a^{2r}\equiv(a^{2r-1})^2\equiv A_{r-1}^2\equiv A_r \pmod{m} $$ 注意要计算表的每一行, 仅需要取前一行最末的数, 平方它然后用模 $m$ 简化. 也注意到表有 $r+1$ 行, 其中 $r$ 是第 $1$ 步中 $k$ 的二进制展开式中 $2$ 的最高指数.
  1. 乘积
$$ A_0^{u_0}\cdot A_1^{u_1}\cdot A_2^{u_2}\cdots A_r^{u_r}\pmod{m} $$ 同余于 $a^k \pmod{m}$. 注意到所有 $u_i$ 是 $0$ 或 $1$, 因此这个数实际上是 $u_i$ 等于 $1$ 的那些 $A_i$ 的乘积. ===== 第 17 章 计算模 m 的 k 次根 ===== === 算法 17.1 (计算模 m 的 k 次根原理) === 设 $b$, $k$, 与 $m$, 是已知整数, 满足 $$ gcd(b,m)=1 与 gcd(k,\phi(m))=1. $$ 下述步骤给出同余式 $$ x^k \equiv b \pmod{m} $$ 的解. - 计算 $\phi(m)$. (见第 11 章.) - 求满足 $ku-\phi(m)v=1$ 的正整数 $u$ 与 $v$. (见第6章, 另一种叙述方法是 $u$ 是为满足 $ku\equiv 1\pmod{\phi(m)}$ 的正整数, 所以 $u$ 实际上是 $k\pmod{\phi(m)}$ 的逆) - 用逐次平方法计算 $b^u\pmod{m}$. (见第 16 章.)所得值给出解 $x$. ===== 第 19 章 素性测试与卡米歇尔数 ===== //卡米歇尔数//是这样的合数 $n$, 即对每个整数 $1 \le a\le n$, 都有 $$ a^n \equiv a\pmod{n} $$ 换句话说, 卡米歇尔数是可冒充素数的一种合数, 因为它没有合数特征的证据. - 每个卡米歇尔数是奇数. - 每个卡米歇尔数是不同素数的乘积. === 定理 19.1 (卡米歇尔数的考塞特判别法) === 设 $n$ 是合数. 则 $n$ 是卡米歇尔数当且仅当它是奇数, 且整除 $n$ 的每个素数 $p$ 满足下述两个条件: - $p^2$ 不整除 $n$. - $p-1$ 整除 $n-1$. === 定理 19.2 (素数的一个性质) === 设 $p$ 是奇素数, 记 $$ p-1=2^kq, q\ 是奇数. $$ 设 $a$ 是不被 $p$ 整除的任何数, 则下述两个条件之一成立: - $a^q$ 模 $p$ 余 $1$ - 数 $a^q,a^{2q},a^{2^2q},\cdots,a^{2^{k-1}q}$ 之一模 $p$ 余 $-1$ === 定理 19.3 (合数的拉宾-米勒测试) === 设 $n$ 是奇素数, 记 $n-1=2^kq$, $q$ 是奇数. 对不被 $n$ 整除的某个 $a$, 如果下述两个条件都成立, 则 $n$ 是合数. - $a^q \equiv \mkern-17mu/ \ 1 \pmod{n}$ , - 对所有 $i=0,1,2,\cdots,k-1,a^{2iq}\equiv\mkern-17mu/ -1 \pmod{n}$ 如果 $n$ 是奇合数, 则 $1$ 与 $n-1$ 之间至少有 $75\%$ 的数可作为 $n$ 的拉宾-米勒证据. 换句话说, 每个合数有许多拉宾-米勒证据来说明它的合数性, 所以, 不存在拉宾-米勒测试的任何“卡米歇尔型数”. ===== 第 20 章 欧拉 $\phi$ 函数与因数和 ===== 对任意整数 $n$, 定义函数 $F(n)$: $$ F(n)=\phi(d_1)+\phi(d_2)+\cdots+\phi(d_r), $$ 其中 $d_1,d_2,\cdots,d_r$ 是 $n$ 的因数. === 断言 20.1 === 如果 $gcd(m,n)=1$, 则 $F(mn)=F(m)F(n)$ === 定理 20.2 (欧拉 $\phi$ 函数求和公式) === 设 $d_1,d_2,\cdots,d_r$ 是 $n$ 的因数, 则 $$ \phi(d_1)+\phi(d_2)+\cdots+\phi(d_r)=n.(\sum_{d|n}\phi(d)=n) $$ ===== 第 21 章 幂模 p 与原根 ===== 如果 $a$ 与 $p$ 互素, 费马小定理(第 9 章)告诉我们 $$ a^{p-1}\equiv 1\pmod{p} $$ //$a$ 模 $p$ 的次数(或阶)指// $$ e_p(a)=(使得 a^e\equiv 1\pmod{p}的最小指数 e\ge 1) $$ (注意仅允许 $a$ 与 $p$ 互素.) === 定理 21.1 (次数整除性质) === 设 $a$ 是不被素数 $p$ 整除的整数, 假设 $a^n\equiv 1\pmod{p}$, 则次数 $e_p(a)$ 整除 $n$. 特别地, 次数 $e_p(a)$ 总整除 $p-1$. 具有最高次数 $e_p(g)=p-1$ 的数称为 模 $p$ 的原根. === 定理 21.2 (原根定理) === 每个素数 $p$ 都有原根. 更精确地, 有恰好 $\phi(p-1)$ 个模 $p$ 的原根.. ===== 第 22 章 原根与指标 ===== 模素数 $p$ 的原根 $g$ 的优美体现在每个模 $p$ 的非零数以 $g$ 的幂次出现. 所以, 对任何 $1\le a