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$。

總結與術語

整除是整數倍關係；最大公因數規範為正數。互素表示最大公因數為一；貝祖系數將該最大公因數表示成線性組合。有理數是等價分數的一個類，而不是唯一的分子分母對。每次數系擴張都需要良定義的運算；實數完備性是有理數算術之外的額外性質。