整数模与裴蜀定理

贡献者： int256

　　 显然单独一个数 $0$ 也构成一个模，称为零模（null module）。

　　 由数的模的定义可知，若 $a\in S$，则 $(a-a)=0\in S$，即 $0$ 总在数的模中。

　　 而对于整数的模，若 $a\in S$，则 $a+a=2a\in S$，类似的，$2a+a=3a\in S$，依此类推。而 $0\in S$，故 $0-a\in S$。综合以上两个性质，就有，若 $a\in S$，则 $\mathrm{\forall }n\in \mathbb{Z}$，$na\in S$。

　　 证明：由 $\mathrm{\forall }a\in S$, $\mathrm{\forall }n\in \mathbb{Z},na\in S$，可知 $\mathrm{\forall }a,b\in S$, $\mathrm{\forall }n,m\in \mathbb{Z},(na+mb)\in S$。我们考虑 $S$ 中的最小正整数 $d$（这是显然存在的），而对于正数 $n\in S$，则对于所有的整数 $z$ 显然都有 $n-zd\in S$。

　　 考虑 $c$ 是 $n$ 被 $d$ 除得到的余数，即 $n=zd+c$，$0\le c<d$，$z\in \mathbb{Z}$。由 $c=n-zd$ 知 $c\in S$，而 $d$ 是 $S$ 中的最小正数，$0\le c<d$，故 $c=0$ 且 $n=zd$，证毕！

　　 证明：这整数模应当是某正整数 $c$ 的整数倍 $zc$ 组成的集合。而对于 $d=(a,b)$，$d|a$, $d|b$，且 $x,y\in \mathbb{Z}$，故 $d|(xa+yb)$，故 $S$ 中的每个元素都是 $d$ 的倍数。

　　 下面证明 $d\in S$。考虑 $s=a{x}_0+b{y}_0$ 是 $ax+by$ 的最小正整数值，令 $q$ 是 $a/s$ 的整数部分，即 $q=\lfloor a/s\rfloor$，而 $r$ 是 $a$ 除以 $s$ 的余数，即 $r=a-qs=a-q(a{x}_0+b{y}_0)$。这就是说，$r=a(1-q{x}_0)+b(-q{y}_0)$。从而 $r$ 也是 $ax+by$ 的某 $(x,y)$ 的值。而由于 $r$ 是 $a$ 除以 $s$ 的余数，故必定有 $0\le r<s$，而 $s$ 是最小的正整数值，故 $r=0$，从而有 $s|a$。类似的有 $s|b$，故 $s$ 是 $a$ 与 $b$ 的公约数。故 $d\ge s$。而 $d|a$，$d|b$，且 $s=a{x}_0+b{y}_0$，所以由整除性质知 $d|s$，而 $s>0$，故 $d\le s$。综上，$s=d$。

　　 证毕！

　　 这定理可以直接引导出裴蜀定理。

　　 现在就可以证明算术基本定理。直接证明定理 2 （欧几里得第一定理），而通过欧几里得第一定理导出算术基本定理的方法已经在标准型与唯一分解定理一文中讨论过。

　　 考虑 $p$ 是素数且 $p|ab$，若 $p\text{⧸}\mid a$ 则 $(a,p)=1$，由裴蜀定理指出存在整数 $x,y$ 使得 $ax+py=1$。也就是 $abx+pby=b$。而 $p|ab$ 且 $p|pb$，故 $p|b$。证毕！