数论复习笔记-1

（这里大概不会涉及代码）

同余关系

算术基本定理

表述

对于任何一个大于$1$的正整数$n$，$n$都能被唯一分解为有限个质数的乘积，写作：

$$n = p_1^{c_1} p_2^{c_2} \cdots p_m^{c_m}$$

其中$c_i \ge 1$、$p_i$是质数$(\forall i)$，且$p_1<p_2< \cdots <p_m$。

证明一

证明一使用了最小数原理。
假设$\exists M, P(M)$：“$M$可以有不唯一的分解”成立，那么令$M’$为最小的这样的$M$。
把$M’$写成$\Pi_{i = 1}^{s} p_i$和$\Pi_{i = 1}^{t} q_i$，并令$p_i \le p_{i + 1}, q_i \le q_{i + 1}$。必然有$p_1\neq q_1$，否则可以找到更小的$M''=\frac{M'}{p_1}$使得$P(M’’)$成立。
设$p_1<q_1$。那么令$T = p_1 \Pi_{i = 2}^{t} q_i, N = M' - T$。由于$M’$是持有性质$P$的最小元素，并且$T<M’$，故$N$为正整数，并且$N$有唯一分解。
把$N$写作$N=p_1(\Pi_{i = 2}^{t} p_i - \Pi_{i = 2}^{t} q_i)=(q_1-p_1)\Pi_{i = 2}^{t} q_i$，那么由于$N$有唯一分解，所以左式中$p_1$是右式中某个数的因数。因为$p_1<q_i(\forall i \ge 2)$，所以$p_1 \mid q_1-p_1 \implies p_1\mid q_1$。矛盾。
故唯一分解定理成立。

证明二

推论

求最大公约数

证明的一些idea:把更相减损术作为推论去证明欧几里得算法。