6. 整数、整除与有理数构造

学习目标与定义

不凭数值猜测证明整除结果，从整数对构造有理数，并区分有理数代数与实数完备性。对整数 $a,b$，$a\mid b$ 表示存在整数 $k$ 使 $b=ak$。素数是满足 $p\ge2$ 且正因数只有 $1,p$ 的整数。非同时为零的整数的最大公因数 $\gcd(a,b)$ 是其最大正公因数。

定理：整数除法与贝祖等式

对整数 $a$ 和 $b>0$，存在唯一整数 $q,r$ 使 $a=bq+r$、$0\le r<b$。对非同时为零的整数 $a,b$，存在整数 $s,t$ 使 $\gcd(a,b)=sa+tb$。

带余除法的证明。 在形式为 $a-bq$ 的非负整数中选取最小的 $r$；取充分小的负数 $q$ 可知这种数存在。若 $r\ge b$，则 $r-b$ 是更小的非负候选数，矛盾。若有两种除法表示，其余数之差为 $b$ 的倍数且绝对值小于 $b$，故差为零，商也相等。

贝祖等式的证明。 正整数形式的组合 $sa+tb$ 存在，因为 $a,b$ 至少一个非零且可以选择符号。选取最小的此类正组合 $d$。用 $d$ 除 $a$；余数也是整数线性组合，因此最小性迫使余数为零。同理 $d\mid b$。$a,b$ 的任何公因数都整除每个组合，因而整除 $d$。所以 $d$ 是最大正公因数，并有要求的表示。

推论：欧几里得引理。 若素数 $p$ 整除 $ab$ 而不整除 $a$，则 $\gcd(p,a)=1$。写 $sp+ta=1$，乘以 $b$。左侧每项都被 $p$ 整除，故 $p\mid b$。这是在归纳证明存在性之外，证明素因数分解唯一性所需的关键一步。

有理数作为等价类

取满足 $b\ne0$ 的整数对 $(a,b)$，若 $ad=bc$ 则定义 $(a,b)\sim(c,d)$。自反性和对称性显然。传递性方面，$ad=bc$、$cf=de$ 蕴含 $adf=bcf=bde$；约去非零的 $d$ 得 $af=be$。因此这是等价关系，其类即有理数 $a/b$。

定义加法 $a/b+c/d=(ad+bc)/(bd)$ 和乘法 $(a/b)(c/d)=ac/(bd)$。规则必须不依赖代表元。例如若 $ab'=a'b$、$cd'=c'd$，则 $acb'd'=(ab')(cd')=(a'b)(c'd)=a'c'bd$，验证乘法与代表元无关。加法检查可展开 $(ad+bc)b'd'$ 并代入相同的两个等式。非零分母对该构造不可缺少。

例题

欧几里得算法。 $252=1(198)+54$、$198=3(54)+36$、$54=1(36)+18$、$36=2(18)$。回代得 $18=4(252)-5(198)$，所以最大公因数为 $18$。除法步骤保持公因数集合，因为两个数的公因数整除其余数，反过来也成立。

无理性证明。 若 $\sqrt2=a/b$ 已约至最简，且 $a,b$ 为正整数，则 $a^2=2b^2$。偶数平方的底数为偶数，故 $a=2c$。代入得 $b^2=2c^2$，所以 $b$ 也为偶数。两者共有因子二，与最简形式矛盾。该证明排除有理数相等，并不构造实数平方根或证明 $\mathbb R$ 的完备性。

分层练习

1. 基础。 用 $5$ 除 $-17$，使余数位于要求的范围内。
2. 核心。 求 $\gcd(35,22)$ 并表示成整数线性组合。
3. 核心。 使用欧几里得引理证明 $\sqrt3$ 是无理数。
4. 证明。 若 $\gcd(a,m)=1$ 且 $a x\equiv a y\pmod m$，证明 $x\equiv y\pmod m$。给出不互素时的反例。

详解

1. $-17=5(-4)+3$，且 $0\le3<5$。若用商 $-3$，余数会为负，违反所选约定。
2. $35=22+13$、$22=13+9$、$13=9+4$、$9=2(4)+1$。回代得 $1=8(22)-5(35)$，所以最大公因数为一。
3. 假设 $\sqrt3=a/b$ 已约至最简且 $b>0$。则 $a^2=3b^2$，由欧几里得引理 $3\mid a$。写 $a=3c$ 得 $b^2=3c^2$，所以 $3\mid b$，与互素矛盾。
4. 贝祖等式给出 $sa+tm=1$。乘以 $x-y$ 后，由于 $m\mid a(x-y)$，左侧两项均被 $m$ 整除，故 $m\mid x-y$。没有互素性时，$2\cdot0\equiv2\cdot2\pmod4$，但 $0\not\equiv2\pmod4$。

总结与术语

整除是整数倍关系；最大公因数规范为正数。互素表示最大公因数为一；贝祖系数将该最大公因数表示成线性组合。有理数是等价分数的一个类，而不是唯一的分子分母对。每次数系扩张都需要良定义的运算；实数完备性是有理数算术之外的额外性质。