整数模与裴蜀定理

                     

贡献者: int256

预备知识 整除,素数与合数

定义 1 数的模

   数的模(module)是指,对于一个数的集合 $S$,若任意两个 $S$ 中的元素 $x, y$,他们的和与差 $(x\pm y)$ 都是 $S$ 中的元素,即 $\forall x, y \in S$,$(x \pm y) \in S$。

   显然单独一个数 $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$,则 $\forall n \in \mathbb Z$,$na \in S$。

定理 1 

   除零模外,任何整数模都是某正整数 $d$ 的整数倍构成的集合。

   证明:由 $\forall a \in S$, $\forall n \in \mathbb Z, na \in S$,可知 $\forall a, b \in S$, $\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$,证毕!

定理 2 

   对于整数 $a, b$ 的模:$\forall x, y \in \mathbb Z$,所有 $xa+yb$ 组成的模 $S$,其是由 $d=(a, b)$ 的整数倍组成的集合。

   证明:这整数模应当是某正整数 $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 - q s = 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 = ax_0 + by_0$,所以由整除性质知 $d|s$,而 $s > 0$,故 $d \le s$。综上,$s = d$。

   证毕!

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

定理 3 裴蜀定理

   方程 $ax + by = n$ 有整数解当且仅当 $d | n$。特别的,$ax+by = d$ 是可以求解的。

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

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

                     

© 小时科技 保留一切权利